name: graphs category: Algorithms, Data Structures, Graphs version: 0.7.1 license: BSD3 cabal-version: >= 1.6 license-file: LICENSE author: Edward A. Kmett maintainer: Edward A. Kmett stability: experimental homepage: http://github.com/ekmett/graphs bug-reports: http://github.com/ekmett/graphs/issues copyright: Copyright (C) 2011-2013 Edward A. Kmett synopsis: A simple monadic graph library description: 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 . . 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, [])] . <> . 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)]} @ build-type: Simple tested-with: GHC == 7.0.4 , GHC == 7.2.2 , GHC == 7.4.2 , GHC == 7.6.3 , GHC == 7.8.4 , GHC == 7.10.3 , GHC == 8.0.2 , GHC == 8.2.2 , GHC == 8.4.1 extra-source-files: .travis.yml CHANGELOG.markdown README.markdown source-repository head type: git location: git://github.com/ekmett/graphs.git library other-extensions: TypeFamilies FlexibleContexts build-depends: base >= 4 && < 5, array >= 0.3 && < 0.7, transformers >= 0.2.2 && < 0.6, transformers-compat >= 0.3 && < 1, containers >= 0.3 && < 0.6, void >= 0.5.5.1 && < 1 if !impl(ghc >= 8.0) build-depends: semigroups >= 0.16 && < 1 exposed-modules: Data.Graph.AdjacencyList Data.Graph.AdjacencyMatrix Data.Graph.Algorithm Data.Graph.Algorithm.DepthFirstSearch Data.Graph.Algorithm.BreadthFirstSearch Data.Graph.Class Data.Graph.Class.AdjacencyList Data.Graph.Class.AdjacencyMatrix Data.Graph.Class.EdgeEnumerable Data.Graph.Class.Bidirectional Data.Graph.Class.VertexEnumerable Data.Graph.Dual Data.Graph.PropertyMap other-modules: Data.Graph.Internal.Color ghc-options: -Wall -fno-warn-deprecations -- hack around the buggy unused matches check for class associated types in ghc 8 rc1 if impl(ghc >= 8) ghc-options: -fno-warn-unused-matches hs-source-dirs: src