Problem with UnidirectedGraph and UndirectedDijkstraShortestPathAlgorithm

Topics: algorithm, graph
Aug 7, 2009 at 8:59 PM

I'm trying out QuickGraph in a distance product we have. I got to work with an AdjacencyGraph but our connections are both ways so I just added two edges for each connection, I would like to avoid this, but cannot quite figure it out, please help:

This works on a AdjacencyGraph

DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>>();
predecessorObserver.Attach(dijkstra);
VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
distObserver.Attach(dijkstra);
dijkstra.Compute(StartP);

This does not work on a UndirectedGraph

UndirectedDijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new UndirectedDijkstraShortestPathAlgorithm<string, Edge<string>>(graph, AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>();
predecessorObserver.Attach(dijkstra);
VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
distObserver.Attach(dijkstra);
dijkstra.Compute(StartP);

I get a error:

Error    1    The best overloaded method match for 'QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string,QuickGraph.Edge<string>>.Attach(QuickGraph.Algorithms.ITreeBuilderAlgorithm<string,QuickGraph.Edge<string>>)' has some invalid arguments    C:\projects\Shipping\EFDistance\DistanceServerModule\DistanceServerModule.cs    655    13    DistanceServerModule

What should I do?

 

Coordinator
Aug 10, 2009 at 6:15 AM

You need to use UndirectedVertexPredecessorRecorderObserver instead.

Aug 10, 2009 at 8:23 AM

Great, it worked. thank you !

Aug 17, 2009 at 2:56 PM

Hmm.. very strange. I have a new problem with the Undirected graph. I'm getting the same distance from the Undirected graph as from the AdjacencyGraph(with all edges duplicated from->to to->from), but i'm getting two different paths with TryGetPath. The Undirected graph gives me a path thats not valid. It looks like there are steps missing (Compared to the Adjecencygraph)?

What can I do to debug this ?

Coordinator
Aug 23, 2009 at 2:49 PM

I'll need a,repro