Routing to self in Dijkstra

Topics: algorithm, bug, graph
Apr 28, 2011 at 10:26 PM

I noticed that when choosing the same node as start and end that Dijkstra always says "no path," even if there is explicitly a self-edge in the graph. I found this by running random tests (code below).

It seems sensible to say "no path" when there is no self-edge, but I'm surprised that it says "no path" when there is an explicit self-edge. Is this by design? Or a potential bug?

The following LinqPad script will exhibit the phenomenon. Be sure to add a reference to the QuickGraph library (F4 in LinqPad), verify by looking at the dump that the self-edge 7->7 is in the graph, then notice that TryGetPath says "False"

void Main()
{
	const int nNodes = 10;
	var graphAsDict = RandomGraphWithSelfEdgeAsDict(nNodes).Dump("graphAsDict: Random graph as Dict");
	
	var velg1 = graphAsDict.ToVertexAndEdgeListGraph(
		kv => Array.ConvertAll<int, SEquatableEdge<int>>(
			kv.Value.ToArray(),
			v => new SEquatableEdge<int>(kv.Key, v))).Dump("velg1: Vertex and Edge-List Graph");

	Func<SEquatableEdge<int>, double> edgeCost = (edge => 1.0D);
	
//	int start = new Random(Guid.NewGuid().GetHashCode()).Next(1, nNodes + 1).Dump("start point");
//	int end = new Random(Guid.NewGuid().GetHashCode()).Next(1, nNodes + 1).Dump("end point");

	int start = 7.Dump("start point");
	int end = 7.Dump("end point");

	var algo = new DijkstraShortestPathAlgorithm<int, SEquatableEdge<int>>(velg1, edgeCost);
	var predecessors = new VertexPredecessorRecorderObserver<int, SEquatableEdge<int>>();
	using (predecessors.Attach(algo))
	{
		algo.Compute(start);
		IEnumerable<SEquatableEdge<int>> path;
		if (predecessors.TryGetPath(end, out path).Dump("TryGetPath"))
			path.Dump("path");
	}
}

public static int[] RandomPermutation(Random ran, int n)
{
	var r = Enumerable.Range(1, n).ToArray();
	for (var i = 0; i < n - 1; i++)
	{
		var k = ran.Next(i + 1, n);
		var t = r[i];
		r[i] = r[k];
		r[k] = t;
	}
	return r;
}

public static Dictionary<int, IEnumerable<int>> 
	RandomGraphWithSelfEdgeAsDict(int nNodes)
{
	var ran = new Random(Guid.NewGuid().GetHashCode());
	var result = new Dictionary<int, IEnumerable<int>>();
	
	for (var j = 1; j <= nNodes; j++)
	{
		var k = ran.Next(0, nNodes);
		var cs = RandomPermutation(ran, nNodes);
		result[j] = cs.Take(k);
	}
	
	// Now put in a self-edge on purpose, say 7 to 7
	if (!result[7].Contains(7))
	{
		var _ = result[7].ToList();
		_.Add(7);
		result[7] = _;
	}
	
	return result;
}
Jun 28, 2012 at 7:58 AM

I noticed the same behavior in my bidirectional graph. I am not a graph expert to know whether this is expected behavior or not. I can of course assume the path to self always exists but it is not exactly what I need. Have you found any explanation/solution to this? BR, Tine