Simple graphs with Math.Combinatorics.Graph

Hello again.

In this blog I'll be talking about my Haskell for Maths library - the maths behind it, how the code works, and how to use it. I thought we'd begin with something easy, (simple) graphs. Here are a couple of examples:

Well actually, these are really the same graph - the cube. You see, we're not really interested in the spatial arrangement of the vertices and edges, but only in the pattern of connectivity between them. These graphs have the same vertices (the numbers 0 to 7), and you can check that the edges connect the same pairs of vertices.

So a graph is defined as a pair (vs, es) where vs is a set of vertices, labelled by integers, say, and es is a set of edges - where an edge is a set of two vertices. In Haskell:

data Graph a = G [a] [[a]] deriving (Eq,Ord,Show)

For example (jumping ahead a little), the graph shown above is:

> :load Math.Combinatorics.Graph
> q 3
G [0,1,2,3,4,5,6,7] [[0,1],[0,2],[0,4],[1,3],[1,5],[2,3],[2,6],[3,7],[4,5],[4,6],[5,7],[6,7]]

Although we will often use integers to label the vertices, notice that the Graph data type permits us to use other types. This will turn out to be extremely useful.

Okay, so whenever we define a new type of mathematical object, one of the first things we want to know is if there are any standard families of such objects. Here are a few standard graphs.



(Note that from now on I usually won't label the vertices. When studying graphs, what we're really interested in is the underlying structure of vertices connected by edges. The labels on the vertices are just scaffolding.)

The graph on the left is c 5, the cyclic graph on 5 vertices.

c n = graph (vs,es) where
    vs = [1..n]
    es = L.insert [1,n] [[i,i+1] | i <- [1..n-1]]

Just a little note about this. For convenience, we insist that the lists of vertices and edges are always in ascending order, and that each edge (list of two vertices) is itself in ascending order. The "graph" constructor checks this for us.

The middle graph above is k 5, the complete graph on 5 vertices, in which every pair of vertices is connected by an edge.

k n = graph (vs,es) where
    vs = [1..n]
    es = [[i,j] | i <- [1..n-1], j <- [i+1..n]]

The graph on the right is the complete bipartite graph kb 2 3, in which each of two vertices on the left is connected to each of three vertices on the right. Here we have an example where it is useful to be able to use types other than Integer to label our vertices:

kb' m n = graph (vs,es) where
    vs = map Left [1..m] ++ map Right [1..n]
    es = [ [Left i, Right j] | i <- [1..m], j <- [1..n] ]

kb m n = to1n $ kb' m n

The function "to1n" converts a graph over some other type to a graph over the integers.

> kb' 2 3
G [Left 1,Left 2,Right 1,Right 2,Right 3]
   [[Left 1,Right 1],[Left 1,Right 2],[Left 1,Right 3],
    [Left 2,Right 1],[Left 2,Right 2],[Left 2,Right 3]]

> kb 2 3
G [1,2,3,4,5] [[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]

There are a few more standard families of graphs, and some new from old constructions, defined in the Math.Combinatorics.Graph module. See the code for details.

That's about all I've got time for just now. What I'm heading for is to be able to study the symmetries (automorphisms) of graphs. The code is in Math.Combinatorics.GraphAuts, if you want a sneak preview - otherwise you'll just have to wait.