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.AdjacencyIntMap data type.
Some of the worst-case complexities include the term min(n,W).
Following IntSet
and IntMap
, the W stands for
word size (usually 32 or 64 bits).
Synopsis
- bfsForest :: [Int] -> AdjacencyIntMap -> Forest Int
- bfs :: [Int] -> AdjacencyIntMap -> [[Int]]
- dfsForest :: AdjacencyIntMap -> Forest Int
- dfsForestFrom :: [Int] -> AdjacencyIntMap -> Forest Int
- dfs :: [Int] -> AdjacencyIntMap -> [Int]
- reachable :: Int -> AdjacencyIntMap -> [Int]
- topSort :: AdjacencyIntMap -> Either (Cycle Int) [Int]
- isAcyclic :: AdjacencyIntMap -> Bool
- isDfsForestOf :: Forest Int -> AdjacencyIntMap -> Bool
- isTopSortOf :: [Int] -> AdjacencyIntMap -> Bool
- type Cycle = NonEmpty
Algorithms
bfsForest :: [Int] -> AdjacencyIntMap -> Forest Int 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)*min(n,W)) 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 :: [Int] -> AdjacencyIntMap -> [[Int]] 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)*min(n,W)) 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 :: AdjacencyIntMap -> Forest Int 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)*min(n,W)) 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 :: [Int] -> AdjacencyIntMap -> Forest Int 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 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)*min(n,W)) 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 :: [Int] -> AdjacencyIntMap -> [Int] Source #
Compute the vertices visited by depth-first search in a graph
from the given vertices. Adjacent vertices are explored in
increasing order with respect to their Ord
instance.
Let L be the number of seed vertices. Complexity: O((L+m)*min(n,W)) 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 :: Int -> AdjacencyIntMap -> [Int] 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*min(n,W)) 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 :: AdjacencyIntMap -> Either (Cycle Int) [Int] 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 Int)
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)*min(n,W)) 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 topSort .vertices
== Right .nub
.sort
isAcyclic :: AdjacencyIntMap -> Bool Source #
Correctness properties
isDfsForestOf :: Forest Int -> AdjacencyIntMap -> 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 :: [Int] -> AdjacencyIntMap -> 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