[boost] [graph] dijkstra_shortest_paths_no_color_map works by accident

Subject: [boost] [graph] dijkstra_shortest_paths_no_color_map works by accident
From: Jan Hudec (bulb_at_[hidden])
Date: 2012-10-22 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 no-op. Correct
"not-in-heap" 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]>