dynamic-graphs: Dynamic graph algorithms

Versions [RSS]	0.1.0.1, 0.1.0.2, 0.1.0.3
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 && <1.3), mwc-random (>=0.12 && <0.15), primitive (>=0.5 && <0.7), QuickCheck, semigroups (>=0.18 && <0.19), text, unordered-containers (>=0.2 && <0.3), 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 2019-01-23T14:28:32Z
Distributions
Executables	gen-program, bench-program, dynamic-graphs-simple
Downloads	1529 total (12 in the last 30 days)
Rating	(no votes yet) [estimated by Bayesian average]
Your Rating	λ λ λ
Status	Docs available [build log] Last success reported on 2019-01-23 [all 1 reports]

Readme for dynamic-graphs-0.1.0.3

[back to package description]

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. You can install it using Stack, Cabal, Nix, or whichever tool you prefer.

Example

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