[Boost-bugs] [Boost C++ Libraries] #3151: Patch to graph library iterator handling

Subject: [Boost-bugs] [Boost C++ Libraries] #3151: Patch to graph library iterator handling
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-06-08 20:00:12

#3151: Patch to graph library iterator handling
-------------------------------------+--------------------------------------
 Reporter:  tkeitt_at_[hidden]         |       Owner:  dgregor
     Type:  Patches                  |      Status:  new    
Milestone:  Boost 1.40.0             |   Component:  graph  
  Version:  Boost Development Trunk  |    Severity:  Problem
 Keywords:  graph, iterator          |  
-------------------------------------+--------------------------------------
 I have developed some graph classes that generate edge lists on-the-fly
 (queried from a database). This means that my iterator ranges are not
 stable across calls to edges or out_edges. I have therefor altered the
 graph library to avoid comparing iterator across calls to vertices, edges,
 out_edges, etc.

 A common example occurs in a number of locations in the graph library:

 edge_iterator ei;
 for ( ei = out_edges(v, g).first, ei != out_edges(v, g).second, ++ei)
 {
   ...
 }

 Notice that ei is compared to subsequent calls to out_edges (this breaks
 my code).

 A synonymous change is to re-write this as:

 edge_iterator ei, e_end;
 for (tie(ei, e_end) = out_edges(v, g); ei != e_end; ++ei)
 {
   ...
 }

 The behavior of the code is not changed and is perhaps a bit easier to
 read. This version will not break my code because ei is only compared to
 e_end.

 I have tried to remove all occurrences of comparing iterators to
 (vertices|edges|out_edges|...)(...).second and replace them with code that
 only compares iterators from the same call to
 (vertices|edges|out_edges|...).

 I also added a file called pair_util.hpp which defines templates that make
 it easy to test whether members of a pair are equal or not equal.

 I am attaching a patch. I have run the graph regression tests and all pass
 except one that does not pass before the patch.

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