blob: 4c8593b9f6f803b4bb94eca427f8085b35fd8f23 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# dynamicgraphs
## Summary
A Haskell library for dealing with the _dynamic connectivity_ problem. Consider
an undirected graph, where edges may be added and removed. This library allows
you to answer the question "are the nodes X and Y connected" at any point in
time.
This blogpost has some more information about this library:
<https://jaspervdj.be/posts/20190111dynamicgraphs.html>.
## Installation
`dynamicgraphs` is available on
[hackage](https://hackage.haskell.org/package/dynamicgraphs). You can install
it using Stack, Cabal, Nix, or whichever tool you prefer.
## Example
```haskell
import qualified Data.Graph.Dynamic.Levels as GD
import qualified Data.Tree as T
main :: IO ()
main = do
graph < GD.empty'
mapM_ (GD.insert_ graph) ["Akanu", "Kanoa", "Kekoa", "Kaiwi", "Onakea"]
GD.link_ graph "Akanu" "Kanoa"
GD.link_ graph "Akanu" "Kaiwi"
GD.link_ graph "Akanu" "Onakea"
GD.link_ graph "Kaiwi" "Onakea"
GD.link_ graph "Onakea" "Kanoa"
GD.link_ graph "Kanoa" "Kekoa"
GD.connected graph "Kaiwi" "Kekoa" >>= print
GD.cut_ graph "Kaiwi" "Akanu"
GD.cut_ graph "Onakea" "Akanu"
GD.cut_ graph "Onakea" "Kanoa"
GD.connected graph "Kaiwi" "Kekoa" >>= print
GD.link_ graph "Akanu" "Kaiwi"
GD.connected graph "Kaiwi" "Kekoa" >>= print
```
