dynamic-graphs: Dynamic graph algorithms

[ bsd3, data, library ] [ Propose Tags ]

A library for dynamic graph algorithms, and in particular dynamic connectivity.

[Skip to Readme]
Versions [faq],
Change log CHANGELOG.md
Dependencies base (>=4.8 && <5), containers (>=0.3 && <0.7), criterion, deepseq, dynamic-graphs, hashable (>=1.0 && <1.3), hashtables (==1.2.*), mwc-random (>=0.12 && <0.15), primitive (>=0.5 && <0.7), QuickCheck, semigroups (==0.18.*), text, unordered-containers (==0.2.*), vector (>=0.10 && <0.13) [details]
License BSD-3-Clause
Copyright 2018-2019 Alex Lang, Jasper Van der Jeugt
Author Alex Lang, Jasper Van der Jeugt
Maintainer me@alang.ca
Category Data
Home page http://github.com/alang9/dynamic-graphs
Bug tracker http://github.com/alang9/dynamic-graphs/issues
Source repo head: git clone git://github.com/alang9/dynamic-graphs.git
Uploaded by JasperVanDerJeugt at Fri Jan 11 23:50:18 UTC 2019
Distributions NixOS:
Executables gen-program, bench-program, dynamic-graphs-simple
Downloads 56 total (56 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-01-12 [all 1 reports]


[Index] [Quick Jump]



Build the auxiliary executables, including benchmarks, tools and examples


Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Maintainer's Corner

For package maintainers and hackage trustees

Readme for dynamic-graphs-

[back to package description]



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.


dynamic-graphs is available on hackage. You can install it using Stack, Cabal, Nix, or whichever tool you prefer.


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