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`

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]] 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`

vs`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 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.

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 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 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] 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 False`isRight`

. 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.

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 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