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

data type and associated functions.
See Algebra.Graph.AdjacencyIntMap.Algorithm for implementations of basic
graph algorithms. `AdjacencyIntMap`

is an instance of the `Graph`

type
class, which can be used for polymorphic graph construction and manipulation.
See Algebra.Graph.AdjacencyMap for graphs with non-`Int`

vertices.

## Synopsis

- data AdjacencyIntMap
- adjacencyIntMap :: AdjacencyIntMap -> IntMap IntSet
- fromAdjacencyMap :: AdjacencyMap Int -> AdjacencyIntMap
- empty :: AdjacencyIntMap
- vertex :: Int -> AdjacencyIntMap
- edge :: Int -> Int -> AdjacencyIntMap
- overlay :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
- connect :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
- vertices :: [Int] -> AdjacencyIntMap
- edges :: [(Int, Int)] -> AdjacencyIntMap
- overlays :: [AdjacencyIntMap] -> AdjacencyIntMap
- connects :: [AdjacencyIntMap] -> AdjacencyIntMap
- isSubgraphOf :: AdjacencyIntMap -> AdjacencyIntMap -> Bool
- isEmpty :: AdjacencyIntMap -> Bool
- hasVertex :: Int -> AdjacencyIntMap -> Bool
- hasEdge :: Int -> Int -> AdjacencyIntMap -> Bool
- vertexCount :: AdjacencyIntMap -> Int
- edgeCount :: AdjacencyIntMap -> Int
- vertexList :: AdjacencyIntMap -> [Int]
- edgeList :: AdjacencyIntMap -> [(Int, Int)]
- adjacencyList :: AdjacencyIntMap -> [(Int, [Int])]
- vertexIntSet :: AdjacencyIntMap -> IntSet
- edgeSet :: AdjacencyIntMap -> Set (Int, Int)
- preIntSet :: Int -> AdjacencyIntMap -> IntSet
- postIntSet :: Int -> AdjacencyIntMap -> IntSet
- path :: [Int] -> AdjacencyIntMap
- circuit :: [Int] -> AdjacencyIntMap
- clique :: [Int] -> AdjacencyIntMap
- biclique :: [Int] -> [Int] -> AdjacencyIntMap
- star :: Int -> [Int] -> AdjacencyIntMap
- stars :: [(Int, [Int])] -> AdjacencyIntMap
- fromAdjacencyIntSets :: [(Int, IntSet)] -> AdjacencyIntMap
- tree :: Tree Int -> AdjacencyIntMap
- forest :: Forest Int -> AdjacencyIntMap
- removeVertex :: Int -> AdjacencyIntMap -> AdjacencyIntMap
- removeEdge :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap
- replaceVertex :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap
- mergeVertices :: (Int -> Bool) -> Int -> AdjacencyIntMap -> AdjacencyIntMap
- transpose :: AdjacencyIntMap -> AdjacencyIntMap
- gmap :: (Int -> Int) -> AdjacencyIntMap -> AdjacencyIntMap
- induce :: (Int -> Bool) -> AdjacencyIntMap -> AdjacencyIntMap
- compose :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap
- closure :: AdjacencyIntMap -> AdjacencyIntMap
- reflexiveClosure :: AdjacencyIntMap -> AdjacencyIntMap
- symmetricClosure :: AdjacencyIntMap -> AdjacencyIntMap
- transitiveClosure :: AdjacencyIntMap -> AdjacencyIntMap
- consistent :: AdjacencyIntMap -> Bool

# Data structure

data AdjacencyIntMap Source #

The `AdjacencyIntMap`

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 :: AdjacencyIntMap Int) == "empty" show (1 :: AdjacencyIntMap Int) == "vertex 1" show (1 + 2 :: AdjacencyIntMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyIntMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyIntMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyIntMap 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

adjacencyIntMap :: AdjacencyIntMap -> IntMap IntSet Source #

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

adjacencyIntMap`empty`

== IntMap.`empty`

adjacencyIntMap (`vertex`

x) == IntMap.`singleton`

x IntSet.`empty`

adjacencyIntMap (`edge`

1 1) == IntMap.`singleton`

1 (IntSet.`singleton`

1) adjacencyIntMap (`edge`

1 2) == IntMap.`fromList`

[(1,IntSet.`singleton`

2), (2,IntSet.`empty`

)]

fromAdjacencyMap :: AdjacencyMap Int -> AdjacencyIntMap Source #

Construct an `AdjacencyIntMap`

from an `AdjacencyMap`

with vertices of
type `Int`

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

fromAdjacencyMap ==`stars`

. AdjacencyMap.`adjacencyList`

# Basic graph construction primitives

empty :: AdjacencyIntMap 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 :: Int -> AdjacencyIntMap 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 :: Int -> Int -> AdjacencyIntMap 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 :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap 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 :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap 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 :: [Int] -> AdjacencyIntMap 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`

`vertexIntSet`

. vertices == IntSet.`fromList`

overlays :: [AdjacencyIntMap] -> AdjacencyIntMap Source #

connects :: [AdjacencyIntMap] -> AdjacencyIntMap Source #

# Relations on graphs

isSubgraphOf :: AdjacencyIntMap -> AdjacencyIntMap -> 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 :: AdjacencyIntMap -> 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 :: Int -> AdjacencyIntMap -> 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 :: AdjacencyIntMap -> 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 :: AdjacencyIntMap -> Int Source #

vertexList :: AdjacencyIntMap -> [Int] Source #

adjacencyList :: AdjacencyIntMap -> [(Int, [Int])] Source #

vertexIntSet :: AdjacencyIntMap -> IntSet Source #

postIntSet :: Int -> AdjacencyIntMap -> IntSet Source #

# Standard families of graphs

path :: [Int] -> AdjacencyIntMap Source #

circuit :: [Int] -> AdjacencyIntMap Source #

clique :: [Int] -> AdjacencyIntMap Source #

stars :: [(Int, [Int])] -> AdjacencyIntMap 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)

fromAdjacencyIntSets :: [(Int, IntSet)] -> AdjacencyIntMap 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.

fromAdjacencyIntSets [] ==`empty`

fromAdjacencyIntSets [(x, IntSet.`empty`

)] ==`vertex`

x fromAdjacencyIntSets [(x, IntSet.`singleton`

y)] ==`edge`

x y fromAdjacencyIntSets .`map`

(`fmap`

IntSet.`fromList`

) ==`stars`

`overlay`

(fromAdjacencyIntSets xs) (fromAdjacencyIntSets ys) == fromAdjacencyIntSets (xs ++ ys)

tree :: Tree Int -> AdjacencyIntMap 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 :: Int -> AdjacencyIntMap -> AdjacencyIntMap Source #

removeEdge :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap 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 :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap Source #

The function

replaces vertex `replaceVertex`

x y`x`

with vertex `y`

in a
given `AdjacencyIntMap`

. 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 :: (Int -> Bool) -> Int -> AdjacencyIntMap -> AdjacencyIntMap 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

gmap :: (Int -> Int) -> AdjacencyIntMap -> AdjacencyIntMap 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
`AdjacencyIntMap`

.
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 :: (Int -> Bool) -> AdjacencyIntMap -> AdjacencyIntMap 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

# Relational operations

compose :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap 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]

closure :: AdjacencyIntMap -> AdjacencyIntMap 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`postIntSet`

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

(`reachable`

x y)

reflexiveClosure :: AdjacencyIntMap -> AdjacencyIntMap 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 :: AdjacencyIntMap -> AdjacencyIntMap 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 :: AdjacencyIntMap -> AdjacencyIntMap 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 :: AdjacencyIntMap -> 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