Hackage :: [Package]

dynamic-graphs: Dynamic graph algorithms

[ bsd3, data, library ] [ Propose Tags ]

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

[Skip to Readme]

Modules

[Last Documentation]

  • Data
    • Graph
      • Dynamic
        • Data.Graph.Dynamic.EulerTour
        • Internal
          • Data.Graph.Dynamic.Internal.Avl
          • Data.Graph.Dynamic.Internal.HashTable
          • Data.Graph.Dynamic.Internal.Random
          • Data.Graph.Dynamic.Internal.Splay
          • Data.Graph.Dynamic.Internal.Tree
        • Data.Graph.Dynamic.Levels

Flags

Manual Flags

NameDescriptionDefault
build-extra-executables

Build the auxiliary executables, including benchmarks, tools and examples

Disabled

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

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.1, 0.1.0.2, 0.1.0.3
Change log CHANGELOG.md
Dependencies base (>=4.9 && <4.12), containers (>=0.3 && <0.7), criterion, deepseq, dynamic-graphs, hashable (>=1.0 && <1.3), hashtables (>=1.2 && <1.3), mwc-random (>=0.12 && <0.14), primitive (>=0.5 && <0.7), QuickCheck, text, unordered-containers (>=0.2 && <0.3), vector (>=0.10 && <0.13) [details]
License BSD-3-Clause
Copyright 2018 Alex Lang, Jasper Van der Jeugt
Author Alex Lang, Jasper Van der Jeugt
Maintainer me@alang.ca
Revised Revision 1 made by HerbertValerioRiedel at 2019-01-11T22:35:36Z
Category Data
Uploaded by JasperVanDerJeugt at 2019-01-11T12:32:53Z
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 not available [build log]
All reported builds failed as of 2019-01-11 [all 3 reports]

Readme for dynamic-graphs-0.1.0.1

[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