[Boost-bugs] [Boost C++ Libraries] #3972: Broken support for unordered sets and multisets in adjacency_list graphs

Subject: [Boost-bugs] [Boost C++ Libraries] #3972: Broken support for unordered sets and multisets in adjacency_list graphs
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2010-03-03 14:02:47

#3972: Broken support for unordered sets and multisets in adjacency_list graphs
-----------------------------------------------------------------------------+
 Reporter:  Thomas Claveirole <thomas@…>                                     |       Owner:  asutton
     Type:  Bugs                                                             |      Status:  new    
Milestone:  Boost 1.43.0                                                     |   Component:  graph  
  Version:  Boost Development Trunk                                          |    Severity:  Problem
 Keywords:  graph adjacency_list unordered unordered_set unordered_multiset  |  
-----------------------------------------------------------------------------+
 Hello,

 The support for adjacency_list graphs using unordered sets and
 multisets is currently broken.  I will attach a patch that solves this
 issues in this report.

 Basically, several compounds are missing and there is a bug in
 edge_range().  Here is a detailed description of the issue:

 * Container traits

 container_traits, container_category, and iterator_stability
 specializations and overrides are missing for unordered_multiset
 and unordered_multimap, in pending/container_traits.hpp.


 * parallel_edge_traits

 parallel_edge_traits specializations are missing for
 hash_multisetS and hash_multimapS, in graph/adjacency_list.hpp.

 * edge_range

 edge_range() uses std::equal_range() on the node's out edge list.
 std::equal_range() expects its input to be ordered in ascending
 order.  This precondition fails when using an unordered set or
 multiset for storing the edges.

 As a solution, the proposed patch uses std::equal_range() by
 default, except on associative containers, for which it uses the
 container's equal_range() method (the equal_range() method is
 a requirement of associative containers).

 Regards,
 Thomas Claveirole

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