Copyright | (c) Andrey Mokhov 2016-2017 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | unstable |
Safe Haskell | None |
Language | Haskell2010 |
This module exposes the implementation of binary relations. The API is unstable and unsafe. Where possible use non-internal modules Algebra.Graph.Relation, Algebra.Graph.Relation.Reflexive, Algebra.Graph.Relation.Symmetric, Algebra.Graph.Relation.Transitive and Algebra.Graph.Relation.Preorder instead.
- data Relation a = Relation {}
- consistent :: Ord a => Relation a -> Bool
- empty :: Relation a
- vertex :: 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
- fromAdjacencyList :: Ord a => [(a, [a])] -> Relation a
- edgeList :: Ord a => Relation a -> [(a, a)]
- preset :: Ord a => a -> Relation a -> Set a
- postset :: Ord a => a -> Relation a -> Set a
- removeVertex :: Ord a => a -> Relation a -> Relation a
- removeEdge :: Ord a => a -> a -> Relation a -> Relation a
- gmap :: (Ord a, Ord b) => (a -> b) -> Relation a -> Relation b
- induce :: Ord a => (a -> Bool) -> Relation a -> Relation a
- reflexiveClosure :: Ord a => Relation a -> Relation a
- symmetricClosure :: Ord a => Relation a -> Relation a
- transitiveClosure :: Ord a => Relation a -> Relation a
- preorderClosure :: Ord a => Relation a -> Relation a
- newtype ReflexiveRelation a = ReflexiveRelation {
- fromReflexive :: Relation a
- newtype SymmetricRelation a = SymmetricRelation {
- fromSymmetric :: Relation a
- newtype TransitiveRelation a = TransitiveRelation {
- fromTransitive :: Relation a
- newtype PreorderRelation a = PreorderRelation {
- fromPreorder :: Relation a
Data structure
The Relation
data type represents a graph as a binary relation. We define
a law-abiding 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
:: 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 (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: Relation Int) == "graph [1,2,3] [(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 hasempty
as the identity:x * empty == x empty * x == x x * (y * z) == (x * y) * z
connect
distributes overoverlay
: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
hasempty
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.
consistent :: Ord a => Relation a -> Bool Source #
Check if the internal representation of a relation is consistent, i.e. if all
pairs of elements in the relation
refer to existing elements in the domain
.
It should be impossible to create an inconsistent Relation
, and we use this
function in testing.
consistentempty
== 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 (graph
xs ys) == True consistent (fromAdjacencyList
xs) == True
Basic graph construction primitives
Construct the empty graph. Complexity: O(1) time and memory.
isEmpty
empty == TruehasVertex
x empty == FalsevertexCount
empty == 0edgeCount
empty == 0
vertex :: a -> Relation a Source #
Construct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.
isEmpty
(vertex x) == FalsehasVertex
x (vertex x) == TruehasVertex
1 (vertex 2) == FalsevertexCount
(vertex x) == 1edgeCount
(vertex x) == 0
overlay :: Ord a => Relation a -> Relation a -> Relation a Source #
Overlay two graphs. This is an idempotent, commutative and associative
operation with the identity empty
.
Complexity: O((n + m) * log(n)) time and O(n + m) memory.
isEmpty
(overlay x y) ==isEmpty
x &&isEmpty
yhasVertex
z (overlay x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(overlay x y) >=vertexCount
xvertexCount
(overlay x y) <=vertexCount
x +vertexCount
yedgeCount
(overlay x y) >=edgeCount
xedgeCount
(overlay x y) <=edgeCount
x +edgeCount
yvertexCount
(overlay 1 2) == 2edgeCount
(overlay 1 2) == 0
connect :: Ord a => Relation a -> Relation a -> Relation a Source #
Connect two graphs. This is an associative operation with the identity
empty
, which distributes over the 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
yhasVertex
z (connect x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(connect x y) >=vertexCount
xvertexCount
(connect x y) <=vertexCount
x +vertexCount
yedgeCount
(connect x y) >=edgeCount
xedgeCount
(connect x y) >=edgeCount
yedgeCount
(connect x y) >=vertexCount
x *vertexCount
yedgeCount
(connect x y) <=vertexCount
x *vertexCount
y +edgeCount
x +edgeCount
yvertexCount
(connect 1 2) == 2edgeCount
(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
xhasVertex
x . vertices ==elem
xvertexCount
. vertices ==length
.nub
vertexSet
. vertices == Set.fromList
fromAdjacencyList :: Ord a => [(a, [a])] -> Relation a Source #
Graph properties
preset :: Ord a => a -> Relation a -> Set a Source #
The preset of an element x
is the set of elements that are related to
it on the left, i.e. preset x == { a | aRx }
. In the context of directed
graphs, this corresponds to the set of direct predecessors of vertex x
.
Complexity: O(n + m) time and O(n) memory.
preset xempty
== Set.empty preset x (vertex
x) == Set.empty preset 1 (edge
1 2) == Set.empty preset y (edge
x y) == Set.fromList [x]
postset :: Ord a => a -> Relation a -> Set a Source #
The postset of an element x
is the set of elements that are related to
it on the right, i.e. postset x == { a | xRa }
. In the context of directed
graphs, this corresponds to the set of direct successors of vertex x
.
Complexity: O(n + m) time and O(n) memory.
postset xempty
== Set.empty postset x (vertex
x) == Set.empty postset x (edge
x y) == Set.fromList [y] postset 2 (edge
1 2) == Set.empty
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 .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
gmap :: (Ord a, 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 fempty
==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) -> 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(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
Operations on binary relations
Reflexive relations
newtype ReflexiveRelation a Source #
The ReflexiveRelation
data type represents a reflexive binary relation
over a set of elements. Reflexive relations satisfy all laws of the
Reflexive
type class and, in particular, the self-loop axiom:
vertex
x ==vertex
x *vertex
x
The Show
instance produces reflexively closed expressions:
show (1 :: ReflexiveRelation Int) == "edge 1 1" show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"
Symmetric relations
newtype SymmetricRelation a Source #
The SymmetricRelation
data type represents a symmetric binary relation
over a set of elements. Symmetric relations satisfy all laws of the
Undirected
type class and, in particular, the
commutativity of connect:
connect
x y ==connect
y x
The Show
instance produces symmetrically closed expressions:
show (1 :: SymmetricRelation Int) == "vertex 1" show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"
Ord a => Eq (SymmetricRelation a) Source # | |
(Num a, Ord a) => Num (SymmetricRelation a) Source # | |
(Ord a, Show a) => Show (SymmetricRelation a) Source # | |
Ord a => Undirected (SymmetricRelation a) Source # | |
Ord a => Graph (SymmetricRelation a) Source # | |
type Vertex (SymmetricRelation a) Source # | |
Transitive relations
newtype TransitiveRelation a Source #
The TransitiveRelation
data type represents a transitive binary relation
over a set of elements. Transitive relations satisfy all laws of the
Transitive
type class and, in particular, the closure axiom:
y /= empty
==> x * y + x * z + y * z == x * y + y * z
For example, the following holds:
path
xs ==clique
xs
The Show
instance produces transitively closed expressions:
show (1 * 2 :: TransitiveRelation Int) == "edge 1 2" show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"
Ord a => Eq (TransitiveRelation a) Source # | |
(Num a, Ord a) => Num (TransitiveRelation a) Source # | |
(Ord a, Show a) => Show (TransitiveRelation a) Source # | |
Ord a => Transitive (TransitiveRelation a) Source # | |
Ord a => Graph (TransitiveRelation a) Source # | |
type Vertex (TransitiveRelation a) Source # | |
Preorders
newtype PreorderRelation a Source #
The PreorderRelation
data type represents a binary relation over a set of
elements that is both transitive and reflexive. Preorders satisfy all laws of the
Preorder
type class and, in particular, the closure
axiom:
y /= empty
==> x * y + x * z + y * z == x * y + y * z
and the self-loop axiom:
vertex
x ==vertex
x *vertex
x
For example, the following holds:
path
xs ==clique
xs
The Show
instance produces reflexively and transitively closed expressions:
show (1 :: PreorderRelation Int) == "edge 1 1" show (1 * 2 :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]" show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"
Ord a => Eq (PreorderRelation a) Source # | |
(Num a, Ord a) => Num (PreorderRelation a) Source # | |
(Ord a, Show a) => Show (PreorderRelation a) Source # | |
Ord a => Preorder (PreorderRelation a) Source # | |
Ord a => Transitive (PreorderRelation a) Source # | |
Ord a => Reflexive (PreorderRelation a) Source # | |
Ord a => Graph (PreorderRelation a) Source # | |
type Vertex (PreorderRelation a) Source # | |