Copyright | (c) Andrey Mokhov 2016-2022 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
Algebra.Graph.Relation.Symmetric
Description
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
2vertex
3 <edge
1 2vertex
1 <edge
1 1edge
1 1 <edge
1 2edge
1 2 <edge
1 1 +edge
2 2edge
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
== idfromSymmetric
. 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 .
isEmpty
empty == TruehasVertex
x empty == FalsevertexCount
empty == 0edgeCount
empty == 0
vertex :: a -> Relation a Source #
Construct the graph comprising a single isolated vertex .
isEmpty
(vertex x) == FalsehasVertex
x (vertex y) == (x == y)vertexCount
(vertex x) == 1edgeCount
(vertex x) == 0
edge :: Ord a => a -> a -> Relation a Source #
Construct the graph comprising a single edge .
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) == TrueedgeCount
(edge x y) == 1vertexCount
(edge 1 1) == 1vertexCount
(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
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 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 xisEmpty
(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
y `div` 2vertexCount
(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
x vertices ==overlays
. mapvertex
hasVertex
x . vertices ==elem
xvertexCount
. 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.
isSubgraphOfempty
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.
isEmptyempty
== 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 xempty
== 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.
vertexCountempty
== 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
edgeListempty
== [] 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
O(1)
time and memory.
relation
.
fromSymmetric
edgeSetempty
== 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 xempty
== 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
== idoverlay
(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 constant time.
mergeVertices (const
False) x == id mergeVertices (== x) y ==replaceVertex
x y mergeVerticeseven
1 (0 * 2) == 1 * 1 mergeVerticesodd
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 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 :: (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 constant time.
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 => Relation ( Maybe a) -> Relation a Source #
Construct the
induced subgraph
of a given graph by removing the vertices
that are
Nothing
.
Complexity:
O(n + m)
time.
induceJust (vertex
Nothing
) ==empty
induceJust (edge
(Just
x)Nothing
) ==vertex
x induceJust .gmap
Just
==id
induceJust .gmap
(\x -> if p x thenJust
x elseNothing
) ==induce
p
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.
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 (stars
xs) == True