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
- Check if you have installed the right swift version
- Add this package as dependency in your
Package.swift
- Import the module in your code:
import DynamicConnectivityHLT
- 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:
-
Use Xcode 8.0 beta
- Download Xcode 8.0 beta
-
Generate xcodeproj
sudo xcode-select -switch /Applications/Xcode-beta.app/Contents/Developer xcrun swift package generate-xcodeproj
- Use the swift compiler in Xcode or use the compiler with the terminal (for example:
xcrun swift build
,xcrun swift test
)
-
Install via Vagrant
- Install Vagrant
-
ssh into the vagrant-box and change to the current directory:
vagrant up vagrant ssh cd /vagrant
- now you can use the swift compiler (for example:
swift build
,swift test
)
<3