Graph's Tour / Dijkstra's parent nodes

[JDKunkMailing@…]

In the tour (http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/quick_tour.html), the last step has me going through and finding all the parents of nodes in Dijkstra algorithm. However, the way the default constructor of Vertex() was set up, it could not find vertex 0 when the parent is 0. Specifically, p[*vi] == Vertex() returned true, when the parent was zero and when there is no parent.

There are two ways to look at this problem.

First, it is not a bug. Whoever uses the library should get used to working around this.

Second, the default Vertex() should be denoted with an invalid id such that no valid vertex can be Vertex().

I would prefer the latter, or another way to work around this issue.

Vertex is typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

I used MSVC 9.0, Win32(Windows7), Intel x2 processors, ... what else?

• Jeff Kunkel

[Jeremiah Willcock]

(In [56563]) Changed from Vertex() to null_vertex() in examples; refs #3506

[Jeremiah Willcock]

This does appear to be a bug in the example -- there is a special null_vertex() value that is used to mark invalid vertices. I changed the code to use that, but it is probably not a good idea to look at the predecessor of the start vertex anyway. I do not believe the visitor ever sets the predecessor since it never has an edge coming in that is discovering the start vertex.

[JDKunkMailing@…]

Replying to jewillco:

This does appear to be a bug in the example -- there is a special null_vertex() value that is used to mark invalid vertices. I changed the code to use that, but it is probably not a good idea to look at the predecessor of the start vertex anyway. I do not believe the visitor ever sets the predecessor since it never has an edge coming in that is discovering the start vertex.

I discovered that if a parent does not exist, it does not set anything to the property map. Therefore, algorithms (maybe just dijkstra) will not change an element if there is nothing to set it to. I recommend that all users should place default values into the analysis from algorithms, but this is just good application programming practice.