Copyright | (c) Andrey Mokhov 2016-2018 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | unstable |
Safe Haskell | None |
Language | Haskell2010 |
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.
Synopsis
- bfsForest :: Ord a => [a] -> AdjacencyMap a -> Forest a
- bfs :: Ord a => [a] -> AdjacencyMap a -> [[a]]
- dfsForest :: Ord a => AdjacencyMap a -> Forest a
- dfsForestFrom :: Ord a => [a] -> AdjacencyMap a -> Forest a
- dfs :: Ord a => [a] -> AdjacencyMap a -> [a]
- reachable :: Ord a => a -> AdjacencyMap a -> [a]
- topSort :: Ord a => AdjacencyMap a -> Either (Cycle a) [a]
- isAcyclic :: Ord a => AdjacencyMap a -> Bool
- scc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a)
- isDfsForestOf :: Ord a => Forest a -> AdjacencyMap a -> Bool
- isTopSortOf :: Ord a => [a] -> AdjacencyMap a -> Bool
- type Cycle = NonEmpty
Algorithms
bfsForest :: Ord a => [a] -> AdjacencyMap a -> Forest a Source #
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
2forest
(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]] Source #
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
gives an enumeration of vertices
reachable from concat
. bfs
vsvs
in breadth first order.
Let L be the number of seed vertices. Complexity: O((L+m)*log n) time and O(n) space.
bfs vsempty
== [] 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 Source #
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.
dfsForestempty
== []forest
(dfsForest $edge
1 1) ==vertex
1forest
(dfsForest $edge
1 2) ==edge
1 2forest
(dfsForest $edge
2 1) ==vertices
[1,2]isSubgraphOf
(forest
$ dfsForest x) x == TrueisDfsForestOf
(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 Source #
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 vsempty
== []forest
(dfsForestFrom [1] $edge
1 1) ==vertex
1forest
(dfsForestFrom [1] $edge
1 2) ==edge
1 2forest
(dfsForestFrom [2] $edge
1 2) ==vertex
2forest
(dfsForestFrom [3] $edge
1 2) ==empty
forest
(dfsForestFrom [2,1] $edge
1 2) ==vertices
[1,2]isSubgraphOf
(forest
$ dfsForestFrom vs x) x == TrueisDfsForestOf
(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] Source #
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] Source #
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] Source #
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 FalseisRight
. topSort ==isAcyclic
topSort .vertices
== Right .nub
.sort
scc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a) Source #
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.
sccempty
==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
TrueisAcyclic
x == (scc x ==gmap
NonEmpty.vertex
x)
Correctness properties
isDfsForestOf :: Ord a => Forest a -> AdjacencyMap a -> Bool Source #
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 Source #
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