ghc-graphs
A simple monadic graph library
A "not-very-Haskelly" API for calculating traversals of graphs that may be too large to fit into memory. The algorithms included are inspired by the visitor concept of the<http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/visitor_concepts.html Boost Graph Library>. Here is a very simple example of how we might execute a depth-first-search. In this case the visitor simply collects the edges and vertices in the order that the corresponding functions get called. After the necessary imports,>import Data.Array>import Data.Monoid>import Data.Graph.AdjacencyList>import Data.Graph.Algorithm>import Data.Graph.Algorithm.DepthFirstSearch create an adjacency list where the vertices are labeled with integers.>graph :: Array Int [Int]>graph = array (0, 3) [(0, [1,2]), (1, [3]), (2, [3]), (3, [])]<<http://i.imgur.com/Pod1SH0.png>>We need a data structure that instantiates `Monoid` to combine the results of our visitor functions. ' data Orderings = Orderings  {  enterV :: [Int]  , enterE :: [(Int, Int)]  , gray :: [(Int, Int)]  , exitV :: [Int]  , black :: [(Int, Int)]  } deriving Show instance Monoid Orderings where mempty = Orderings [] [] [] [] [] mappend (Orderings a1 a2 a3 a4 a5)(Orderings b1 b2 b3 b4 b5) =  Orderings (a1 ++ b1) (a2 ++ b2) (a3 ++ b3) (a4 ++ b4) (a5 ++ b5) ' The `dfs` function's first argument is of type `GraphSearch` which is a visitor containing the functions to be run at various times during the search. The second argument is the starting vertex for the search. ' orderings :: GraphSearch (AdjacencyList Int) Orderings orderings = GraphSearch  (v ->return $ mempty{enterV = [v]}  (e ->return $ mempty{enterE = [e]}  (e ->return $ mempty{gray = [e]}  (v ->return $ mempty{exitV = [v]}  (e ->return $ mempty{black = [e]} ' Finally `runAdjacencylist` unwraps the function in the `Adjacencylist` newtype and runs it on `graph`.>dfsTest :: Orderings>dfsTest = runAdjacencyList (dfs orderings 0) graph Running `dfsTest` in ghci will yield: ' Orderings{enterV = [0,2,3,1], enterE = [(0,2),(2,3),(0,1)], gray = [], exitV = [3,2,1,0], black = [(1,3)]} '.
BSD-3-Clause