DynamicConnectivity

• DynamicConnectivityHLT Implementation of a dynamic connectivity data structure, based on the idea of Holm, Lichtenberg and Thorub

Note

This implementation has still some problems / bugs. I will try to fix them as fast as possible. So be nice.

Complexity

• Add an edge: O(log n) amortized
• Remove an edge: O(log n) amortized
• Connectivity queries: O(log n) amortized

Implementation Details

• Uses an Euler Tour Tree
• The Euler Tour Tree is based on a Splay Tree

Use this package

1. Check if you have installed the right swift version
2. Add this package as dependency in your Package.swift
3. Import the module in your code: import DynamicConnectivityHLT
4. Use it. See main.swift for an example

Install swift and compile this project

This Implementation is tested with the swift 3.0 preview 1.

There are many possibilities to use swift. Two of them are:

1. Use Xcode 8.0 beta

   1. Download Xcode 8.0 beta

   2. Generate xcodeproj

      sudo xcode-select -switch /Applications/Xcode-beta.app/Contents/Developer
      xcrun swift package generate-xcodeproj
      

   3. Use the swift compiler in Xcode or use the compiler with the terminal (for example: xcrun swift build, xcrun swift test)

2. Install via Vagrant

   1. Install Vagrant

   2. ssh into the vagrant-box and change to the current directory:

      vagrant up
      vagrant ssh
      cd /vagrant
      

   3. now you can use the swift compiler (for example: swift build, swift test)

<3