Sunday 7 June 2009

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.

6 comments:

  1. There's nothing particular in your datatype choice that seems to restrict you to only graphs - or in the terminology I'd use a simplicial 1-skeleton...

    You see any use in generalizing the datatype to simplicial complexes in general?

    ReplyDelete
  2. Will you provide a package for hackage? It's looks very interesting

    ReplyDelete
  3. Mikael,

    Yes you're right, the datatype is appropriate for any set system. So elsewhere in the library, we have the equivalent datatypes:

    data Design a = D [a] [[a]] deriving (Eq,Ord,Show)

    data Hypergraph a = H [a] [[a]] deriving (Eq,Ord,Show)

    I did think about just using Hypergraph for everything, but I decided that it was clearer to have different types - for example, there are some functions that make sense for graphs, but not for designs - having different types prevents some programmer errors.

    I haven't given much thought to simplicial complexes. Can you recommend a good source for *algorithmic* algebraic topology?

    ReplyDelete
  4. Alex,

    The zipfile on the linked website contains, I believe, a working .cabal file. I have been able to configure, build, and install locally. However, I have had trouble getting gzip and tar working on my windows machine, and hence haven't been able to sdist for hackage.

    ReplyDelete
  5. DavidA: My favourites are Zomorodian [1] and Kozlov [2]. Also, we're currently starting up a project joint with Stanford and INRIA to build an algorithmic algebraic topology library similar to CGAL.


    [1] http://www.amazon.com/Computing-Cambridge-Monographs-Computational-Mathematics/dp/0521136091/ref=sr_1_1?ie=UTF8&s=books&qid=1244794934&sr=8-1
    [2] http://www.amazon.com/Combinatorial-Algebraic-Algorithms-Computation-Mathematics/dp/3540730516/ref=sr_1_1?ie=UTF8&s=books&qid=1244794987&sr=1-1

    It's still not very ripe as a field - but that only makes it more fun! :-)

    ReplyDelete
  6. 2David:
    You can install MinGW that contains many unix tools, including gzip + tar

    ReplyDelete

Followers