
Boost : 
Subject: [boost] [graph] dijkstra_shortest_paths_no_color_map works by accident
From: Jan Hudec (bulb_at_[hidden])
Date: 20121022 15:56:58
Hello,
I've been writing custom version of Dijkstra's shortes path algorithm because
of specific constraints and I was using the
dijkstra_shortest_paths_no_color_map function as template. And I've notices
that it only works by accident:
The inner loop (I've had 1.51, but there is no change in trunk) goes like
this:
BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) {
// [visitor, negative check, not interesting now]
// Extract the neighboring vertex and get its distance
Vertex neighbor_vertex = target(current_edge, graph);
Distance neighbor_vertex_distance = get(distance_map, neighbor_vertex);
bool is_neighbor_undiscovered =
!distance_compare(neighbor_vertex_distance, distance_infinity);
Considering the case when the vertex is not discovered:
neighbor_vertex_distance = infinity
is_neighbor_undiscovered = true
// Attempt to relax the edge
bool was_edge_relaxed = relax(current_edge, graph, weight_map,
predecessor_map, distance_map,
distance_weight_combine, distance_compare);
Since any sensible distance is less than infinity, the relax function will
return *true*:
was_edge_relaxed = true
if (was_edge_relaxed) {
vertex_queue.update(neighbor_vertex);
So this gets executed. But the vertex is not in the queue! OOPS!
The code however executes successfuly. This is because the index_in_heap
property map given to the d_ary_heap_indirect is initialized to 0. But 0 is
correct index pointing to top and updating top is a noop. Correct
"notinheap" value would be 1 (and that's what the queue stores in pop()).
visitor.edge_relaxed(current_edge, graph);
} else {
visitor.edge_not_relaxed(current_edge, graph);
}
if (is_neighbor_undiscovered) {
visitor.discover_vertex(neighbor_vertex, graph);
vertex_queue.push(neighbor_vertex);
Here finally comes the push. Obviously it should have been first.
Curiously this visitor callback is called before the queue operations while
the edge_relaxed above is called after. Is there any reason for this
particular order of operations? (Obviously fixing the code would be easier
if the order of callbacks didn't matter)
}
} // end out edge iteration
Should this be fixed? Are there any risks doing so?
 Jan 'Bulb' Hudec <bulb_at_[hidden]>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk