Copyright | (c) Andrey Mokhov 2016-2022 |
---|---|
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 AdjacencyMap
data type for undirected bipartite
graphs and associated functions. See
Algebra.Graph.Bipartite.AdjacencyMap.Algorithm for basic bipartite graph
algorithms.
To avoid name clashes with Algebra.Graph.AdjacencyMap, this module can be imported qualified:
import qualified Algebra.Graph.Bipartite.AdjacencyMap as Bipartite
Synopsis
- data AdjacencyMap a b
- leftAdjacencyMap :: AdjacencyMap a b -> Map a (Set b)
- rightAdjacencyMap :: AdjacencyMap a b -> Map b (Set a)
- empty :: AdjacencyMap a b
- leftVertex :: a -> AdjacencyMap a b
- rightVertex :: b -> AdjacencyMap a b
- vertex :: Either a b -> AdjacencyMap a b
- edge :: a -> b -> AdjacencyMap a b
- overlay :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b
- connect :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b
- vertices :: (Ord a, Ord b) => [a] -> [b] -> AdjacencyMap a b
- edges :: (Ord a, Ord b) => [(a, b)] -> AdjacencyMap a b
- overlays :: (Ord a, Ord b) => [AdjacencyMap a b] -> AdjacencyMap a b
- connects :: (Ord a, Ord b) => [AdjacencyMap a b] -> AdjacencyMap a b
- swap :: AdjacencyMap a b -> AdjacencyMap b a
- toBipartite :: (Ord a, Ord b) => AdjacencyMap (Either a b) -> AdjacencyMap a b
- toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c) -> AdjacencyMap a -> AdjacencyMap b c
- fromBipartite :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap (Either a b)
- fromBipartiteWith :: Ord c => (a -> c) -> (b -> c) -> AdjacencyMap a b -> AdjacencyMap c
- isEmpty :: AdjacencyMap a b -> Bool
- hasLeftVertex :: Ord a => a -> AdjacencyMap a b -> Bool
- hasRightVertex :: Ord b => b -> AdjacencyMap a b -> Bool
- hasVertex :: (Ord a, Ord b) => Either a b -> AdjacencyMap a b -> Bool
- hasEdge :: (Ord a, Ord b) => a -> b -> AdjacencyMap a b -> Bool
- leftVertexCount :: AdjacencyMap a b -> Int
- rightVertexCount :: AdjacencyMap a b -> Int
- vertexCount :: AdjacencyMap a b -> Int
- edgeCount :: AdjacencyMap a b -> Int
- leftVertexList :: AdjacencyMap a b -> [a]
- rightVertexList :: AdjacencyMap a b -> [b]
- vertexList :: AdjacencyMap a b -> [Either a b]
- edgeList :: AdjacencyMap a b -> [(a, b)]
- leftVertexSet :: AdjacencyMap a b -> Set a
- rightVertexSet :: AdjacencyMap a b -> Set b
- vertexSet :: (Ord a, Ord b) => AdjacencyMap a b -> Set (Either a b)
- edgeSet :: (Ord a, Ord b) => AdjacencyMap a b -> Set (a, b)
- leftAdjacencyList :: AdjacencyMap a b -> [(a, [b])]
- rightAdjacencyList :: AdjacencyMap a b -> [(b, [a])]
- data List a b
- evenList :: [(a, b)] -> List a b
- oddList :: a -> [(b, a)] -> List a b
- path :: (Ord a, Ord b) => List a b -> AdjacencyMap a b
- circuit :: (Ord a, Ord b) => [(a, b)] -> AdjacencyMap a b
- biclique :: (Ord a, Ord b) => [a] -> [b] -> AdjacencyMap a b
- star :: (Ord a, Ord b) => a -> [b] -> AdjacencyMap a b
- stars :: (Ord a, Ord b) => [(a, [b])] -> AdjacencyMap a b
- mesh :: (Ord a, Ord b) => [a] -> [b] -> AdjacencyMap (a, b) (a, b)
- removeLeftVertex :: Ord a => a -> AdjacencyMap a b -> AdjacencyMap a b
- removeRightVertex :: Ord b => b -> AdjacencyMap a b -> AdjacencyMap a b
- removeEdge :: (Ord a, Ord b) => a -> b -> AdjacencyMap a b -> AdjacencyMap a b
- bimap :: (Ord a, Ord b, Ord c, Ord d) => (a -> c) -> (b -> d) -> AdjacencyMap a b -> AdjacencyMap c d
- box :: (Ord a, Ord b) => AdjacencyMap a a -> AdjacencyMap b b -> AdjacencyMap (a, b) (a, b)
- boxWith :: (Ord a, Ord b, Ord c, Ord d, Ord e, Ord f) => (a -> c -> e) -> (b -> d -> e) -> (a -> d -> f) -> (b -> c -> f) -> AdjacencyMap a b -> AdjacencyMap c d -> AdjacencyMap e f
- consistent :: (Ord a, Ord b) => AdjacencyMap a b -> Bool
Data structure
data AdjacencyMap a b Source #
The AdjacencyMap
data type represents an undirected bipartite
graph. The two type parameters determine the types of vertices of each part. If
the types coincide, the vertices of the left part are still treated as disjoint
from the vertices of the right part. See examples for more details.
We define a Num
instance as a convenient notation for working with bipartite
graphs:
0 ==rightVertex
0swap
1 ==leftVertex
1swap
1 + 2 ==vertices
[1] [2]swap
1 * 2 ==edge
1 2swap
1 + 2 *swap
3 ==overlay
(leftVertex
1) (edge
3 2)swap
1 * (2 +swap
3) ==connect
(leftVertex
1) (vertices
[3] [2])
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 == "empty" show 1 == "rightVertex 1" show (swap
2) == "leftVertex 2" show (1 + 2) == "vertices [] [1,2]" show (swap
(1 + 2)) == "vertices [1,2] []" show (swap
1 * 2) == "edge 1 2" show (swap
1 * 2 *swap
3) == "edges [(1,2),(3,2)]" show (swap
1 * 2 +swap
3) == "overlay (leftVertex 3) (edge 1 2)"
The Eq
instance satisfies all axioms of undirected bipartite algebraic graphs:
overlay
is commutative and associative:x + y == y + x x + (y + z) == (x + y) + z
connect
is commutative, associative and hasempty
as the identity:x * empty == x empty * x == x x * y == y * 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
connect
has the same effect asoverlay
on vertices of the same part:leftVertex x * leftVertex y == leftVertex x + leftVertex y rightVertex x * rightVertex y == rightVertex x + rightVertex y
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 of the graph, respectively. In addition, l and r will denote the number of vertices in the left and right parts of the graph, respectively.
Instances
leftAdjacencyMap :: AdjacencyMap a b -> Map a (Set b) Source #
The adjacency map of the left part of the graph: each left vertex is associated with a set of its right neighbours. Complexity: O(1) time and memory.
leftAdjacencyMapempty
== Map.empty
leftAdjacencyMap (leftVertex
x) == Map.singleton
x Set.empty
leftAdjacencyMap (rightVertex
x) == Map.empty
leftAdjacencyMap (edge
x y) == Map.singleton
x (Set.singleton
y)
rightAdjacencyMap :: AdjacencyMap a b -> Map b (Set a) Source #
The adjacency map of the right part of the graph: each right vertex is associated with a set of its left neighbours. Complexity: O(1) time and memory.
rightAdjacencyMapempty
== Map.empty
rightAdjacencyMap (leftVertex
x) == Map.empty
rightAdjacencyMap (rightVertex
x) == Map.singleton
x Set.empty
rightAdjacencyMap (edge
x y) == Map.singleton
y (Set.singleton
x)
Basic graph construction primitives
empty :: AdjacencyMap a b Source #
Construct the empty graph.
isEmpty
empty == TrueleftAdjacencyMap
empty == Map.empty
rightAdjacencyMap
empty == Map.empty
hasVertex
x empty == False
leftVertex :: a -> AdjacencyMap a b Source #
Construct the graph comprising a single isolated vertex in the left part.
leftAdjacencyMap
(leftVertex x) == Map.singleton
x Set.empty
rightAdjacencyMap
(leftVertex x) == Map.empty
hasLeftVertex
x (leftVertex y) == (x == y)hasRightVertex
x (leftVertex y) == FalsehasEdge
x y (leftVertex z) == False
rightVertex :: b -> AdjacencyMap a b Source #
Construct the graph comprising a single isolated vertex in the right part.
leftAdjacencyMap
(rightVertex x) == Map.empty
rightAdjacencyMap
(rightVertex x) == Map.singleton
x Set.empty
hasLeftVertex
x (rightVertex y) == FalsehasRightVertex
x (rightVertex y) == (x == y)hasEdge
x y (rightVertex z) == False
vertex :: Either a b -> AdjacencyMap a b Source #
Construct the graph comprising a single isolated vertex.
vertex . Left ==leftVertex
vertex . Right ==rightVertex
edge :: a -> b -> AdjacencyMap a b Source #
Construct the graph comprising a single edge.
edge x y ==connect
(leftVertex
x) (rightVertex
y)leftAdjacencyMap
(edge x y) == Map.singleton
x (Set.singleton
y)rightAdjacencyMap
(edge x y) == Map.singleton
y (Set.singleton
x)hasEdge
x y (edge x y) == TruehasEdge
1 2 (edge 2 1) == False
overlay :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b 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
y
connect :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b Source #
Connect two graphs, filtering out the edges between vertices of the same
part. 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 in the arguments: O(m1 + m2 + l1 * r2 + l2 * r1).
connect (leftVertex
x) (leftVertex
y) ==vertices
[x,y] [] connect (leftVertex
x) (rightVertex
y) ==edge
x y connect (rightVertex
x) (leftVertex
y) ==edge
y x connect (rightVertex
x) (rightVertex
y) ==vertices
[] [x,y] connect (vertices
xs1 ys1) (vertices
xs2 ys2) ==overlay
(biclique
xs1 ys2) (biclique
xs2 ys1)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) >=leftVertexCount
x *rightVertexCount
yedgeCount
(connect x y) <=leftVertexCount
x *rightVertexCount
y +rightVertexCount
x *leftVertexCount
y +edgeCount
x +edgeCount
y
vertices :: (Ord a, Ord b) => [a] -> [b] -> AdjacencyMap a b Source #
Construct the graph comprising given lists of isolated vertices in each part. Complexity: O(L * log(L)) time and O(L) memory, where L is the total length of two lists.
vertices [] [] ==empty
vertices [x] [] ==leftVertex
x vertices [] [x] ==rightVertex
x vertices xs ys ==overlays
(map
leftVertex
xs ++map
rightVertex
ys)hasLeftVertex
x (vertices xs ys) ==elem
x xshasRightVertex
y (vertices xs ys) ==elem
y ys
overlays :: (Ord a, Ord b) => [AdjacencyMap a b] -> AdjacencyMap a b Source #
connects :: (Ord a, Ord b) => [AdjacencyMap a b] -> AdjacencyMap a b Source #
swap :: AdjacencyMap a b -> AdjacencyMap b a Source #
Conversion functions
toBipartite :: (Ord a, Ord b) => AdjacencyMap (Either a b) -> AdjacencyMap a b Source #
Construct a bipartite AdjacencyMap
from an Algebra.Graph.AdjacencyMap,
adding any missing edges to make the graph undirected and filtering out the
edges within the same parts.
Complexity: O(m * log(n)).
toBipartiteempty
==empty
toBipartite (vertex
(Left x)) ==leftVertex
x toBipartite (vertex
(Right x)) ==rightVertex
x toBipartite (edge
(Left x) (Left y)) ==vertices
[x,y] [] toBipartite (edge
(Left x) (Right y)) ==edge
x y toBipartite (edge
(Right x) (Left y)) ==edge
y x toBipartite (edge
(Right x) (Right y)) ==vertices
[] [x,y] toBipartite .clique
==uncurry
biclique
.partitionEithers
toBipartite .fromBipartite
==id
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c) -> AdjacencyMap a -> AdjacencyMap b c Source #
Construct a bipartite AdjacencyMap
from an Algebra.Graph.AdjacencyMap,
where the two parts are identified by a separate function, adding any missing
edges to make the graph undirected and filtering out the edges within the
same parts.
Complexity: O(m * log(n)).
toBipartiteWith fempty
==empty
toBipartiteWith Left x ==vertices
(vertexList
x) [] toBipartiteWith Right x ==vertices
[] (vertexList
x) toBipartiteWith f ==toBipartite
.gmap
f toBipartiteWith id ==toBipartite
fromBipartite :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap (Either a b) Source #
Construct an Algebra.Graph.AdjacencyMap from a bipartite AdjacencyMap
.
Complexity: O(m * log(n)).
fromBipartiteempty
==empty
fromBipartite (leftVertex
x) ==vertex
(Left x) fromBipartite (edge
x y) ==edges
[(Left x, Right y), (Right y, Left x)]toBipartite
. fromBipartite ==id
fromBipartiteWith :: Ord c => (a -> c) -> (b -> c) -> AdjacencyMap a b -> AdjacencyMap c Source #
Construct an Algebra.Graph.AdjacencyMap from a bipartite AdjacencyMap
given a way to inject vertices of the two parts into the resulting vertex
type.
Complexity: O(m * log(n)).
fromBipartiteWith Left Right ==fromBipartite
fromBipartiteWith id id (vertices
xs ys) ==vertices
(xs ++ ys) fromBipartiteWith id id .edges
==symmetricClosure
.edges
Graph properties
isEmpty :: AdjacencyMap a b -> Bool Source #
hasLeftVertex :: Ord a => a -> AdjacencyMap a b -> Bool Source #
Check if a graph contains a given vertex in the left part. Complexity: O(log(l)) time.
hasLeftVertex xempty
== False hasLeftVertex x (leftVertex
y) == (x == y) hasLeftVertex x (rightVertex
y) == False
hasRightVertex :: Ord b => b -> AdjacencyMap a b -> Bool Source #
Check if a graph contains a given vertex in the right part. Complexity: O(log(r)) time.
hasRightVertex xempty
== False hasRightVertex x (leftVertex
y) == False hasRightVertex x (rightVertex
y) == (x == y)
hasVertex :: (Ord a, Ord b) => Either a b -> AdjacencyMap a b -> Bool Source #
Check if a graph contains a given vertex. Complexity: O(log(n)) time.
hasVertex . Left ==hasLeftVertex
hasVertex . Right ==hasRightVertex
leftVertexCount :: AdjacencyMap a b -> Int Source #
The number of vertices in the left part of a graph. Complexity: O(1) time.
leftVertexCountempty
== 0 leftVertexCount (leftVertex
x) == 1 leftVertexCount (rightVertex
x) == 0 leftVertexCount (edge
x y) == 1 leftVertexCount .edges
==length
.nub
.map
fst
rightVertexCount :: AdjacencyMap a b -> Int Source #
The number of vertices in the right part of a graph. Complexity: O(1) time.
rightVertexCountempty
== 0 rightVertexCount (leftVertex
x) == 0 rightVertexCount (rightVertex
x) == 1 rightVertexCount (edge
x y) == 1 rightVertexCount .edges
==length
.nub
.map
snd
vertexCount :: AdjacencyMap a b -> Int Source #
The number of vertices in a graph. Complexity: O(1) time.
vertexCountempty
== 0 vertexCount (vertex
x) == 1 vertexCount (edge
x y) == 2 vertexCount x ==leftVertexCount
x +rightVertexCount
x
edgeCount :: AdjacencyMap a b -> Int Source #
leftVertexList :: AdjacencyMap a b -> [a] Source #
The sorted list of vertices of the left part of a graph. Complexity: O(l) time and memory.
leftVertexListempty
== [] leftVertexList (leftVertex
x) == [x] leftVertexList (rightVertex
x) == [] leftVertexList .flip
vertices
[] ==nub
.sort
rightVertexList :: AdjacencyMap a b -> [b] Source #
The sorted list of vertices of the right part of a graph. Complexity: O(r) time and memory.
rightVertexListempty
== [] rightVertexList (leftVertex
x) == [] rightVertexList (rightVertex
x) == [x] rightVertexList .vertices
[] ==nub
.sort
vertexList :: AdjacencyMap a b -> [Either a b] Source #
edgeList :: AdjacencyMap a b -> [(a, b)] Source #
leftVertexSet :: AdjacencyMap a b -> Set a Source #
The set of vertices of the left part of a graph. Complexity: O(l) time and memory.
leftVertexSetempty
== Set.empty
leftVertexSet .leftVertex
== Set.singleton
leftVertexSet .rightVertex
==const
Set.empty
leftVertexSet .flip
vertices
[] == Set.fromList
rightVertexSet :: AdjacencyMap a b -> Set b Source #
The set of vertices of the right part of a graph. Complexity: O(r) time and memory.
rightVertexSetempty
== Set.empty
rightVertexSet .leftVertex
==const
Set.empty
rightVertexSet .rightVertex
== Set.singleton
rightVertexSet .vertices
[] == Set.fromList
leftAdjacencyList :: AdjacencyMap a b -> [(a, [b])] Source #
The sorted adjacency list of the left part of a graph. Complexity: O(n + m) time and memory.
leftAdjacencyListempty
== [] leftAdjacencyList (vertices
[] xs) == [] leftAdjacencyList (vertices
xs []) == [(x, []) | x <-nub
(sort
xs)] leftAdjacencyList (edge
x y) == [(x, [y])] leftAdjacencyList (star
x ys) == [(x,nub
(sort
ys))]
rightAdjacencyList :: AdjacencyMap a b -> [(b, [a])] Source #
The sorted adjacency list of the right part of a graph. Complexity: O(n + m) time and memory.
rightAdjacencyListempty
== [] rightAdjacencyList (vertices
[] xs) == [(x, []) | x <-nub
(sort
xs)] rightAdjacencyList (vertices
xs []) == [] rightAdjacencyList (edge
x y) == [(y, [x])] rightAdjacencyList (star
x ys) == [(y, [x]) | y <-nub
(sort
ys)]
Standard families of graphs
A list of values of two alternating types. The first type argument denotes the type of the value at the head.
With the OverloadedLists
extension it is possible to use the standard list
notation to construct a List
where the two types coincide, for example:
[1, 2, 3, 4, 5] :: List Int Int
We make use of this shorthand notation in the examples below.
Instances
IsList (List a a) Source # | |
(Eq a, Eq b) => Eq (List a b) Source # | |
(Ord a, Ord b) => Ord (List a b) Source # | |
Defined in Algebra.Graph.Bipartite.AdjacencyMap | |
(Show a, Show b) => Show (List a b) Source # | |
Generic (List a b) Source # | |
type Rep (List a b) Source # | |
Defined in Algebra.Graph.Bipartite.AdjacencyMap type Rep (List a b) = D1 ('MetaData "List" "Algebra.Graph.Bipartite.AdjacencyMap" "algebraic-graphs-0.7-DxCmXygYU3a8wvsz565Q5f" 'False) (C1 ('MetaCons "Nil" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (List b a)))) | |
type Item (List a a) Source # | |
Defined in Algebra.Graph.Bipartite.AdjacencyMap |
circuit :: (Ord a, Ord b) => [(a, b)] -> AdjacencyMap a b Source #
The circuit on a list of pairs of vertices. Complexity: O(L * log(L)) time, where L is the length of the given list.
circuit [] ==empty
circuit [(x,y)] ==edge
x y circuit [(1,2), (3,4), (5,6)] ==edges
[(1,2), (3,2), (3,4), (5,4), (5,6), (1,6)] circuit .reverse
==swap
. circuit .map
Data.Tuple.swap
star :: (Ord a, Ord b) => a -> [b] -> AdjacencyMap a b Source #
The star formed by a center vertex connected to a list of leaves. Complexity: O(L * log(L)) time, where L is the length of the given list.
star x [] ==leftVertex
x star x [y] ==edge
x y star x [y,z] ==edges
[(x,y), (x,z)] star x ys ==connect
(leftVertex
x) (vertices
[] ys)
stars :: (Ord a, Ord b) => [(a, [b])] -> AdjacencyMap a b Source #
The stars formed by overlaying a list of star
s.
Complexity: O(L * log(L)) time, where L is the total size of the input.
stars [] ==empty
stars [(x, [])] ==leftVertex
x stars [(x, [y])] ==edge
x y stars [(x, ys)] ==star
x ys stars ==overlays
.map
(uncurry
star
)overlay
(stars xs) (stars ys) == stars (xs ++ ys)
mesh :: (Ord a, Ord b) => [a] -> [b] -> AdjacencyMap (a, b) (a, b) Source #
Construct a mesh graph from two lists of vertices. Complexity: O(L1 * L2 * log(L1 * L2)) time, where L1 and L2 are the lengths of the given lists.
mesh xs [] ==empty
mesh [] ys ==empty
mesh [x] [y] ==leftVertex
(x,y) mesh [1,1] ['a','b'] ==biclique
[(1,'a'), (1,'b')] [(1,'a'), (1,'b')] mesh [1,2] ['a','b'] ==biclique
[(1,'a'), (2,'b')] [(1,'b'), (2,'a')]
Graph transformation
removeLeftVertex :: Ord a => a -> AdjacencyMap a b -> AdjacencyMap a b Source #
Remove a vertex from the left part of a given graph. Complexity: O(r * log(l)) time.
removeLeftVertex x (leftVertex
x) ==empty
removeLeftVertex 1 (leftVertex
2) ==leftVertex
2 removeLeftVertex x (rightVertex
y) ==rightVertex
y removeLeftVertex x (edge
x y) ==rightVertex
y removeLeftVertex x . removeLeftVertex x == removeLeftVertex x
removeRightVertex :: Ord b => b -> AdjacencyMap a b -> AdjacencyMap a b Source #
Remove a vertex from the right part of a given graph. Complexity: O(l * log(r)) time.
removeRightVertex x (rightVertex
x) ==empty
removeRightVertex 1 (rightVertex
2) ==rightVertex
2 removeRightVertex x (leftVertex
y) ==leftVertex
y removeRightVertex y (edge
x y) ==leftVertex
x removeRightVertex x . removeRightVertex x == removeRightVertex x
removeEdge :: (Ord a, Ord b) => a -> b -> AdjacencyMap a b -> AdjacencyMap a b Source #
Remove an edge from a given graph. Complexity: O(log(l) + log(r)) time.
removeEdge x y (edge
x y) ==vertices
[x] [y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .removeLeftVertex
x ==removeLeftVertex
x removeEdge x y .removeRightVertex
y ==removeRightVertex
y
bimap :: (Ord a, Ord b, Ord c, Ord d) => (a -> c) -> (b -> d) -> AdjacencyMap a b -> AdjacencyMap c d Source #
Transform a graph by applying given functions to the vertices of each part. Complexity: O((n + m) * log(n)) time.
bimap f gempty
==empty
bimap f g .vertex
==vertex
. Data.Bifunctor.bimap
f g bimap f g (edge
x y) ==edge
(f x) (g y) bimapid
id
==id
bimap f1 g1 . bimap f2 g2 == bimap (f1 . f2) (g1 . g2)
Graph composition
box :: (Ord a, Ord b) => AdjacencyMap a a -> AdjacencyMap b b -> AdjacencyMap (a, b) (a, b) Source #
Compute the Cartesian product of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.
box
(path
[0,1]) (path
['a','b']) ==edges
[ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((1,'b'), (0,'b')) , ((1,'b'), (1,'a')) ]
Up to isomorphism between the resulting vertex types, this operation is
commutative, associative, distributes over overlay
, has singleton
graphs as identities and swapping identities, and empty
as the
annihilating zero. Below ~~
stands for equality up to an isomorphism,
e.g. (x,
()) ~~ x
.
box x y ~~ box y x box x (box y z) ~~ box (box x y) z box x (overlay
y z) ==overlay
(box x y) (box x z) box x (leftVertex
()) ~~ x box x (rightVertex
()) ~~swap
x box xempty
~~empty
vertexCount
(box x y) ==vertexCount
x *vertexCount
yedgeCount
(box x y) ==vertexCount
x *edgeCount
y +edgeCount
x *vertexCount
y
boxWith :: (Ord a, Ord b, Ord c, Ord d, Ord e, Ord f) => (a -> c -> e) -> (b -> d -> e) -> (a -> d -> f) -> (b -> c -> f) -> AdjacencyMap a b -> AdjacencyMap c d -> AdjacencyMap e f Source #
Compute the generalised Cartesian product of two graphs. The resulting vertices are obtained using the given vertex combinators. Complexity: O((n + m) * log(n)) time and O(n + m) memory.
See box
for some examples.
box == boxWith (,) (,) (,) (,)
Miscellaneous
consistent :: (Ord a, Ord b) => AdjacencyMap a b -> Bool Source #
Check that the internal graph representation is consistent, i.e. that all
edges that are present in the leftAdjacencyMap
are also present in the
rightAdjacencyMap
map. It should be impossible to create an inconsistent
adjacency map, and we use this function in testing.
consistentempty
== True consistent (vertex
x) == True consistent (edge
x y) == True consistent (edges
x) == True consistent (toBipartite
x) == True consistent (swap
x) == True consistent (circuit
x) == True consistent (biclique
x y) == True