Testing Graph Algorithms

This morning I was talking to a guy in Microsoft Research who is pretty famous. He described a neat project he worked on that essentially boiled down to a very complex graph shortest-path problem. That got my mind churning on the general problem of graph algorithms and testing graph algorithm implementations. I hadn’t looked at a graph problem in a while so I decided to code up the more-or-less canonical example: Dijkstra’s algorithm for finding the shortest distance on a graph between a source node and all other nodes. For example, see the graph image below. If the source node is node 0, then the shortest distances to nodes 1, 2, 3, 4, and 5 are 7, 9, 20, 23, and 11 respectively. Even with such a tiny graph it’s easy for a human to make a mistake. I went to Wikipedia, which I find is a pretty good reference for basic algorithm and data structure information, and coded up the algorithm I found there:

Console.WriteLine("\nBegin");
int source = 0;
int[,] graph = new int[,]{
{0,7,9,-1,-1,14},
{7,0,10,15,-1,-1},
{9,10,0,11,-1,2},
{-1,15,11,0,6,-1},
{-1,-1,-1,6,0,12},
{14,-1,2,-1,12,0}
};

int[] shortestPaths = FindShortestPaths(graph, source);
Console.WriteLine("\nGraph is: \n");
DisplayGraph(graph);
Console.WriteLine("\nShortest paths from node " + source + " to other nodes are: \n");
DisplayDistances(shortestPaths);
Console.WriteLine("\nDone");

Where:

static int[] FindShortestPaths(int[,] graph, int source)
{
int[] distance = new int[graph.GetLength(0)];
for (int i = 0; i < distance.Length; ++i)
distance[i] = int.MaxValue;
distance = 0;
int[] previous = new int[graph.GetLength(0)];
for (int i = 0; i < previous.Length; ++i)
previous[i] = -1;
bool[] q = new bool[graph.GetLength(0)];
for (int i = 0; i < q.Length; ++i)
q[i] = true; // true => corresponding node (index) is in q
int u;
int v;
while (!IsEmpty(q))
{
// etc.

See image below. So, what about testing graph algorithms? In some ways this is a classic problem: a large number of inputs, possibility of bad arguments, many assumptions, and so on. Graph algorithms are really important in many fields and if you scan the Wikipedia entry on graph algorithms, you’ll get a good overview.