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
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. 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) == TruevertexCount
(vertex x) == 1edgeCount
(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) == 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
xhasVertex
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
x) == True hasVertex 1 (vertex
2) == False 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
clique :: Ord a => [a] -> Relation a Source #
The clique on a list of vertices. Complexity: O((n + m) * log(n)) time + O(m*log(m)) time from computing the symmetricClosure and O(n + m)/ memory.
clique [] ==empty
clique [x] ==vertex
x clique [x,y] ==edge
x y clique [x,y,z] ==edges
[(x,y), (x,z), (y,z)] clique (xs ++ ys) ==connect
(clique xs) (clique ys) clique == clique .reverse
biclique :: Ord a => [a] -> [a] -> Relation a Source #
The biclique on two lists of vertices. Complexity: O(n * log(n) + m) time + O(m*log(m)) time from computing the symmetricClosure 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 yx
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 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(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