[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.

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:04 UTC