Copyright | (c) Andrey Mokhov 2016-2022 |
---|---|
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 according to their
Ord
instance.
The search is seeded by a list of vertices that will become the roots of the
resulting forest. Duplicates in the list will have their first occurrence
expanded and subsequent ones ignored. The seed vertices that do not belong to
the graph are also ignored.
Complexity: O((L+m)*log n) time and O(n) space, where L is the number of seed vertices.
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 #
A version of
bfsForest
where the resulting forest is converted to a level
structure. Adjacent vertices are explored in the increasing order according
to their
Ord
instance. Flattening the result via
concat
.
bfs
vs
gives an enumeration of vertices reachable from
vs
in the BFS order.
Complexity: O((L+m)*min(n,W)) time and O(n) space, where L is the number of seed vertices.
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 explored in the increasing order according 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 starting from the given
seed vertices, where adjacent vertices are explored in the increasing order
according to their
Ord
instance. Note that the resulting forest does not
necessarily span the whole graph, as some vertices may be unreachable. The
seed vertices which do not belong to the graph are ignored.
Complexity: O((L+m)*log n) time and O(n) space, where L be the number of seed vertices.
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 #
Return the list vertices visited by the
depth-first search
in a graph,
starting from the given seed vertices. Adjacent vertices are explored in the
increasing order according to their
Ord
instance.
Complexity: O((L+m)*log n) time and O(n) space, where L is the number of seed vertices.
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 #
Return the list of vertices that are reachable from a given source vertex in a graph. The vertices in the resulting list appear in the 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 :: AdjacencyIntMap -> Either ( Cycle Int ) [ Int ] Source #
Compute a topological sort of a graph or discover a cycle.
Vertices are explored in the decreasing order according 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