HoffmanPavleyRankedShortestPathAlgorithm

Topics: algorithm
Jun 16, 2011 at 2:14 PM

I am completely new to this graph theory stuff so be gentle!

I tried rewriting some code I have just done (for an interview test) to calculate all routes between two nodes that do not revisit a node using QuickGraph.

I used the above algorithm but in some cases it seems to returns fewer paths than my code did (as well as writing to the Console!!).

Am I using the wrong algorithm or misusing it?

Here is my old code showing the edges (I'm sure you experts can picture all this in your head - me I get a pad and pencil) and the code snippet doing the calc

connectionAB = new Connection(stationA, stationB, 3);
connectionBA = new Connection(stationB, stationA, 3);
connectionAD = new Connection(stationA, stationD, 6);
connectionBC = new Connection(stationB, stationC, 7);
connectionCD = new Connection(stationC, stationD, 8);
connectionDE = new Connection(stationD, stationE, 9);
connectionED = new Connection(stationE, stationD, 9);
connectionDC = new Connection(stationD, stationC, 9);
connectionDB = new Connection(stationD, stationB, 5);
connectionCE = new Connection(stationC, stationE, 3);

var a = new HoffmanPavleyRankedShortestPathAlgorithm<Station, Connection>(graph.ToBidirectionalGraph(), GetConnectionCost);
a.Compute(start, end);

foreach(var path in a.ComputedShortestPaths)
{
	yield return new RouteSummary(path.ToList());
}

 

This is the output that is common to my old code and the new HoffmanPavley stuff above for all paths from :

(A) -> 3 -> (B) : 3
(A) -> 6 -> (D) -> 5 -> (B) : 11
(A) -> 3 -> (B) -> 7 -> (C) : 10
(A) -> 6 -> (D) -> 9 -> (C) : 15
(A) -> 6 -> (D) -> 5 -> (B) -> 7 -> (C) : 18
(A) -> 6 -> (D) : 6
(A) -> 3 -> (B) -> 7 -> (C) -> 8 -> (D) : 18
(A) -> 3 -> (B) -> 7 -> (C) -> 3 -> (E) -> 9 -> (D) : 22
(A) -> 6 -> (D) -> 9 -> (E) : 15
(A) -> 3 -> (B) -> 7 -> (C) -> 3 -> (E) : 13
(A) -> 6 -> (D) -> 9 -> (C) -> 3 -> (E) : 18

 

But my code also returns these paths:
(A) -> 6 -> (D) -> 5 -> (B) -> 7 -> (C) -> 3 -> (E) : 21
(A) -> 3 -> (B) -> 7 -> (C) -> 8 -> (D) -> 9 -> (E) : 27

 

which appear perfectly valid to me.

 

Any ideas?

Jun 16, 2011 at 7:41 PM
The (non-QuickGraph) code I have looks like this:
 
		static IEnumerable<IList<IGraphNode>> FindAllNodesBetweenCore(IGraph graph, IGraphNode start, IGraphNode end, IList<IGraphNode> pathSoFar)
		{
			pathSoFar = new List<IGraphNode>(pathSoFar) { start };

			if (start == end)
			{
				yield return pathSoFar;
			}
			else
			{
				foreach(var childNode in graph.FindAdjacentNodesFrom(start))
				{
					// Prevent cycles
					if (pathSoFar.Contains(childNode)) continue;

					foreach(var newPath in FindAllNodesBetweenCore(graph, childNode, end, pathSoFar))
					{
						yield return newPath;
					}
				}
			}
		}

How can I achieve the same in QuickGraph?