Re: [boost] Graph/Shortest Path usage question

From: Andrew Myers (andrew_at_[hidden])
Date: 2001-01-05 00:05:32

Jeremy Siek wrote:
> This event point is the "on_discover" event in the BGL algorithm: the
> point at which the node is removed from the priority queue (because it is
> the node with minimum distance). In Andrew's early post he asked if the
> "finish" event would work. It would work, though by that time a little
> extra (unnecesary) processing has occurred, namely all the outgoing edges
> have been added to the queue.

And here's some output from BGL to illustrate the point and, I hope, draw this
discussion to a close. Thanks for everyone's input.

Here is a directed graph (the same one in the examples
lib/graph/examples/visitor.cpp)

  // Original graph
  //                               +---+ 
  //                               v   |
  //          0 ------> 2 -------> 1 --+
  //          ^          \       /^ ^   
  //          |           \     //   \
  //          |            \   //     \
  //          |             v v/       \
  //          |              3 -------> 4
  //          |                         |
  //          +-------------------------+

When the breadth_first_search algorithm is run on this graph, using event
vistors (adapted to a bfs_visitor), we get this oputput.

Breadth First Search categorized directed graph
discovered: 0
  tree edge: 0 --> 2
finished: 0
discovered: 2
  tree edge: 2 --> 1
  tree edge: 2 --> 3
finished: 2
discovered: 1
  cycle edge: 1 --> 1
  cycle edge: 1 --> 3
finished: 1
discovered: 3
  cycle edge: 3 --> 1
  tree edge: 3 --> 4
finished: 3
discovered: 4
  cycle edge: 4 --> 0
  cycle edge: 4 --> 1
finished: 4

The tree and cycle edges are not as important as the vertex discover and finish
times.

Now add some weights to the graph edges.

  // Original graph with weights
  //
  //                               +---+ 
  //              (1)       (7)    v   |(2)
  //          0 ------> 2 -------> 1 --+
  //          ^          \       /^ ^   
  //          |        (3)\  (1)//   \(1)
  //          |            \   //(2)  \
  //          |             v v/       \
  //          |              3 -------> 4
  //          |                  (1)    |
  //          |                         |
  //          +-------------------------+  
  //                      (1)   
  //

Run the dijkstra_shortest_paths algorithm over this, using same vertex event
visitors (adapted this time to a ucs_visitor) and we get this output.

Dijkstra shortest paths
discovered: 0
  edge relaxed: 0 --> 2
finished: 0
discovered: 2
  edge relaxed: 2 --> 1
  edge relaxed: 2 --> 3
finished: 2
discovered: 3
  edge relaxed: 3 --> 1
  edge relaxed: 3 --> 4
finished: 3
discovered: 4
finished: 4
discovered: 1
finished: 1

Distances from start vertex:
  distance(0) = 0
  distance(1) = 6
  distance(2) = 1
  distance(3) = 4
  distance(4) = 5

Notice the different order in which the vertices are discovered. Vertex 1 for
example is discovered earlier in the breadth first search than the dijkstra
algorithm.

As Jeremey says, once the vertex is removed from the queue (of unvisited
vertices) it is "discovered" and at that point we can be sure no shorter path to
that vertex exists. This we can use the OnVertexDiscover event as the basis for
early termination of the algorithm.

-- 
  Andrew Myers                                                      I-SiTE 
  Senior Software Engineer                                3D Laser Imaging
  Phone: [phone]                  
  Fax  : [phone]                         
  Email: andrew_at_[hidden]                   http://www.isite3d.com.au