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

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 and associated functions.
See Algebra.Graph.AdjacencyMap.Algorithm for implementations of basic graph
algorithms. `AdjacencyMap`

is an instance of the `Graph`

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

vertices.

## Synopsis

- data AdjacencyMap a
- adjacencyMap :: AdjacencyMap a -> Map a (Set a)
- empty :: AdjacencyMap a
- vertex :: 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
- 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 :: Eq a => AdjacencyMap a -> Set (a, a)
- preSet :: Ord a => a -> AdjacencyMap a -> Set 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
- stars :: Ord a => [(a, [a])] -> AdjacencyMap a
- fromAdjacencySets :: Ord a => [(a, Set 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 :: (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a
- induceJust :: Ord a => AdjacencyMap (Maybe a) -> AdjacencyMap a
- compose :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a
- box :: (Ord a, Ord b) => AdjacencyMap a -> AdjacencyMap b -> AdjacencyMap (a, b)
- closure :: Ord a => AdjacencyMap a -> AdjacencyMap a
- reflexiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a
- symmetricClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a
- transitiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a
- consistent :: Ord a => AdjacencyMap a -> Bool

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

**Note:** the `Num`

instance does not satisfy several "customary laws" of `Num`

,
which dictate that `fromInteger`

`0`

and `fromInteger`

`1`

should act as
additive and multiplicative identities, and `negate`

as additive inverse.
Nevertheless, overloading `fromInteger`

, `+`

and `*`

is very convenient when
working with algebraic graphs; we hope that in future Haskell's Prelude will
provide a more fine-grained class hierarchy for algebraic structures, which we
would be able to utilise without violating any laws.

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.

The total order on graphs is defined using *size-lexicographic* comparison:

- Compare the number of vertices. In case of a tie, continue.
- Compare the sets of vertices. In case of a tie, continue.
- Compare the number of edges. In case of a tie, continue.
- Compare the sets of edges.

Here are a few examples:

`vertex`

1 <`vertex`

2`vertex`

3 <`edge`

1 2`vertex`

1 <`edge`

1 1`edge`

1 1 <`edge`

1 2`edge`

1 2 <`edge`

1 1 +`edge`

2 2`edge`

1 2 <`edge`

1 3

Note that the resulting order refines the `isSubgraphOf`

relation and is
compatible with `overlay`

and `connect`

operations:

`isSubgraphOf`

x y ==> x <= y

`empty`

<= x
x <= x + y
x + y <= x * y

## Instances

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

The *adjacency map* of a graph: each vertex is associated with a set of
its direct successors. Complexity: *O(1)* time and memory.

adjacencyMap`empty`

== Map.`empty`

adjacencyMap (`vertex`

x) == Map.`singleton`

x Set.`empty`

adjacencyMap (`edge`

1 1) == Map.`singleton`

1 (Set.`singleton`

1) adjacencyMap (`edge`

1 2) == Map.`fromList`

[(1,Set.`singleton`

2), (2,Set.`empty`

)]

# Basic graph construction primitives

empty :: 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 :: 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 y) == (x == y)`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 #

# 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 isSubgraphOf x y ==> x <= y

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

y) == (x == y) 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`

vertexCount x < vertexCount y ==> x < y

edgeCount :: AdjacencyMap a -> Int Source #

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

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

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

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 #

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

The *stars* formed by overlaying a list of `star`

s. An inverse of
`adjacencyList`

.
Complexity: *O(L * log(n))* time, memory and size, where *L* is the total
size of the input.

stars [] ==`empty`

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

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

x y stars [(x, ys)] ==`star`

x ys stars ==`overlays`

.`map`

(`uncurry`

`star`

) stars .`adjacencyList`

== id`overlay`

(stars xs) (stars ys) == stars (xs`++`

ys)

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

Construct a graph from a list of adjacency sets; a variation of `stars`

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

fromAdjacencySets [] ==`empty`

fromAdjacencySets [(x, Set.`empty`

)] ==`vertex`

x fromAdjacencySets [(x, Set.`singleton`

y)] ==`edge`

x y fromAdjacencySets .`map`

(`fmap`

Set.`fromList`

) ==`stars`

`overlay`

(fromAdjacencySets xs) (fromAdjacencySets ys) == fromAdjacencySets (xs`++`

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 :: (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(n + 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

induceJust :: Ord a => AdjacencyMap (Maybe a) -> AdjacencyMap a Source #

# Graph composition

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

Left-to-right *relational composition* of graphs: vertices `x`

and `z`

are
connected in the resulting graph if there is a vertex `y`

, such that `x`

is
connected to `y`

in the first graph, and `y`

is connected to `z`

in the
second graph. There are no isolated vertices in the result. This operation is
associative, has `empty`

and single-`vertex`

graphs as *annihilating zeroes*,
and distributes over `overlay`

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

compose`empty`

x ==`empty`

compose x`empty`

==`empty`

compose (`vertex`

x) y ==`empty`

compose x (`vertex`

y) ==`empty`

compose x (compose y z) == compose (compose x y) z compose x (`overlay`

y z) ==`overlay`

(compose x y) (compose x z) compose (`overlay`

x y) z ==`overlay`

(compose x z) (compose y z) compose (`edge`

x y) (`edge`

y z) ==`edge`

x z compose (`path`

[1..5]) (`path`

[1..5]) ==`edges`

[(1,3), (2,4), (3,5)] compose (`circuit`

[1..5]) (`circuit`

[1..5]) ==`circuit`

[1,3,5,2,4]

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

Compute the *Cartesian product* of graphs.
Complexity: *O(n * m * log(n)^2)* time.

box (`path`

[0,1]) (`path`

"ab") ==`edges`

[ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ]

Up to an isomorphism between the resulting vertex types, this operation
is *commutative*, *associative*, *distributes* over `overlay`

, has singleton
graphs as *identities* and `empty`

as the *annihilating zero*. Below `~~`

stands for the equality up to an isomorphism, e.g. `(x, ()) ~~ x`

.

box x y ~~ box y x box x (box y z) ~~ box (box x y) z box x (`overlay`

y z) ==`overlay`

(box x y) (box x z) box x (`vertex`

()) ~~ x box x`empty`

~~`empty`

`transpose`

(box x y) == box (`transpose`

x) (`transpose`

y)`vertexCount`

(box x y) ==`vertexCount`

x *`vertexCount`

y`edgeCount`

(box x y) <=`vertexCount`

x *`edgeCount`

y +`edgeCount`

x *`vertexCount`

y

# Relational operations

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

Compute the *reflexive and transitive closure* of a graph.
Complexity: *O(n * m * log(n)^2)* time.

closure`empty`

==`empty`

closure (`vertex`

x) ==`edge`

x x closure (`edge`

x x) ==`edge`

x x closure (`edge`

x y) ==`edges`

[(x,x), (x,y), (y,y)] closure (`path`

$`nub`

xs) ==`reflexiveClosure`

(`clique`

$`nub`

xs) closure ==`reflexiveClosure`

.`transitiveClosure`

closure ==`transitiveClosure`

.`reflexiveClosure`

closure . closure == closure`postSet`

x (closure y) == Set.`fromList`

(`reachable`

x y)

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

Compute the *reflexive closure* of a graph by adding a self-loop to every
vertex.
Complexity: *O(n * log(n))* time.

reflexiveClosure`empty`

==`empty`

reflexiveClosure (`vertex`

x) ==`edge`

x x reflexiveClosure (`edge`

x x) ==`edge`

x x reflexiveClosure (`edge`

x y) ==`edges`

[(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure

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

Compute the *symmetric closure* of a graph by overlaying it with its own
transpose.
Complexity: *O((n + m) * log(n))* time.

symmetricClosure`empty`

==`empty`

symmetricClosure (`vertex`

x) ==`vertex`

x symmetricClosure (`edge`

x y) ==`edges`

[(x,y), (y,x)] symmetricClosure x ==`overlay`

x (`transpose`

x) symmetricClosure . symmetricClosure == symmetricClosure

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

Compute the *transitive closure* of a graph.
Complexity: *O(n * m * log(n)^2)* time.

transitiveClosure`empty`

==`empty`

transitiveClosure (`vertex`

x) ==`vertex`

x transitiveClosure (`edge`

x y) ==`edge`

x y transitiveClosure (`path`

$`nub`

xs) ==`clique`

(`nub`

xs) transitiveClosure . transitiveClosure == transitiveClosure

# Miscellaneous

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

Check that the internal graph representation is consistent, i.e. that all edges refer to existing vertices. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.

consistent`empty`

== True consistent (`vertex`

x) == True consistent (`overlay`

x y) == True consistent (`connect`

x y) == True consistent (`edge`

x y) == True consistent (`edges`

xs) == True consistent (`stars`

xs) == True