[Boost-bugs] [Boost C++ Libraries] #3257: boost/graph/prim_minimum_spanning_tree doesn't handle complete graph well

Subject: [Boost-bugs] [Boost C++ Libraries] #3257: boost/graph/prim_minimum_spanning_tree doesn't handle complete graph well
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-07-10 10:41:59

#3257: boost/graph/prim_minimum_spanning_tree doesn't handle complete graph well
--------------------------------+-------------------------------------------
 Reporter:  Li.Long@…           |       Owner:         
     Type:  Bugs                |      Status:  new    
Milestone:  Boost 1.40.0        |   Component:  None   
  Version:  Boost 1.39.0        |    Severity:  Problem
 Keywords:                      |  
--------------------------------+-------------------------------------------
 prim_minimum_spanning_tree handles "undirected" graph.  But when you have
 a complete graph w/ positive weights, and you specify each edge twice,
 instead of once, the return results are different.  An example is
 attached.  Compile with:

 g++ -DSPECIFY_ONCE -I...where-boost-is-installed... mstree_prim.cpp

 gives correct answer, while

 g++ -I...where-boost-is-installed... mstree_prim.cpp

 gives incorrect answer (two spanning trees).

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