[Boost-bugs] [Boost C++ Libraries] #4737: Documentation for Prim MST concerning distance_map is wrong

Subject: [Boost-bugs] [Boost C++ Libraries] #4737: Documentation for Prim MST concerning distance_map is wrong
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-10-14 15:32:36

#4737: Documentation for Prim MST concerning distance_map is wrong
-----------------------------------+----------------------------------------
 Reporter:  nicoe@…                |       Owner:  asutton
     Type:  Bugs                   |      Status:  new    
Milestone:  To Be Determined       |   Component:  graph  
  Version:  Boost 1.44.0           |    Severity:  Problem
 Keywords:                         |  
-----------------------------------+----------------------------------------
 In the documentation for prim_minimum_spanning_tree, you can read at
 distance_map:

  The shortest path weight from the source vertex s to each vertex in the
 graph g is recorded in this property map. The shortest path weight is the
 sum of the edge weights along the shortest path.

 I would say this is wrong. I claim that the prim_minimum_spanning_tree
 stores original edgeweights in the distance map. Precisely, an entry i in
 the distance map corresponds to the edgeweight of the edge from vertex i
 to its predecessor in the MST.

 Example:
 Given a undirected graph on the vertex set {0,1,2} with edges (0,1,2),
 (0,2,3), (1,2,4) (to be read as vertex, vertex, weight).
 The output of prim MST called with parameters root_vertex(1) concerning
 the distance map is (2,0,3).
 According to the documentation it schould be (2,0,5).

 See attached example for details

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/4737>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.