Algebra.Graph.Bipartite.Undirected.AdjacencyMap

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. To avoid name clashes with Algebra.Graph.AdjacencyMap, this module can be imported qualified:

import qualified Algebra.Graph.Bipartite.Undirected.AdjacencyMap as Bipartite

Data structure

data AdjacencyMap a b

The AdjacencyMap data type represents an undirected bipartite graph. The two type parameteters define the types of identifiers of the vertices of each part.

Note: even if the identifiers and their types for two vertices of different parts are equal, these vertices are considered to be different. See examples for more details.

We define a Num instance as a convenient notation for working with bipartite graphs:

0                     == rightVertex 0
swap 1                == leftVertex 1
swap 1 + 2            == vertices [1] [2]
swap 1 * 2            == edge 1 2
swap 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 algebraic graphs:

• overlay is commutative and associative:

        x + y == y + x
  x + (y + z) == (x + y) + z

• connect is commutative, associative and has empty as the identity:

    x * empty == x
    empty * x == x
        x * y == y * x
  x * (y * z) == (x * y) * z

• connect distributes over overlay:

  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 as overlay on vertices of one 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 has empty 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. In addition, l and r will denote the number of vertices in the left and in the right part of graph, respectively.

Instances

(Ord a, Ord b) => Eq (AdjacencyMap a b)

Defined in Algebra.Graph.Bipartite.Undirected.AdjacencyMap

Methods

(==) :: AdjacencyMap a b -> AdjacencyMap a b -> Bool

(/=) :: AdjacencyMap a b -> AdjacencyMap a b -> Bool

(Ord a, Ord b, Num b) => Num (AdjacencyMap a b)

Note: this does not satisfy the usual ring laws; see AdjacencyMap for more details.

Defined in Algebra.Graph.Bipartite.Undirected.AdjacencyMap

Methods

(+) :: AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b

(-) :: AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b

(*) :: AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b

negate :: AdjacencyMap a b -> AdjacencyMap a b

abs :: AdjacencyMap a b -> AdjacencyMap a b

signum :: AdjacencyMap a b -> AdjacencyMap a b

fromInteger :: Integer -> AdjacencyMap a b

(Ord a, Ord b) => Ord (AdjacencyMap a b)

Defined in Algebra.Graph.Bipartite.Undirected.AdjacencyMap

Methods

compare :: AdjacencyMap a b -> AdjacencyMap a b -> Ordering

(<) :: AdjacencyMap a b -> AdjacencyMap a b -> Bool

(<=) :: AdjacencyMap a b -> AdjacencyMap a b -> Bool

(>) :: AdjacencyMap a b -> AdjacencyMap a b -> Bool

(>=) :: AdjacencyMap a b -> AdjacencyMap a b -> Bool

max :: AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b

min :: AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b

(Ord a, Ord b, Show a, Show b) => Show (AdjacencyMap a b)

Defined in Algebra.Graph.Bipartite.Undirected.AdjacencyMap

Methods

showsPrec :: Int -> AdjacencyMap a b -> ShowS

show :: AdjacencyMap a b -> String

showList :: [AdjacencyMap a b] -> ShowS

Generic (AdjacencyMap a b)

Defined in Algebra.Graph.Bipartite.Undirected.AdjacencyMap

Associated Types

type Rep (AdjacencyMap a b) :: Type -> Type

Methods

from :: AdjacencyMap a b -> Rep (AdjacencyMap a b) x

to :: Rep (AdjacencyMap a b) x -> AdjacencyMap a b

type Rep (AdjacencyMap a b)

Defined in Algebra.Graph.Bipartite.Undirected.AdjacencyMap

type Rep (AdjacencyMap a b) = D1 (MetaData "AdjacencyMap" "Algebra.Graph.Bipartite.Undirected.AdjacencyMap" "algebraic-graphs-0.5-4dnrALfehjHELqhQlGFoFS" False) (C1 (MetaCons "BAM" PrefixI True) (S1 (MetaSel (Just "leftAdjacencyMap") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map a (Set b))) :*: S1 (MetaSel (Just "rightAdjacencyMap") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map b (Set a)))))

leftAdjacencyMap :: AdjacencyMap a b -> Map a (Set b)

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.

leftAdjacencyMap empty           == 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)

The adjacency map of the right part of the graph: each right vertex is associated with a set of left neighbours. Complexity: O(1) time and memory.

rightAdjacencyMap empty           == 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

Construct the empty graph. Complexity: O(1) time and memory.

isEmpty empty           == True
leftAdjacencyMap empty  == Map.empty
rightAdjacencyMap empty == Map.empty
hasVertex x empty       == False

leftVertex :: a -> AdjacencyMap a b

Construct the bipartite graph comprising a single isolated vertex in the left part. Complexity: O(1) time and memory.

leftAdjacencyMap (leftVertex x)  == Map.singleton x Set.empty
rightAdjacencyMap (leftVertex x) == Map.empty
hasLeftVertex x (leftVertex y)   == (x == y)
hasRightVertex x (leftVertex y)  == False
hasEdge x y (leftVertex z)       == False

rightVertex :: b -> AdjacencyMap a b

Construct the bipartite graph comprising a single isolated vertex in the right part. Complexity: O(1) time and memory.

leftAdjacencyMap (rightVertex x)  == Map.empty
rightAdjacencyMap (rightVertex x) == Map.singleton x Set.empty
hasLeftVertex x (rightVertex y)   == False
hasRightVertex x (rightVertex y)  == (x == y)
hasEdge x y (rightVertex z)       == False

vertex :: Either a b -> AdjacencyMap a b

Construct the bipartite graph comprising a single isolated vertex. Complexity: O(1) time and memory.

vertex . Left  == leftVertex
vertex . Right == rightVertex

edge :: a -> b -> AdjacencyMap a b

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

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)       == True
hasEdge 1 2 (edge 2 1)       == False

overlay :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b

Overlay two bipartite 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

connect :: (Ord a, Ord b) => AdjacencyMap a b -> AdjacencyMap a b -> AdjacencyMap a b

Connect two bipartite graphs, not adding the edges between vertices in 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   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)                     >= leftVertexCount x * rightVertexCount y
edgeCount   (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

Construct the graph comprising two given lists of isolated vertices for 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
hasLeftVertex  x (vertices xs ys) == elem x xs
hasRightVertex y (vertices xs ys) == elem y ys

edges :: (Ord a, Ord b) => [(a, b)] -> AdjacencyMap a b

Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

edges []            == empty
edges [(x,y)]       == edge x y
edges               == overlays . map (uncurry edge)
hasEdge x y . edges == elem (x,y)
edgeCount   . edges == length . nub

overlays :: (Ord a, Ord b) => [AdjacencyMap a b] -> AdjacencyMap a b

Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

overlays []        == empty
overlays [x]       == x
overlays [x,y]     == overlay x y
overlays           == foldr overlay empty
isEmpty . overlays == all isEmpty

connects :: (Ord a, Ord b) => [AdjacencyMap a b] -> AdjacencyMap a b

Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

connects []        == empty
connects [x]       == x
connects [x,y]     == connect x y
connects           == foldr connect empty
isEmpty . connects == all isEmpty

swap :: AdjacencyMap a b -> AdjacencyMap b a

Swap parts of a given graph. Complexity: O(1) time and memory.

swap empty            == empty
swap . leftVertex     == rightVertex
swap (vertices xs ys) == vertices ys xs
swap (edge x y)       == edge y x
swap . edges          == edges . map Data.Tuple.swap
swap . swap           == id

Conversion functions

toBipartite :: (Ord a, Ord b) => AdjacencyMap (Either a b) -> AdjacencyMap a b

Construct a bipartite AdjacencyMap from an Algebra.Graph.AdjacencyMap with given part identifiers, adding all needed edges to make the graph undirected and removing all edges within the same parts. Complexity: O(m * log(n)).

toBipartite empty                      == 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 xs)                == uncurry biclique (partitionEithers xs)
toBipartite . fromBipartite            == id

toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c) -> AdjacencyMap a -> AdjacencyMap b c

Construct a bipartite AdjacencyMap from Algebra.Graph.AdjacencyMap with part identifiers obtained from a given function, adding all neeeded edges to make the graph undirected and removing all edges within the same parts. Complexity: O(m * log(n)).

toBipartiteWith f empty == 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)

Construct an AdjacencyMap from a bipartite AdjacencyMap. Complexity: O(m * log(n)).

fromBipartite empty          == 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

Construct an AdjacencyMap from a bipartite AdjacencyMap given a way to inject vertices from different 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

Check if a graph is empty. Complecity: O(1) time.

isEmpty empty                 == True
isEmpty (overlay empty empty) == True
isEmpty (vertex x)            == False
isEmpty                       == (==) empty

hasLeftVertex :: Ord a => a -> AdjacencyMap a b -> Bool

Check if a graph contains a given vertex in the left part. Complexity: O(log(n)) time.

hasLeftVertex x empty           == False
hasLeftVertex x (leftVertex y)  == (x == y)
hasLeftVertex x (rightVertex y) == False

hasRightVertex :: Ord b => b -> AdjacencyMap a b -> Bool

Check if a graph contains a given vertex in the right part. Complexity: O(log(n)) time.

hasRightVertex x empty           == False
hasRightVertex x (leftVertex y)  == False
hasRightVertex x (rightVertex y) == (x == y)

hasVertex :: (Ord a, Ord b) => Either a b -> AdjacencyMap a b -> Bool

Check if a graph contains a given vertex. Complexity: O(log(n)) time.

hasVertex . Left  == hasLeftVertex
hasVertex . Right == hasRightVertex

hasEdge :: (Ord a, Ord b) => a -> b -> AdjacencyMap a b -> Bool

Check if a graph contains a given edge. Complexity: O(log(n)) time.

hasEdge x y empty      == False
hasEdge x y (vertex z) == False
hasEdge x y (edge x y) == True
hasEdge x y            == elem (x,y) . edgeList

leftVertexCount :: AdjacencyMap a b -> Int

The number of vertices in the left part in a graph. Complexity: O(1) time.

leftVertexCount empty           == 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

The number of vertices in the right part in a graph. Complexity: O(1) time.

rightVertexCount empty           == 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

The number of vertices in a graph. Complexity: O(1) time.

vertexCount empty      == 0
vertexCount (vertex x) == 1
vertexCount (edge x y) == 2
vertexCount x          == leftVertexCount x + rightVertexCount x

edgeCount :: AdjacencyMap a b -> Int

The number of edges in a graph. Complexity: O(n) time.

edgeCount empty      == 0
edgeCount (vertex x) == 0
edgeCount (edge x y) == 1
edgeCount . edges    == length . nub

leftVertexList :: AdjacencyMap a b -> [a]

The sorted list of vertices of the left part of a given graph. Complexity: O(l) time and memory.

leftVertexList empty              == []
leftVertexList (leftVertex x)     == [x]
leftVertexList (rightVertex x)    == []
leftVertexList . flip vertices [] == nub . sort

rightVertexList :: AdjacencyMap a b -> [b]

The sorted list of vertices of the right part of a given graph. Complexity: O(r) time and memory.

rightVertexList empty           == []
rightVertexList (leftVertex x)  == []
rightVertexList (rightVertex x) == [x]
rightVertexList . vertices []   == nub . sort

vertexList :: AdjacencyMap a b -> [Either a b]

The sorted list of vertices of a given graph. Complexity: O(n) time and memory

vertexList empty                             == []
vertexList (vertex x)                        == [x]
vertexList (edge x y)                        == [Left x, Right y]
vertexList (vertices (lefts xs) (rights xs)) == nub (sort xs)

edgeList :: AdjacencyMap a b -> [(a, b)]

The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.

edgeList empty      == []
edgeList (vertex x) == []
edgeList (edge x y) == [(x,y)]
edgeList . edges    == nub . sort

leftVertexSet :: AdjacencyMap a b -> Set a

The set of vertices of the left part of a given graph. Complexity: O(l) time and memory.

leftVertexSet empty              == Set.empty
leftVertexSet . leftVertex       == Set.singleton
leftVertexSet . rightVertex      == const Set.empty
leftVertexSet . flip vertices [] == Set.fromList

rightVertexSet :: AdjacencyMap a b -> Set b

The set of vertices of the right part of a given graph. Complexity: O(r) time and memory.

rightVertexSet empty         == Set.empty
rightVertexSet . leftVertex  == const Set.empty
rightVertexSet . rightVertex == Set.singleton
rightVertexSet . vertices [] == Set.fromList

vertexSet :: (Ord a, Ord b) => AdjacencyMap a b -> Set (Either a b)

The set of vertices of a given graph. Complexity: O(n) time and memory.

vertexSet empty                             == Set.empty
vertexSet . vertex                          == Set.singleton
vertexSet (edge x y)                        == Set.fromList [Left x, Right y]
vertexSet (vertices (lefts xs) (rights xs)) == Set.fromList xs

edgeSet :: (Ord a, Ord b) => AdjacencyMap a b -> Set (a, b)

The set of edges of a given graph. Complexity: O(n + m) time and O(m) memory.

edgeSet empty      == Set.empty
edgeSet (vertex x) == Set.empty
edgeSet (edge x y) == Set.singleton (x,y)
edgeSet . edges    == Set.fromList

Standard families of graphs

circuit :: (Ord a, Ord b) => [(a, b)] -> AdjacencyMap a b

The circuit on a list of vertices. Complexity: O(n * log(n)) time and O(n) memory.

circuit []                    == empty
circuit [(x,y)]               == edge x y
circuit [(1,2), (3,4)]        == biclique [1,3] [2,4]
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

biclique :: (Ord a, Ord b) => [a] -> [b] -> AdjacencyMap a b

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

biclique [] [] == empty
biclique xs [] == vertices xs []
biclique [] ys == vertices [] ys
biclique xs ys == connect (vertices xs []) (vertices [] ys)

Algorithms

type OddCycle a = [a]

An cycle of odd length. For example, [1, 2, 3] represents the cycle 1 -> 2 -> 3 -> 1.

detectParts :: Ord a => AdjacencyMap a -> Either (OddCycle a) (AdjacencyMap a a)

Test the bipartiteness of given graph. In case of success, return an AdjacencyMap with the same set of edges and each vertex marked with the part it belongs to. In case of failure, return any cycle of odd length in the graph.

The returned partition is lexicographically minimal. That is, consider the string of part identifiers for each vertex in ascending order. Then, considering that the identifier of the left part is less then the identifier of the right part, this string is lexicographically minimal of all such strings for all partitions.

The returned cycle is optimal in the following way: there exists a path that is either empty or ends in a vertex adjacent to the first vertex in the cycle, such that all vertices in path ++ cycle are distinct and path ++ cycle is lexicographically minimal among all such pairs of paths and cycles.

Note: since AdjacencyMap represents undirected bipartite graphs, all edges in the input graph are treated as undirected. See the examples and the correctness property for a clarification.

It is advised to use leftVertexList and rightVertexList to obtain the partition of the vertices and hasLeftVertex and hasRightVertex to check whether a vertex belongs to a part.

Complexity: O((n + m) * log(n)) time and O(n + m) memory.

detectParts empty                                       == Right empty
detectParts (vertex x)                                  == Right (leftVertex x)
detectParts (edge x x)                                  == Left [x]
detectParts (edge 1 2)                                  == Right (edge 1 2)
detectParts (1 * (2 + 3))                               == Right (edges [(1,2), (1,3)])
detectParts (1 * 2 * 3)                                 == Left [1, 2, 3]
detectParts ((1 + 3) * (2 + 4) + 6 * 5)                 == Right (swap (1 + 3) * (2 + 4) + swap 5 * 6)
detectParts ((1 * 3 * 4) + 2 * (1 + 2))                 == Left [2]
detectParts (clique [1..10])                            == Left [1, 2, 3]
detectParts (circuit [1..10])                           == Right (circuit [(x, x + 1) | x <- [1,3,5,7,9]])
detectParts (circuit [1..11])                           == Left [1..11]
detectParts (biclique [] xs)                            == Right (vertices xs [])
detectParts (biclique (map Left (x:xs)) (map Right ys)) == Right (biclique (map Left (x:xs)) (map Right ys))
isRight (detectParts (star x ys))                       == notElem x ys
isRight (detectParts (fromBipartite (toBipartite x)))   == True

The correctness of detectParts can be expressed by the following property:

let undirected = symmetricClosure input in
case detectParts input of
    Left cycle -> mod (length cycle) 2 == 1 && isSubgraphOf (circuit cycle) undirected
    Right result -> gmap fromEither (fromBipartite result) == undirected

Miscellaneous

consistent :: (Ord a, Ord b) => AdjacencyMap a b -> Bool

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.

consistent empty           == 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