Documentation

A graph is mathematically defined as a set of vertexes and a set of edges, where an edge is a set of two elements from the set of vertexes. I.e., if \(G = (V, E)\), where \(E \subseteq \{ \{v_1, v_2\} \,|\, v_1 \in V, v_2 \in V\}\), then \(G\) is a graph.

The following is an example of a graph, with vertexes represented as circles and edges represented as lines.

Notes

A vertex in a graph.

In general, vertexes can be anything. For these problems, vertexes will be integers.

An edge in a graph.

We will only deal with undirected graphs. I.e.,

Edge (u, v) == Edge (v, u)

There are many ways to represent graphs in Haskell. For example, the example graph can be represented by variables including their adjacent vertexes as values:

>>> :{
let v1 = Var () [v2, v4]
    v2 = Var () [v1, v3, v4]
    v3 = Var () [v2, v4]
    v4 = Var () [v1, v2, v3, v5]
    v5 = Var () [v4]
:}

We will not be using this representation of graphs further.

Tying the knot

>>> :{
let v1  = Var 1 [v2]
    v2  = Var 2 [v3]
    v3  = Var 3 [v1']
    v1' = Var 1 [v3]
:}

>>> :{
let v1 = Var 1 [v2]
    v2 = Var 2 [v1]
:}

Graphs can also be represented by the lists of its vertexes and edges. This is close to the standard mathematical definition of a graph.

For example, the example graph can be represented as:

>>> Lists ([1, 2, 3, 4, 5], [(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5)])
Lists ...

A common approach to representing graphs are with adjacency lists. As the name implies, for each vertex it lists its adjacent vertexes

For example, the example graph can be represented as:

>>> Adjacency [(1, [2, 4]), (2, [1, 3, 4]), (3, [2, 4]), (4, [1, 2, 3, 5]), (5, [4])]
Adjacency ...

The previous approaches can be verbose and error-prone for humans to use.

An easier way for humans is to use paths of vertexes to represent both the vertexes and edges. Within a path is implicitly an edge between consecutive vertexes. E.g., a path [a, b, c, ...] means there are vertexes a, b, c, ... and edges (a, b), (b, c), ... There will be as many paths as required to represent all edges in the graph.

For example, the example graph can be represented as:

>>> Paths [[1, 2, 3, 4, 5], [1, 4], [2, 4]]
Paths ...

DOT graphs

graph {
  1 -- 2 -- 3 -- 4 -- 5
  1 -- 4
  2 -- 4
}

Represents a graph with a map where a vertex is a key and the set of its neighbors is the value.

This is basically an indexed version of adjacency lists. This representation may be the easiest for graph functions to use, and we will use it as the default representation of graphs.

For example, the example graph can be represented as:

>>> :{
G $ Map.map Set.fromList $ Map.fromList
  [ (1, [2, 4])
  , (2, [1, 3, 4])
  , (3, [2, 4])
  , (4, [1, 2, 3, 5])
  , (5, [4])
  ]
:}
G ...

Checks whether the given set of vertexes and edges can form a graph.

I.e., the vertexes in edges must be in the set of vertexes.