Algebra.Graph.AdjacencyMap.Algorithm

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module provides basic graph algorithms, such as depth-first search, implemented for the Algebra.Graph.AdjacencyMap data type.

Algorithms

bfsForest :: Ord a => [a] -> AdjacencyMap a -> Forest a

Compute the breadth-first search forest of a graph, such that adjacent vertices are explored in increasing order with respect to their Ord instance. The search is seeded by a list of argument vertices that will be the roots of the resulting forest. Duplicates in the list will have their first occurrence expanded and subsequent ones ignored. Argument vertices not in the graph are also ignored.

Let L be the number of seed vertices. Complexity: O((L+m)*log n) time and O(n) space.

forest (bfsForest [1,2] $ edge 1 2)      == vertices [1,2]
forest (bfsForest [2]   $ edge 1 2)      == vertex 2
forest (bfsForest [3]   $ edge 1 2)      == empty
forest (bfsForest [2,1] $ edge 1 2)      == vertices [1,2]
isSubgraphOf (forest $ bfsForest vs x) x == True
bfsForest (vertexList g) g               == map (v -> Node v []) (nub $ vertexList g)
bfsForest [] x                           == []
bfsForest [1,4] (3 * (1 + 4) * (1 + 5))  == [ Node { rootLabel = 1
                                                   , subForest = [ Node { rootLabel = 5
                                                                        , subForest = [] }]}
                                            , Node { rootLabel = 4
                                                   , subForest = [] }]
forest (bfsForest [3] (circuit [1..5] + circuit [5,4..1])) == path [3,2,1] + path [3,4,5]

bfs :: Ord a => [a] -> AdjacencyMap a -> [[a]]

This is bfsForest with the resulting forest converted to a level structure. Adjacent vertices are explored in increasing order with respect to their Ord instance. Flattening the result via concat . bfs vs gives an enumeration of vertices reachable from vs in breadth first order.

Let L be the number of seed vertices. Complexity: O((L+m)*log n) time and O(n) space.

bfs vs empty                                         == []
bfs [] g                                             == []
bfs [1]   (edge 1 1)                                 == [[1]]
bfs [1]   (edge 1 2)                                 == [[1],[2]]
bfs [2]   (edge 1 2)                                 == [[2]]
bfs [1,2] (edge 1 2)                                 == [[1,2]]
bfs [2,1] (edge 1 2)                                 == [[2,1]]
bfs [3]   (edge 1 2)                                 == []
bfs [1,2] ( (1*2) + (3*4) + (5*6) )                  == [[1,2]]
bfs [1,3] ( (1*2) + (3*4) + (5*6) )                  == [[1,3],[2,4]]
bfs [3] (3 * (1 + 4) * (1 + 5))                      == [[3],[1,4,5]]
bfs [2] (circuit [1..5] + circuit [5,4..1])          == [[2],[1,3],[5,4]]
concat (bfs [3] $ circuit [1..5] + circuit [5,4..1]) == [3,2,4,1,5]
bfs vs == map concat . transpose . map levels . bfsForest vs

dfsForest :: Ord a => AdjacencyMap a -> Forest a

Compute the depth-first search forest of a graph, where adjacent vertices are expanded in increasing order with respect to their Ord instance.

Complexity: O((n+m)*log n) time and O(n) space.

dfsForest empty                       == []
forest (dfsForest $ edge 1 1)         == vertex 1
forest (dfsForest $ edge 1 2)         == edge 1 2
forest (dfsForest $ edge 2 1)         == vertices [1,2]
isSubgraphOf (forest $ dfsForest x) x == True
isDfsForestOf (dfsForest x) x         == True
dfsForest . forest . dfsForest        == dfsForest
dfsForest (vertices vs)               == map (\v -> Node v []) (nub $ sort vs)
dfsForestFrom (vertexList x) x        == dfsForest x
dfsForest $ 3 * (1 + 4) * (1 + 5)     == [ Node { rootLabel = 1
                                                , subForest = [ Node { rootLabel = 5
                                                                     , subForest = [] }]}
                                         , Node { rootLabel = 3
                                                , subForest = [ Node { rootLabel = 4
                                                                     , subForest = [] }]}]
forest (dfsForest $ circuit [1..5] + circuit [5,4..1]) == path [1,2,3,4,5]

dfsForestFrom :: Ord a => [a] -> AdjacencyMap a -> Forest a

Compute the depth-first search forest of a graph from the given vertices, where adjacent vertices are expanded in increasing order with respect to their Ord instance. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. Any of the given vertices which are not in the graph are ignored.

Let L be the number of seed vertices. Complexity: O((L+m)*log n) time and O(n) space.

dfsForestFrom vs empty                           == []
forest (dfsForestFrom [1]   $ edge 1 1)          == vertex 1
forest (dfsForestFrom [1]   $ edge 1 2)          == edge 1 2
forest (dfsForestFrom [2]   $ edge 1 2)          == vertex 2
forest (dfsForestFrom [3]   $ edge 1 2)          == empty
forest (dfsForestFrom [2,1] $ edge 1 2)          == vertices [1,2]
isSubgraphOf (forest $ dfsForestFrom vs x) x     == True
isDfsForestOf (dfsForestFrom (vertexList x) x) x == True
dfsForestFrom (vertexList x) x                   == dfsForest x
dfsForestFrom vs             (vertices vs)       == map (\v -> Node v []) (nub vs)
dfsForestFrom []             x                   == []
dfsForestFrom [1,4] $ 3 * (1 + 4) * (1 + 5)      == [ Node { rootLabel = 1
                                                           , subForest = [ Node { rootLabel = 5
                                                                                , subForest = [] }
                                                    , Node { rootLabel = 4
                                                           , subForest = [] }]
 forest (dfsForestFrom [3] $ circuit [1..5] + circuit [5,4..1]) == path [3,2,1,5,4]

dfs :: Ord a => [a] -> AdjacencyMap a -> [a]

Compute the vertices visited by depth-first search in a graph from the given vertices. Adjacent vertices are expanded in increasing order with respect to their Ord instance.

Let L be the number of seed vertices. Complexity: O((L+m)*log n) time and O(n) space.

dfs vs    $ empty                    == []
dfs [1]   $ edge 1 1                 == [1]
dfs [1]   $ edge 1 2                 == [1,2]
dfs [2]   $ edge 1 2                 == [2]
dfs [3]   $ edge 1 2                 == []
dfs [1,2] $ edge 1 2                 == [1,2]
dfs [2,1] $ edge 1 2                 == [2,1]
dfs []    $ x                        == []
dfs [1,4] $ 3 * (1 + 4) * (1 + 5)    == [1,5,4]
isSubgraphOf (vertices $ dfs vs x) x == True
dfs [3] $ circuit [1..5] + circuit [5,4..1] == [3,2,1,5,4]

reachable :: Ord a => a -> AdjacencyMap a -> [a]

Compute the list of vertices that are reachable from a given source vertex in a graph. The vertices in the resulting list appear in depth-first order.

Complexity: O(m*log n) time and O(n) space.

reachable x $ empty                       == []
reachable 1 $ vertex 1                    == [1]
reachable 1 $ vertex 2                    == []
reachable 1 $ edge 1 1                    == [1]
reachable 1 $ edge 1 2                    == [1,2]
reachable 4 $ path    [1..8]              == [4..8]
reachable 4 $ circuit [1..8]              == [4..8] ++ [1..3]
reachable 8 $ clique  [8,7..1]            == [8] ++ [1..7]
isSubgraphOf (vertices $ reachable x y) y == True

topSort :: Ord a => AdjacencyMap a -> Either (Cycle a) [a]

Compute a topological sort of a DAG or discover a cycle.

Vertices are expanded in decreasing order with respect to their Ord instance. This gives the lexicographically smallest topological ordering in the case of success. In the case of failure, the cycle is characterized by being the lexicographically smallest up to rotation with respect to Ord (Dual a) in the first connected component of the graph containing a cycle, where the connected components are ordered by their largest vertex with respect to Ord a.

Complexity: O((n+m)*log n) time and O(n) space.

topSort (1 * 2 + 3 * 1)                    == Right [3,1,2]
topSort (path [1..5])                      == Right [1..5]
topSort (3 * (1 * 4 + 2 * 5))              == Right [3,1,2,4,5]
topSort (1 * 2 + 2 * 1)                    == Left (2 :| [1])
topSort (path [5,4..1] + edge 2 4)         == Left (4 :| [3,2])
topSort (circuit [1..3])                   == Left (3 :| [1,2])
topSort (circuit [1..3] + circuit [3,2,1]) == Left (3 :| [2])
topSort (1*2 + 2*1 + 3*4 + 4*3 + 5*1)      == Left (1 :| [2])
fmap (flip isTopSortOf x) (topSort x)      /= Right False
isRight . topSort                          == isAcyclic
topSort . vertices                         == Right . nub . sort

isAcyclic :: Ord a => AdjacencyMap a -> Bool

Check if a given graph is acyclic.

Complexity: O((n+m)*log n) time and O(n) space.

isAcyclic (1 * 2 + 3 * 1) == True
isAcyclic (1 * 2 + 2 * 1) == False
isAcyclic . circuit       == null
isAcyclic                 == isRight . topSort

scc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a)

Compute the condensation of a graph, where each vertex corresponds to a strongly-connected component of the original graph. Note that component graphs are non-empty, and are therefore of type Algebra.Graph.NonEmpty.AdjacencyMap.

Details about the implementation can be found at gabow-notes.

Complexity: O((n+m)*log n) time and O(n+m) space.

scc empty               == empty
scc (vertex x)          == vertex (NonEmpty.vertex x)
scc (vertices xs)       == vertices (map vertex xs)
scc (edge 1 1)          == vertex (NonEmpty.edge 1 1)
scc (edge 1 2)          == edge   (NonEmpty.vertex 1) (NonEmpty.vertex 2)
scc (circuit (1:xs))    == vertex (NonEmpty.circuit1 (1 :| xs))
scc (3 * 1 * 4 * 1 * 5) == edges  [ (NonEmpty.vertex  3      , NonEmpty.vertex  5      )
                                  , (NonEmpty.vertex  3      , NonEmpty.clique1 [1,4,1])
                                  , (NonEmpty.clique1 [1,4,1], NonEmpty.vertex  5      ) ]
isAcyclic . scc == const True
isAcyclic x     == (scc x == gmap NonEmpty.vertex x)

Correctness properties

isDfsForestOf :: Ord a => Forest a -> AdjacencyMap a -> Bool

Check if a given forest is a correct depth-first search forest of a graph. The implementation is based on the paper "Depth-First Search and Strong Connectivity in Coq" by François Pottier.

isDfsForestOf []                              empty            == True
isDfsForestOf []                              (vertex 1)       == False
isDfsForestOf [Node 1 []]                     (vertex 1)       == True
isDfsForestOf [Node 1 []]                     (vertex 2)       == False
isDfsForestOf [Node 1 [], Node 1 []]          (vertex 1)       == False
isDfsForestOf [Node 1 []]                     (edge 1 1)       == True
isDfsForestOf [Node 1 []]                     (edge 1 2)       == False
isDfsForestOf [Node 1 [], Node 2 []]          (edge 1 2)       == False
isDfsForestOf [Node 2 [], Node 1 []]          (edge 1 2)       == True
isDfsForestOf [Node 1 [Node 2 []]]            (edge 1 2)       == True
isDfsForestOf [Node 1 [], Node 2 []]          (vertices [1,2]) == True
isDfsForestOf [Node 2 [], Node 1 []]          (vertices [1,2]) == True
isDfsForestOf [Node 1 [Node 2 []]]            (vertices [1,2]) == False
isDfsForestOf [Node 1 [Node 2 [Node 3 []]]]   (path [1,2,3])   == True
isDfsForestOf [Node 1 [Node 3 [Node 2 []]]]   (path [1,2,3])   == False
isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (path [1,2,3])   == True
isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (path [1,2,3])   == True
isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] (path [1,2,3])   == False

isTopSortOf :: Ord a => [a] -> AdjacencyMap a -> Bool

Check if a given list of vertices is a correct topological sort of a graph.

isTopSortOf [3,1,2] (1 * 2 + 3 * 1) == True
isTopSortOf [1,2,3] (1 * 2 + 3 * 1) == False
isTopSortOf []      (1 * 2 + 3 * 1) == False
isTopSortOf []      empty           == True
isTopSortOf [x]     (vertex x)      == True
isTopSortOf [x]     (edge x x)      == False

Type synonyms

type Cycle = NonEmpty