summaryrefslogtreecommitdiff
path: root/README.md
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
# dynamic-graphs

## 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/2019-01-11-dynamic-graphs.html>.

## Installation

`dynamic-graphs` is available on
[hackage](https://hackage.haskell.org/package/dynamic-graphs).  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
```