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

License | MIT (see the file LICENSE) |

Maintainer | andrey.mokhov@gmail.com |

Stability | experimental |

Safe Haskell | None |

Language | Haskell2010 |

An abstract implementation of symmetric binary relations. To avoid name clashes with Algebra.Graph.Relation, this module can be imported qualified:

import qualified Algebra.Graph.Relation.Symmetric as Symmetric

`Relation`

is an instance of the `Graph`

type
class, which can be used for polymorphic graph construction and manipulation.

## Synopsis

- data Relation a
- toSymmetric :: Ord a => Relation a -> Relation a
- fromSymmetric :: Relation a -> Relation a
- empty :: Relation a
- vertex :: a -> Relation a
- edge :: Ord a => a -> a -> Relation a
- overlay :: Ord a => Relation a -> Relation a -> Relation a
- connect :: Ord a => Relation a -> Relation a -> Relation a
- vertices :: Ord a => [a] -> Relation a
- edges :: Ord a => [(a, a)] -> Relation a
- overlays :: Ord a => [Relation a] -> Relation a
- connects :: Ord a => [Relation a] -> Relation a
- isSubgraphOf :: Ord a => Relation a -> Relation a -> Bool
- isEmpty :: Relation a -> Bool
- hasVertex :: Ord a => a -> Relation a -> Bool
- hasEdge :: Ord a => a -> a -> Relation a -> Bool
- vertexCount :: Relation a -> Int
- edgeCount :: Ord a => Relation a -> Int
- vertexList :: Relation a -> [a]
- edgeList :: Ord a => Relation a -> [(a, a)]
- adjacencyList :: Eq a => Relation a -> [(a, [a])]
- vertexSet :: Relation a -> Set a
- edgeSet :: Ord a => Relation a -> Set (a, a)
- neighbours :: Ord a => a -> Relation a -> Set a
- path :: Ord a => [a] -> Relation a
- circuit :: Ord a => [a] -> Relation a
- clique :: Ord a => [a] -> Relation a
- biclique :: Ord a => [a] -> [a] -> Relation a
- star :: Ord a => a -> [a] -> Relation a
- stars :: Ord a => [(a, [a])] -> Relation a
- tree :: Ord a => Tree a -> Relation a
- forest :: Ord a => Forest a -> Relation a
- removeVertex :: Ord a => a -> Relation a -> Relation a
- removeEdge :: Ord a => a -> a -> Relation a -> Relation a
- replaceVertex :: Ord a => a -> a -> Relation a -> Relation a
- mergeVertices :: Ord a => (a -> Bool) -> a -> Relation a -> Relation a
- gmap :: Ord b => (a -> b) -> Relation a -> Relation b
- induce :: (a -> Bool) -> Relation a -> Relation a
- induceJust :: Ord a => Relation (Maybe a) -> Relation a
- consistent :: Ord a => Relation a -> Bool

# Data structure

This data type represents a *symmetric binary relation* over a set of
elements of type `a`

. Symmetric relations satisfy all laws of the
`Undirected`

type class, including the commutativity of
`connect`

:

`connect`

x y ==`connect`

y x

The `Show`

instance lists edge vertices in non-decreasing order:

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

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`

2 1 <`edge`

1 3

`edge`

1 2 ==`edge`

2 1

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

toSymmetric :: Ord a => Relation a -> Relation a Source #

Construct a symmetric relation from a given Algebra.Graph.Relation.
Complexity: *O(m*log(m))* time.

toSymmetric (`edge`

1 2) ==`edge`

1 2 toSymmetric .`fromSymmetric`

== id`fromSymmetric`

. toSymmetric ==`symmetricClosure`

`vertexCount`

. toSymmetric ==`vertexCount`

(*2) .`edgeCount`

. toSymmetric >=`edgeCount`

fromSymmetric :: Relation a -> Relation a Source #

Extract the underlying symmetric Algebra.Graph.Relation.
Complexity: *O(1)* time and memory.

fromSymmetric (`edge`

1 2) ==`edges`

[(1,2), (2,1)]`vertexCount`

. fromSymmetric ==`vertexCount`

`edgeCount`

. fromSymmetric <= (*2) .`edgeCount`

# Basic graph construction primitives

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 -> Relation 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 -> Relation a Source #

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

edge x y ==`connect`

(`vertex`

x) (`vertex`

y) edge x y ==`edge`

y x edge x y ==`edges`

[(x,y), (y,x)]`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 => Relation a -> Relation a -> Relation 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 => Relation a -> Relation a -> Relation a Source #

*Connect* two graphs. This is a commutative and 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)*.

connect x y == connect y x`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 `div` 2`vertexCount`

(connect 1 2) == 2`edgeCount`

(connect 1 2) == 1

vertices :: Ord a => [a] -> Relation 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`

# Relations on graphs

isSubgraphOf :: Ord a => Relation a -> Relation 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 (`edge`

x y) (`edge`

y x) == True isSubgraphOf x y ==> x <= y

# Graph properties

isEmpty :: Relation a -> Bool Source #

Check if a relation 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 -> Relation 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 :: Relation 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

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

edgeList :: Ord a => Relation a -> [(a, a)] Source #

The sorted list of edges of a graph, where edge vertices appear in the
non-decreasing order.
Complexity: *O(n + m)* time and *O(m)* memory.

Note: If you need the sorted list of edges where an edge appears in both
directions, use

.`edgeList`

. `fromSymmetric`

edgeList`empty`

== [] edgeList (`vertex`

x) == [] edgeList (`edge`

x y) == [(`min`

x y,`max`

y x)] edgeList (`star`

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

adjacencyList :: Eq a => Relation a -> [(a, [a])] Source #

edgeSet :: Ord a => Relation a -> Set (a, a) Source #

The set of edges of a given graph, where edge vertices appear in the
non-decreasing order.
Complexity: *O(m)* time.

Note: If you need the set of edges where an edge appears in both directions,
use

. The latter is much
faster than this function, and takes only `relation`

. `fromSymmetric`

*O(1)* time and memory.

edgeSet`empty`

== Set.`empty`

edgeSet (`vertex`

x) == Set.`empty`

edgeSet (`edge`

x y) == Set.`singleton`

(`min`

x y,`max`

x y)

neighbours :: Ord a => a -> Relation a -> Set a Source #

The set of *neighbours* of an element `x`

is the set of elements that are
related to it, i.e. `neighbours x == { a | aRx }`

. In the context of undirected
graphs, this corresponds to the set of *adjacent* vertices of vertex `x`

.

neighbours x`empty`

== Set.`empty`

neighbours x (`vertex`

x) == Set.`empty`

neighbours x (`edge`

x y) == Set.`fromList`

[y] neighbours y (`edge`

x y) == Set.`fromList`

[x]

# Standard families of graphs

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

The *biclique* on two lists of vertices.
Complexity: *O((n + m) * log(n))* time and *O(n + m)* memory.

biclique [] [] ==`empty`

biclique [x] [] ==`vertex`

x biclique [] [y] ==`vertex`

y biclique [x1,x2] [y1,y2] ==`edges`

[(x1,y1), (x1,y2), (x2,x2), (x2,y2)] biclique xs ys ==`connect`

(`vertices`

xs) (`vertices`

ys)

stars :: Ord a => [(a, [a])] -> Relation 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)

tree :: Ord a => Tree a -> Relation 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

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

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

removeEdge x y (`edge`

x y) ==`vertices`

[x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y == removeEdge y x 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 -> Relation a -> Relation a Source #

The function

replaces vertex `replaceVertex`

x y`x`

with vertex `y`

in a
given `Relation`

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

gmap :: Ord b => (a -> b) -> Relation a -> Relation 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
`Relation`

.
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) -> Relation a -> Relation 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

# Miscellaneous

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

Check that the internal representation of a symmetric relation is
consistent, i.e. that (i) that all edges refer to existing vertices, and (ii)
all edges have their symmetric counterparts. It should be impossible to
create an inconsistent `Relation`

, 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