Edge-labelled graphs, where the type variable e stands for edge labels. For example, AdjacencyMap Bool a is isomorphic to unlabelled graphs defined in the top-level module Algebra.Graph.AdjacencyMap, where False and True denote the lack of and the existence of an unlabelled edge, respectively.

The adjacency map of an edge-labelled graph: each vertex is associated with a map from its direct successors to the corresponding edge labels.

Construct the empty graph.

isEmpty     empty == True
hasVertex x empty == False
vertexCount empty == 0
edgeCount   empty == 0

Construct the graph comprising a single isolated vertex.

isEmpty     (vertex x) == False
hasVertex x (vertex y) == (x == y)
vertexCount (vertex x) == 1
edgeCount   (vertex x) == 0

Construct the graph comprising a single edge.

edge e    x y              == connect e (vertex x) (vertex y)
edge zero x y              == vertices [x,y]
hasEdge   x y (edge e x y) == (e /= zero)
edgeLabel x y (edge e x y) == e
edgeCount     (edge e x y) == if e == zero then 0 else 1
vertexCount   (edge e 1 1) == 1
vertexCount   (edge e 1 2) == 2

The left-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges.

x -<e>- y == edge e x y

The right-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges.

x -<e>- y == edge e x y

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
vertexCount (overlay 1 2) == 2
edgeCount   (overlay 1 2) == 0

Note: overlay composes edges in parallel using the operator <+> with zero acting as the identity:

edgeLabel x y $ overlay (edge e x y) (edge zero x y) == e
edgeLabel x y $ overlay (edge e x y) (edge f    x y) == e <+> f

Furthermore, when applied to transitive graphs, overlay composes edges in sequence using the operator <.> with one acting as the identity:

edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge one y z)) == e
edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge f   y z)) == e <.> f

Connect two graphs with edges labelled by a given label. When applied to the same labels, this is an 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).

isEmpty     (connect e x y) == isEmpty   x   && isEmpty   y
hasVertex z (connect e x y) == hasVertex z x || hasVertex z y
vertexCount (connect e x y) >= vertexCount x
vertexCount (connect e x y) <= vertexCount x + vertexCount y
edgeCount   (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
vertexCount (connect e 1 2) == 2
edgeCount   (connect e 1 2) == if e == zero then 0 else 1

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 . map vertex
hasVertex x . vertices == elem x
vertexCount . vertices == length . nub
vertexSet   . vertices == Set.fromList

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

edges []        == empty
edges [(e,x,y)] == edge e x y
edges           == overlays . map (\(e, x, y) -> edge e x y)

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

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

fromAdjacencyMaps []                                  == empty
fromAdjacencyMaps [(x, Map.empty)]                    == vertex x
fromAdjacencyMaps [(x, Map.singleton y e)]            == if e == zero then vertices [x,y] else edge e x y
overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs ++ ys)

The isSubgraphOf function takes two graphs and returns True if the first graph is a subgraph of the second. Complexity: O(s + m * log(m)) time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.

isSubgraphOf empty      x     ==  True
isSubgraphOf (vertex x) empty ==  False
isSubgraphOf x y              ==> x <= y

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

isEmpty empty                         == True
isEmpty (overlay empty empty)         == True
isEmpty (vertex x)                    == False
isEmpty (removeVertex x $ vertex x)   == True
isEmpty (removeEdge x y $ edge e x y) == False

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

hasVertex x empty            == False
hasVertex x (vertex y)       == (x == y)
hasVertex x . removeVertex x == const False

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 e x y)     == (e /= zero)
hasEdge x y . removeEdge x y == const False
hasEdge x y                  == not . null . filter (\(_,ex,ey) -> ex == x && ey == y) . edgeList

Extract the label of a specified edge in a graph. Complexity: O(log(n)) time.

edgeLabel x y empty         == zero
edgeLabel x y (vertex z)    == zero
edgeLabel x y (edge e x y)  == e
edgeLabel s t (overlay x y) == edgeLabel s t x + edgeLabel s t y

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

vertexCount empty             ==  0
vertexCount (vertex x)        ==  1
vertexCount                   ==  length . vertexList
vertexCount x < vertexCount y ==> x < y

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

edgeCount empty        == 0
edgeCount (vertex x)   == 0
edgeCount (edge e x y) == if e == zero then 0 else 1
edgeCount              == length . edgeList

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

vertexList empty      == []
vertexList (vertex x) == [x]
vertexList . vertices == nub . sort

The list of edges of a graph, sorted lexicographically with respect to pairs of connected vertices (i.e. edge-labels are ignored when sorting). Complexity: O(n + m) time and O(m) memory.

edgeList empty        == []
edgeList (vertex x)   == []
edgeList (edge e x y) == if e == zero then [] else [(e,x,y)]

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

vertexSet empty      == Set.empty
vertexSet . vertex   == Set.singleton
vertexSet . vertices == Set.fromList

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 e x y) == if e == zero then Set.empty else Set.singleton (e,x,y)

The preset of an element x is the set of its direct predecessors. Complexity: O(n * log(n)) time and O(n) memory.

preSet x empty        == Set.empty
preSet x (vertex x)   == Set.empty
preSet 1 (edge e 1 2) == Set.empty
preSet y (edge e x y) == if e == zero then Set.empty else Set.fromList [x]

The postset of a vertex is the set of its direct successors. Complexity: O(log(n)) time and O(1) memory.

postSet x empty        == Set.empty
postSet x (vertex x)   == Set.empty
postSet x (edge e x y) == if e == zero then Set.empty else Set.fromList [y]
postSet 2 (edge e 1 2) == Set.empty

Convert a graph to the corresponding unlabelled AdjacencyMap by forgetting labels on all non-zero edges. Complexity: O((n + m) * log(n)) time and memory.

hasEdge x y == hasEdge x y . skeleton

Remove a vertex from a given graph. Complexity: O(n*log(n)) time.

removeVertex x (vertex x)       == empty
removeVertex 1 (vertex 2)       == vertex 2
removeVertex x (edge e x x)     == empty
removeVertex 1 (edge e 1 2)     == vertex 2
removeVertex x . removeVertex x == removeVertex x

Remove an edge from a given graph. Complexity: O(log(n)) time.

removeEdge x y (edge e x y)     == vertices [x,y]
removeEdge x y . removeEdge x y == removeEdge x y
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

The function replaceVertex x y replaces vertex x with vertex y in a given AdjacencyMap. 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            == gmap (\v -> if v == x then y else v)

Replace an edge from a given graph. If it doesn't exist, it will be created. Complexity: O(log(n)) time.

replaceEdge e x y z                 == overlay (removeEdge x y z) (edge e x y)
replaceEdge e x y (edge f x y)      == edge e x y
edgeLabel x y (replaceEdge e x y z) == e

Transpose a given graph. Complexity: O(m * log(n)) time, O(n + m) memory.

transpose empty        == empty
transpose (vertex x)   == vertex x
transpose (edge e x y) == edge e y x
transpose . transpose  == id

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 AdjacencyMap. Complexity: O((n + m) * log(n)) time.

gmap f empty        == empty
gmap f (vertex x)   == vertex (f x)
gmap f (edge e x y) == edge e (f x) (f y)
gmap id             == id
gmap f . gmap g     == gmap (f . g)

Transform a graph by applying a function h to each of its edge labels. Complexity: O((n + m) * log(n)) time.

The function h is required to be a homomorphism on the underlying type of labels e. At the very least it must preserve zero and <+>:

h zero      == zero
h x <+> h y == h (x <+> y)

If e is also a semiring, then h must also preserve the multiplicative structure:

h one       == one
h x <.> h y == h (x <.> y)

If the above requirements hold, then the implementation provides the following guarantees.

emap h empty           == empty
emap h (vertex x)      == vertex x
emap h (edge e x y)    == edge (h e) x y
emap h (overlay x y)   == overlay (emap h x) (emap h y)
emap h (connect e x y) == connect (h e) (emap h x) (emap h y)
emap id                == id
emap g . emap h        == emap (g . h)

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

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 then Just x else Nothing) == induce p

Compute the reflexive and transitive closure of a graph over the underlying star semiring using the Warshall-Floyd-Kleene algorithm.

closure empty         == empty
closure (vertex x)    == edge one x x
closure (edge e x x)  == edge one x x
closure (edge e x y)  == edges [(one,x,x), (e,x,y), (one,y,y)]
closure               == reflexiveClosure . transitiveClosure
closure               == transitiveClosure . reflexiveClosure
closure . closure     == closure
postSet x (closure y) == Set.fromList (reachable x y)

Compute the reflexive closure of a graph over the underlying semiring by adding a self-loop of weight one to every vertex. Complexity: O(n * log(n)) time.

reflexiveClosure empty              == empty
reflexiveClosure (vertex x)         == edge one x x
reflexiveClosure (edge e x x)       == edge one x x
reflexiveClosure (edge e x y)       == edges [(one,x,x), (e,x,y), (one,y,y)]
reflexiveClosure . reflexiveClosure == reflexiveClosure

Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.

symmetricClosure empty              == empty
symmetricClosure (vertex x)         == vertex x
symmetricClosure (edge e x y)       == edges [(e,x,y), (e,y,x)]
symmetricClosure x                  == overlay x (transpose x)
symmetricClosure . symmetricClosure == symmetricClosure

Compute the transitive closure of a graph over the underlying star semiring using a modified version of the Warshall-Floyd-Kleene algorithm, which omits the reflexivity step.

transitiveClosure empty               == empty
transitiveClosure (vertex x)          == vertex x
transitiveClosure (edge e x y)        == edge e x y
transitiveClosure . transitiveClosure == transitiveClosure

Check that the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and there are no zero-labelled edges. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.