The AdjacencyMap data type represents a graph by a map of vertices to their adjacency sets. We define a law-abiding Num instance as a convenient notation for working with graphs:

0           == vertex 0
1 + 2       == overlay (vertex 1) (vertex 2)
1 * 2       == connect (vertex 1) (vertex 2)
1 + 2 * 3   == overlay (vertex 1) (connect (vertex 2) (vertex 3))
1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))

The Show instance is defined using basic graph construction primitives:

show (empty     :: AdjacencyMap Int) == "empty"
show (1         :: AdjacencyMap Int) == "vertex 1"
show (1 + 2     :: AdjacencyMap Int) == "vertices [1,2]"
show (1 * 2     :: AdjacencyMap Int) == "edge 1 2"
show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: AdjacencyMap Int) == "graph [1,2,3] [(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 associative and has empty as the identity:

    x * empty == x
    empty * x == 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

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.

The adjacency map of the graph: each vertex is associated with a set of its direct successors.

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

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

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

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

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

edge x y               == connect (vertex x) (vertex y)
hasEdge x y (edge x y) == True
edgeCount   (edge x y) == 1
vertexCount (edge 1 1) == 1
vertexCount (edge 1 2) == 2

Overlay two graphs. This is an idempotent, commutative and associative 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

Connect two graphs. This is an associative operation with the identity empty, which distributes over the 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 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) >= edgeCount y
edgeCount   (connect x y) >= vertexCount x * vertexCount y
edgeCount   (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
vertexCount (connect 1 2) == 2
edgeCount   (connect 1 2) == 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
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 [(x, y)]    == edge x y
edgeCount . edges == length . nub
edgeList . edges  == nub . sort

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
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
isEmpty . connects == all isEmpty

Construct the graph from given lists of vertices V and edges E. The resulting graph contains the vertices V as well as all the vertices referred to by the edges E. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

graph []  []      == empty
graph [x] []      == vertex x
graph []  [(x,y)] == edge x y
graph vs  es      == overlay (vertices vs) (edges es)

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

fromAdjacencyList []                                  == empty
fromAdjacencyList [(x, [])]                           == vertex x
fromAdjacencyList [(x, [y])]                          == edge x y
fromAdjacencyList . adjacencyList                     == id
overlay (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys)

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.

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

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 x y) == False

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

hasVertex x empty            == False
hasVertex x (vertex x)       == True
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 x y)       == True
hasEdge x y . removeEdge x y == const False

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

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

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

edgeCount empty      == 0
edgeCount (vertex x) == 0
edgeCount (edge x y) == 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 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 (star 2 [3,1]) == [(2,1), (2,3)]
edgeList . edges        == nub . sort

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

adjacencyList empty               == []
adjacencyList (vertex x)          == [(x, [])]
adjacencyList (edge 1 2)          == [(1, [2]), (2, [])]
adjacencyList (star 2 [3,1])      == [(1, []), (2, [1,3]), (3, [])]
fromAdjacencyList . adjacencyList == id

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
vertexSet . clique   == Set.fromList

The set of edges of a given graph. Complexity: O((n + m) * log(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 postset of a vertex is the set of its direct successors.

postset x empty      == Set.empty
postset x (vertex x) == Set.empty
postset x (edge x y) == Set.fromList [y]
postset 2 (edge 1 2) == Set.empty

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

path []    == empty
path [x]   == vertex x
path [x,y] == edge x y

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

circuit []    == empty
circuit [x]   == edge x x
circuit [x,y] == edges [(x,y), (y,x)]

The clique on a list of vertices. Complexity: O((n + m) * log(n)) time 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)]

The biclique on a list of vertices. Complexity: O((n + m) * log(n)) time 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,y1), (x2,y2)]

The star formed by a centre vertex and a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

star x []    == vertex x
star x [y]   == edge x y
star x [y,z] == edges [(x,y), (x,z)]

The tree graph constructed from a given Tree data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

The forest graph constructed from a given Forest data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

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

removeVertex x (vertex x)       == empty
removeVertex x . removeVertex x == removeVertex x

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

removeEdge x y (edge 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            == mergeVertices (== x) y

Merge vertices satisfying a given predicate with 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
mergeVertices even 1 (0 * 2)     == 1 * 1
mergeVertices odd  1 (3 + 4 * 5) == 4 * 1

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 x y) == edge (f x) (f y)
gmap id           == id
gmap f . gmap g   == gmap (f . g)

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

Compute the depth-first search forest of a graph.

forest (dfsForest $ edge 1 1)         == vertex 1
forest (dfsForest $ edge 1 2)         == edge 1 2
forest (dfsForest $ edge 2 1)         == vertices [1, 2]
isSubgraphOf (forest $ dfsForest x) x == True
dfsForest . forest . dfsForest        == dfsForest
dfsForest $ 3 * (1 + 4) * (1 + 5)     == [ Node { rootLabel = 1
                                                , subForest = [ Node { rootLabel = 5
                                                                     , subForest = [] }]}
                                         , Node { rootLabel = 3
                                                , subForest = [ Node { rootLabel = 4
                                                                     , subForest = [] }]}]

Compute the topological sort of a graph or return Nothing if the graph is cyclic.

topSort (1 * 2 + 3 * 1)             == Just [3,1,2]
topSort (1 * 2 + 2 * 1)             == Nothing
fmap (flip isTopSort x) (topSort x) /= Just False

Check if a given list of vertices is a valid topological sort of a graph.

isTopSort [3, 1, 2] (1 * 2 + 3 * 1) == True
isTopSort [1, 2, 3] (1 * 2 + 3 * 1) == False
isTopSort []        (1 * 2 + 3 * 1) == False
isTopSort []        empty           == True
isTopSort [x]       (vertex x)      == True
isTopSort [x]       (edge x x)      == False

Compute the condensation of a graph, where each vertex corresponds to a strongly-connected component of the original graph.

scc empty               == empty
scc (vertex x)          == vertex (Set.singleton x)
scc (edge x y)          == edge (Set.singleton x) (Set.singleton y)
scc (circuit (1:xs))    == edge (Set.fromList (1:xs)) (Set.fromList (1:xs))
scc (3 * 1 * 4 * 1 * 5) == edges [ (Set.fromList [1,4], Set.fromList [1,4])
                                 , (Set.fromList [1,4], Set.fromList [5]  )
                                 , (Set.fromList [3]  , Set.fromList [1,4])
                                 , (Set.fromList [3]  , Set.fromList [5]  )]

GraphKL encapsulates King-Launchbury graphs, which are implemented in the Data.Graph module of the containers library. If graphKL g == h then the following holds:

map (getVertex h) (vertices $ getGraph h)                            == Set.toAscList (vertexSet g)
map (\(x, y) -> (getVertex h x, getVertex h y)) (edges $ getGraph h) == edgeList g

Array-based graph representation (King and Launchbury, 1995).

A mapping of Data.Graph.Vertex to vertices of type a.

Build GraphKL from the adjacency map of a graph.

fromGraphKL . graphKL == id

Extract the adjacency map of a King-Launchbury graph.

fromGraphKL . graphKL == id