[Support] ShortestPathsDijkstra unexpectedly returning null

[rurounijones]

Describe the bug

New to the library (and thanks for updating a venerable one and saving it from bitrot!)

Attempting to use the ShortestPathsDijkstra as detailed in https://github.com/KeRNeLith/QuikGraph/wiki/Dijkstra-Shortest-Distance-Example using the extensions method is returning null given a valid (I believe) graph.

Using Quikgraph v2.2.0 via nuget.

To Reproduce Steps to reproduce the behavior:

1. Run the C# code in https://gist.github.com/rurounijones/3cc32a3d69741d49e3042fb6b0f69ef9 Alternatively clone Visual Studio project repository from https://github.com/rurounijones/graph-test and run

Expected behavior Application outputs Pads 14 through 20 to Bravo / Delta Junction via taxiways Charlie, Alpha, Delta

Actual Behaviour Application outputs Path was null.

Screenshots

Command-line Output

Graph Definition
-------------------------------------
digraph G {
0 [label="Runway 4"];
1 [label="Alpha / Delta Junction"];
2 [label="Alpha / Charlie Junction"];
3 [label="Bravo / Delta Junction"];
4 [label="Pads 14 to 20"];
0 -> 1 [label="Taxiway Alpha : Cost 1"];
1 -> 2 [label="Taxiway Alpha : Cost 1"];
1 -> 3 [label="Taxiway Delta : Cost 1"];
2 -> 4 [label="Taxiway Charlie : Cost 1"];
}
-------------------------------------
Shortest Path Test
Getting Path
Path was null
Press Enter to close

Additional context I am using http://webgraphviz.com/ to convert the dot notation to a visible graph to verify that the graph is properly constructed.

[KeRNeLith]

Hello,

I ran your code and I noticed that it seems normal to have a null path there. Let me explain why. You are using a BidirectionalGraph which is in fact a directed graph meaning A -> B is not the same as B -> A. Adding the first edge will not induce the second one, you need to add both if it's the intended behavior.

So there the algorithm returns no path because in fact there is no path between "Pads 14 to 20" and "Bravo / Delta Junction".

I put the reprensation of your graph from web graphviz:

There is no path between your 2 vertices. Adding the two edges in red would allow you to get a path between your root and target vertices.

[rurounijones]

Thanks for the information. I thought Bidirectional was QuickGraph terminology for Undirected.

After you pointed out this is not the case I went to the wiki again and realised I had missed the Show 37 more pages link at the bottom of the page listing so I never saw the UndirectedGraph page. (In fact I had missed a lot of wiki pages).

All I saw was the AdjacencyGraph and BidirectionalGraph which was further reinforced by the Creating-Graphs page only talking about AdjacencyGraph and the AdjacencyGraph linking only to the BidirectionalGraph page.

My bad for not going through the wiki in more detail.

[KeRNeLith]

No problem. The wiki is certainly not perfect. For sure it does not cover the full potential of the QuikGraph libraries. Bidirectional is a kind of graph where you have easy access to in and out edges, while adjacency is just for out edges. Undirected graphs have a different naming, we talk about adjacent edges and are in fact not directed.

Form time to time I'm working on a little sample project for QuikGraph that would help showcasing some code samples. Meanwhile, there are unit tests that are a great place to see all features, but it's a bit harder to read. My sample project will have the form of "unit tests" for easy running, and will be a lot easier to read, without assertions just to give a quick example.

I encourage you to maybe open the QuikGraph to have a look what is available. The way the solution is structured should make it not too hard to extract information you need. I'm just putting there the kind of graphs available in QuikGraph for now.

Also, even if it contains a lot of stuff the generated documentation may also help you a bit. The library is fully commented which help to have the generated documentation more useful.

Don't hesitate to contribute or give feedbacks, everything is welcomed.