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 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 undirected bipartite 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 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 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 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.

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)

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.

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)

Construct the empty graph.

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

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)  == False
hasEdge x y (leftVertex z)       == False

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)   == False
hasRightVertex x (rightVertex y)  == (x == y)
hasEdge x y (rightVertex z)       == False

Construct the graph comprising a single isolated vertex.

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

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

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   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 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   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

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 xs
hasRightVertex y (vertices xs ys) == elem y ys

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

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

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 the 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

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)).

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

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 f empty == empty
toBipartiteWith Left x  == vertices (vertexList x) []
toBipartiteWith Right x == vertices [] (vertexList x)
toBipartiteWith f       == toBipartite . gmap f
toBipartiteWith id      == toBipartite

Construct an Algebra.Graph.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

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

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

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

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

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

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

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

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

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

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

The number of vertices in the left part of 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

The number of vertices in the right part of 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

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

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

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

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

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

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

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

The sorted list of vertices of a 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)

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

The set of vertices of the left part of a 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

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

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

The set of vertices of a 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

The set of edges of a 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

The sorted adjacency list of the left part of a graph. Complexity: O(n + m) time and memory.

leftAdjacencyList empty            == []
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))]

The sorted adjacency list of the right part of a graph. Complexity: O(n + m) time and memory.

rightAdjacencyList empty            == []
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)]

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.

Construct a List of even length from a list of pairs.

evenList []                 == Nil
evenList [(1,2), (3,4)]     == [1, 2, 3, 4] :: List Int Int
evenList [(1,'a'), (2,'b')] == Cons 1 (Cons 'a' (Cons 2 (Cons 'b' Nil)))

Construct a List of odd length given the first element and a list of pairs.

oddList 1 []                 == Cons 1 Nil
oddList 1 [(2,3), (4,5)]     == [1, 2, 3, 4, 5] :: List Int Int
oddList 1 [('a',2), ('b',3)] == Cons 1 (Cons 'a' (Cons 2 (Cons 'b' (Cons 3 Nil))))

The path on a List of vertices. Complexity: O(L * log(L)) time, where L is the length of the given list.

path Nil                   == empty
path (Cons x Nil)          == leftVertex x
path (Cons x (Cons y Nil)) == edge x y
path [1, 2, 3, 4, 5]       == edges [(1,2), (3,2), (3,4), (5,4)]

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

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)

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)

The stars formed by overlaying a list of stars. 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)

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')]

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

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

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

Transform a graph by applying given functions to the vertices of each part. Complexity: O((n + m) * log(n)) time.

bimap f g empty           == empty
bimap f g . vertex        == vertex . Data.Bifunctor.bimap f g
bimap f g (edge x y)      == edge (f x) (g y)
bimap id id               == id
bimap f1 g1 . bimap f2 g2 == bimap (f1 . f2) (g1 . g2)

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 x empty            ~~ empty
vertexCount (box x y)  == vertexCount x * vertexCount y
edgeCount   (box x y)  == vertexCount x * edgeCount y + edgeCount x * vertexCount y

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 (,) (,) (,) (,)

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