Copyright | (c) Andrey Mokhov 2016-2018 |
---|---|

License | MIT (see the file LICENSE) |

Maintainer | andrey.mokhov@gmail.com |

Stability | experimental |

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 defines the `AdjacencyMap`

data type, as well as associated
operations and algorithms. `AdjacencyMap`

is an instance of the `Graph`

type
class, which can be used for polymorphic graph construction and manipulation.
Algebra.Graph.IntAdjacencyMap defines adjacency maps specialised to graphs
with `Int`

vertices.

- data AdjacencyMap a
- adjacencyMap :: AdjacencyMap a -> Map a (Set a)
- empty :: Ord a => AdjacencyMap a
- vertex :: Ord a => a -> AdjacencyMap a
- edge :: Ord a => a -> a -> AdjacencyMap a
- overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
- connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
- vertices :: Ord a => [a] -> AdjacencyMap a
- edges :: Ord a => [(a, a)] -> AdjacencyMap a
- overlays :: Ord a => [AdjacencyMap a] -> AdjacencyMap a
- connects :: Ord a => [AdjacencyMap a] -> AdjacencyMap a
- fromAdjacencyList :: Ord a => [(a, [a])] -> AdjacencyMap a
- isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool
- isEmpty :: AdjacencyMap a -> Bool
- hasVertex :: Ord a => a -> AdjacencyMap a -> Bool
- hasEdge :: Ord a => a -> a -> AdjacencyMap a -> Bool
- vertexCount :: AdjacencyMap a -> Int
- edgeCount :: AdjacencyMap a -> Int
- vertexList :: AdjacencyMap a -> [a]
- edgeList :: AdjacencyMap a -> [(a, a)]
- adjacencyList :: AdjacencyMap a -> [(a, [a])]
- vertexSet :: AdjacencyMap a -> Set a
- edgeSet :: Ord a => AdjacencyMap a -> Set (a, a)
- postSet :: Ord a => a -> AdjacencyMap a -> Set a
- path :: Ord a => [a] -> AdjacencyMap a
- circuit :: Ord a => [a] -> AdjacencyMap a
- clique :: Ord a => [a] -> AdjacencyMap a
- biclique :: Ord a => [a] -> [a] -> AdjacencyMap a
- star :: Ord a => a -> [a] -> AdjacencyMap a
- starTranspose :: Ord a => a -> [a] -> AdjacencyMap a
- tree :: Ord a => Tree a -> AdjacencyMap a
- forest :: Ord a => Forest a -> AdjacencyMap a
- removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a
- removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a
- replaceVertex :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a
- mergeVertices :: Ord a => (a -> Bool) -> a -> AdjacencyMap a -> AdjacencyMap a
- transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a
- gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b
- induce :: Ord a => (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a
- dfsForest :: AdjacencyMap a -> Forest a
- dfsForestFrom :: [a] -> AdjacencyMap a -> Forest a
- dfs :: [a] -> AdjacencyMap a -> [a]
- topSort :: Ord a => AdjacencyMap a -> Maybe [a]
- isTopSort :: Ord a => [a] -> AdjacencyMap a -> Bool
- scc :: Ord a => AdjacencyMap a -> AdjacencyMap (Set a)

# Data structure

data AdjacencyMap a Source #

The `AdjacencyMap`

data type represents a graph by a map of vertices to
their adjacency sets. We define a `Num`

instance as a convenient notation for
working with graphs:

0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))

The `Show`

instance is defined using basic graph construction primitives:

show (empty :: AdjacencyMap Int) == "empty" show (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"

The `Eq`

instance satisfies all axioms of algebraic graphs:

`overlay`

is commutative and associative:x + y == y + x x + (y + z) == (x + y) + z

`connect`

is associative and has`empty`

as the identity:x * empty == x empty * x == x x * (y * z) == (x * y) * z

`connect`

distributes over`overlay`

:x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z

`connect`

can be decomposed:x * y * z == x * y + x * z + y * z

The following useful theorems can be proved from the above set of axioms.

`overlay`

has`empty`

as the identity and is idempotent:x + empty == x empty + x == x x + x == x

Absorption and saturation of

`connect`

:x * y + x + y == x * y x * x * x == x * x

When specifying the time and memory complexity of graph algorithms, *n* and *m*
will denote the number of vertices and edges in the graph, respectively.

Eq a => Eq (AdjacencyMap a) Source # | |

(Ord a, Num a) => Num (AdjacencyMap a) Source # | |

(Ord a, Show a) => Show (AdjacencyMap a) Source # | |

ToGraph (AdjacencyMap a) Source # | |

Ord a => Graph (AdjacencyMap a) Source # | |

type ToVertex (AdjacencyMap a) Source # | |

type Vertex (AdjacencyMap a) Source # | |

adjacencyMap :: AdjacencyMap a -> Map a (Set a) Source #

The *adjacency map* of the graph: each vertex is associated with a set
of its direct successors.

# Basic graph construction primitives

empty :: Ord a => AdjacencyMap a Source #

Construct the *empty graph*.
Complexity: *O(1)* time and memory.

`isEmpty`

empty == True`hasVertex`

x empty == False`vertexCount`

empty == 0`edgeCount`

empty == 0

vertex :: Ord a => a -> AdjacencyMap a Source #

Construct the graph comprising *a single isolated vertex*.
Complexity: *O(1)* time and memory.

`isEmpty`

(vertex x) == False`hasVertex`

x (vertex x) == True`vertexCount`

(vertex x) == 1`edgeCount`

(vertex x) == 0

edge :: Ord a => a -> a -> AdjacencyMap a Source #

Construct the graph comprising *a single edge*.
Complexity: *O(1)* time, memory.

edge x y ==`connect`

(`vertex`

x) (`vertex`

y)`hasEdge`

x y (edge x y) == True`edgeCount`

(edge x y) == 1`vertexCount`

(edge 1 1) == 1`vertexCount`

(edge 1 2) == 2

overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a Source #

*Overlay* two graphs. This is a commutative, associative and idempotent
operation with the identity `empty`

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

`isEmpty`

(overlay x y) ==`isEmpty`

x &&`isEmpty`

y`hasVertex`

z (overlay x y) ==`hasVertex`

z x ||`hasVertex`

z y`vertexCount`

(overlay x y) >=`vertexCount`

x`vertexCount`

(overlay x y) <=`vertexCount`

x +`vertexCount`

y`edgeCount`

(overlay x y) >=`edgeCount`

x`edgeCount`

(overlay x y) <=`edgeCount`

x +`edgeCount`

y`vertexCount`

(overlay 1 2) == 2`edgeCount`

(overlay 1 2) == 0

connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a Source #

*Connect* two graphs. This is an associative operation with the identity
`empty`

, which distributes over `overlay`

and obeys the decomposition axiom.
Complexity: *O((n + m) * log(n))* time and *O(n + m)* memory. Note that the
number of edges in the resulting graph is quadratic with respect to the number
of vertices of the arguments: *m = O(m1 + m2 + n1 * n2)*.

`isEmpty`

(connect x y) ==`isEmpty`

x &&`isEmpty`

y`hasVertex`

z (connect x y) ==`hasVertex`

z x ||`hasVertex`

z y`vertexCount`

(connect x y) >=`vertexCount`

x`vertexCount`

(connect x y) <=`vertexCount`

x +`vertexCount`

y`edgeCount`

(connect x y) >=`edgeCount`

x`edgeCount`

(connect x y) >=`edgeCount`

y`edgeCount`

(connect x y) >=`vertexCount`

x *`vertexCount`

y`edgeCount`

(connect x y) <=`vertexCount`

x *`vertexCount`

y +`edgeCount`

x +`edgeCount`

y`vertexCount`

(connect 1 2) == 2`edgeCount`

(connect 1 2) == 1

vertices :: Ord a => [a] -> AdjacencyMap a Source #

Construct the graph comprising a given list of isolated vertices.
Complexity: *O(L * log(L))* time and *O(L)* memory, where *L* is the length
of the given list.

vertices [] ==`empty`

vertices [x] ==`vertex`

x`hasVertex`

x . vertices ==`elem`

x`vertexCount`

. vertices ==`length`

.`nub`

`vertexSet`

. vertices == Set.`fromList`

edges :: Ord a => [(a, a)] -> AdjacencyMap a Source #

overlays :: Ord a => [AdjacencyMap a] -> AdjacencyMap a Source #

connects :: Ord a => [AdjacencyMap a] -> AdjacencyMap a Source #

fromAdjacencyList :: Ord a => [(a, [a])] -> AdjacencyMap a Source #

Construct a graph from an adjacency list.
Complexity: *O((n + m) * log(n))* time and *O(n + m)* memory.

fromAdjacencyList [] ==`empty`

fromAdjacencyList [(x, [])] ==`vertex`

x fromAdjacencyList [(x, [y])] ==`edge`

x y fromAdjacencyList .`adjacencyList`

== id`overlay`

(fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys)

# Relations on graphs

isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool Source #

The `isSubgraphOf`

function takes two graphs and returns `True`

if the
first graph is a *subgraph* of the second.
Complexity: *O((n + m) * log(n))* time.

isSubgraphOf`empty`

x == True isSubgraphOf (`vertex`

x)`empty`

== False isSubgraphOf x (`overlay`

x y) == True isSubgraphOf (`overlay`

x y) (`connect`

x y) == True isSubgraphOf (`path`

xs) (`circuit`

xs) == True

# Graph properties

isEmpty :: AdjacencyMap a -> Bool Source #

Check if a graph is empty.
Complexity: *O(1)* time.

isEmpty`empty`

== True isEmpty (`overlay`

`empty`

`empty`

) == True isEmpty (`vertex`

x) == False isEmpty (`removeVertex`

x $`vertex`

x) == True isEmpty (`removeEdge`

x y $`edge`

x y) == False

hasVertex :: Ord a => a -> AdjacencyMap a -> Bool Source #

Check if a graph contains a given vertex.
Complexity: *O(log(n))* time.

hasVertex x`empty`

== False hasVertex x (`vertex`

x) == True hasVertex 1 (`vertex`

2) == False hasVertex x .`removeVertex`

x == const False

vertexCount :: AdjacencyMap a -> Int Source #

The number of vertices in a graph.
Complexity: *O(1)* time.

vertexCount`empty`

== 0 vertexCount (`vertex`

x) == 1 vertexCount ==`length`

.`vertexList`

edgeCount :: AdjacencyMap a -> Int Source #

vertexList :: AdjacencyMap a -> [a] Source #

edgeList :: AdjacencyMap a -> [(a, a)] Source #

adjacencyList :: AdjacencyMap a -> [(a, [a])] Source #

The sorted *adjacency list* of a graph.
Complexity: *O(n + m)* time and *O(m)* memory.

adjacencyList`empty`

== [] adjacencyList (`vertex`

x) == [(x, [])] adjacencyList (`edge`

1 2) == [(1, [2]), (2, [])] adjacencyList (`star`

2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]`fromAdjacencyList`

. adjacencyList == id

vertexSet :: AdjacencyMap a -> Set a Source #

# Standard families of graphs

path :: Ord a => [a] -> AdjacencyMap a Source #

circuit :: Ord a => [a] -> AdjacencyMap a Source #

clique :: Ord a => [a] -> AdjacencyMap a Source #

biclique :: Ord a => [a] -> [a] -> AdjacencyMap a Source #

star :: Ord a => a -> [a] -> AdjacencyMap a Source #

starTranspose :: Ord a => a -> [a] -> AdjacencyMap a Source #

The *star transpose* formed by a list of leaves connected to a centre vertex.
Complexity: *O(L)* time, memory and size, where *L* is the length of the
given list.

starTranspose x [] ==`vertex`

x starTranspose x [y] ==`edge`

y x starTranspose x [y,z] ==`edges`

[(y,x), (z,x)] starTranspose x ys ==`connect`

(`vertices`

ys) (`vertex`

x) starTranspose x ys ==`transpose`

(`star`

x ys)

tree :: Ord a => Tree a -> AdjacencyMap a Source #

The *tree graph* constructed from a given `Tree`

data structure.
Complexity: *O((n + m) * log(n))* time and *O(n + m)* memory.

tree (Node x []) ==`vertex`

x tree (Node x [Node y [Node z []]]) ==`path`

[x,y,z] tree (Node x [Node y [], Node z []]) ==`star`

x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==`edges`

[(1,2), (1,3), (3,4), (3,5)]

# Graph transformation

removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a Source #

removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a Source #

Remove an edge from a given graph.
Complexity: *O(log(n))* time.

removeEdge x y (`edge`

x y) ==`vertices`

[x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .`removeVertex`

x ==`removeVertex`

x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2

replaceVertex :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a Source #

The function

replaces vertex `replaceVertex`

x y`x`

with vertex `y`

in a
given `AdjacencyMap`

. If `y`

already exists, `x`

and `y`

will be merged.
Complexity: *O((n + m) * log(n))* time.

replaceVertex x x == id replaceVertex x y (`vertex`

x) ==`vertex`

y replaceVertex x y ==`mergeVertices`

(== x) y

mergeVertices :: Ord a => (a -> Bool) -> a -> AdjacencyMap a -> AdjacencyMap a Source #

Merge vertices satisfying a given predicate into a given vertex.
Complexity: *O((n + m) * log(n))* time, assuming that the predicate takes
*O(1)* to be evaluated.

```
mergeVertices (const False) x == id
mergeVertices (== x) y ==
````replaceVertex`

x y
mergeVertices even 1 (0 * 2) == 1 * 1
mergeVertices odd 1 (3 + 4 * 5) == 4 * 1

transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a Source #

gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b Source #

Transform a graph by applying a function to each of its vertices. This is
similar to `Functor`

's `fmap`

but can be used with non-fully-parametric
`AdjacencyMap`

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

gmap f`empty`

==`empty`

gmap f (`vertex`

x) ==`vertex`

(f x) gmap f (`edge`

x y) ==`edge`

(f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g)

induce :: Ord a => (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a Source #

Construct the *induced subgraph* of a given graph by removing the
vertices that do not satisfy a given predicate.
Complexity: *O(m)* time, assuming that the predicate takes *O(1)* to
be evaluated.

induce (const True ) x == x induce (const False) x ==`empty`

induce (/= x) ==`removeVertex`

x induce p . induce q == induce (\x -> p x && q x)`isSubgraphOf`

(induce p x) x == True

# Algorithms

dfsForest :: AdjacencyMap a -> Forest a Source #

Compute the *depth-first search* forest of a graph.

`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 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 = [] }]}]

dfsForestFrom :: [a] -> AdjacencyMap a -> Forest a Source #

Compute the *depth-first search* forest of a graph, searching from each of
the given vertices in order. Note that the resulting forest does not
necessarily span the whole graph, as some vertices may be unreachable.

`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 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 = [] }]

dfs :: [a] -> AdjacencyMap a -> [a] Source #

Compute the list of vertices visited by the *depth-first search* in a graph,
when searching from each of the given vertices in order.

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

topSort :: Ord a => AdjacencyMap a -> Maybe [a] Source #

Compute the *topological sort* of a graph or return `Nothing`

if the graph
is cyclic.

```
topSort (1 * 2 + 3 * 1) == Just [3,1,2]
topSort (1 * 2 + 2 * 1) == Nothing
fmap (flip
````isTopSort`

x) (topSort x) /= Just False

scc :: Ord a => AdjacencyMap a -> AdjacencyMap (Set a) Source #

Compute the *condensation* of a graph, where each vertex corresponds to a
*strongly-connected component* of the original graph.

scc`empty`

==`empty`

scc (`vertex`

x) ==`vertex`

(Set.`singleton`

x) scc (`edge`

x y) ==`edge`

(Set.`singleton`

x) (Set.`singleton`

y) scc (`circuit`

(1:xs)) ==`edge`

(Set.`fromList`

(1:xs)) (Set.`fromList`

(1:xs)) scc (3 * 1 * 4 * 1 * 5) ==`edges`

[ (Set.`fromList`

[1,4], Set.`fromList`

[1,4]) , (Set.`fromList`

[1,4], Set.`fromList`

[5] ) , (Set.`fromList`

[3] , Set.`fromList`

[1,4]) , (Set.`fromList`

[3] , Set.`fromList`

[5] )]