[Boost-commit] svn:boost r64074 - in trunk/boost: graph/detail pending

Subject: [Boost-commit] svn:boost r64074 - in trunk/boost: graph/detail pending
From: jewillco_at_[hidden]
Date: 2010-07-16 14:12:30

Author: jewillco
Date: 2010-07-16 14:12:29 EDT (Fri, 16 Jul 2010)
New Revision: 64074
URL: http://svn.boost.org/trac/boost/changeset/64074

Log:
Disabled edge_range() for adjacency list graphs that do not guarantee equal_range() to work on their out edge lists; cleaned up edge() for all adjacency lists
Text files modified: 
   trunk/boost/graph/detail/adjacency_list.hpp |    58 +++++---------------------------        
   trunk/boost/pending/container_traits.hpp    |    69 +++++++++++++++++++++++++++++++++++++-- 
   2 files changed, 75 insertions(+), 52 deletions(-)

Modified: trunk/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/detail/adjacency_list.hpp	(original)
+++ trunk/boost/graph/detail/adjacency_list.hpp	2010-07-16 14:12:29 EDT (Fri, 16 Jul 2010)
@@ -1505,51 +1505,6 @@
 
       typedef typename Config::global_edgelist_selector
         global_edgelist_selector;
-
-      //    protected:
-
-      // The edge_dispatch() functions should be static, but
-      // Borland gets confused about constness.
-
-      // O(E/V)
-      inline std::pair<edge_descriptor,bool>
-      edge_dispatch(const AdjList& g,
-                    vertex_descriptor u, vertex_descriptor v,
-                    boost::allow_parallel_edge_tag) const
-      {
-        bool found;
-        const typename Config::OutEdgeList& el = g.out_edge_list(u);
-        typename Config::OutEdgeList::const_iterator
-          i = std::find_if(el.begin(), el.end(),
-                           detail::target_is<vertex_descriptor>(v));
-        found = (i != g.out_edge_list(u).end());
-        if (found)
-          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
-                                true);
-        else
-          return std::make_pair(edge_descriptor(u, v, 0), false);
-      }
-      // O(log(E/V))
-      inline std::pair<edge_descriptor,bool>
-      edge_dispatch(const AdjList& g,
-                    vertex_descriptor u, vertex_descriptor v,
-                    boost::disallow_parallel_edge_tag) const
-      {
-        bool found;
-        /* According to the standard, this should be iterator, not const_iterator,
-           but the VC++ std::set::find() const returns const_iterator.
-           And since iterator should be convertible to const_iterator, the
-           following should work everywhere. -Jeremy */
-        typename Config::OutEdgeList::const_iterator
-          i = g.out_edge_list(u).find(StoredEdge(v)),
-          end = g.out_edge_list(u).end();
-        found = (i != end);
-        if (found)
-          return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
-                                true);
-        else
-          return std::make_pair(edge_descriptor(u, v, 0), false);
-      }
     };
 
     template <class Config, class Base>
@@ -1630,9 +1585,16 @@
          const adj_list_helper<Config, Base>& g_)
     {
       typedef typename Config::graph_type Graph;
-      typedef typename Config::edge_parallel_category Cat;
-      const Graph& g = static_cast<const Graph&>(g_);
-      return g_.edge_dispatch(g, u, v, Cat());
+      typedef typename Config::StoredEdge StoredEdge;
+      const Graph& cg = static_cast<const Graph&>(g_);
+      typedef typename Config::out_edge_iterator out_edge_iterator;
+      const typename Config::OutEdgeList& el = cg.out_edge_list(u);
+      typename Config::OutEdgeList::const_iterator it = graph_detail::
+        find(el, StoredEdge(v));
+      return std::make_pair(
+               typename Config::edge_descriptor
+                     (u, v, (it == el.end() ? 0 : &(*it).get_property())),
+               (it != el.end()));
     }
 
     template <class Config, class Base>

Modified: trunk/boost/pending/container_traits.hpp
==============================================================================
--- trunk/boost/pending/container_traits.hpp	(original)
+++ trunk/boost/pending/container_traits.hpp	2010-07-16 14:12:29 EDT (Fri, 16 Jul 2010)
@@ -458,7 +458,67 @@
     return push_dispatch(c, v, container_category(c));
   }
 
+  // Find
+  template <class Container, class Value>
+  typename Container::iterator
+  find_dispatch(Container& c,
+                const Value& value,
+                container_tag)
+  {
+    return std::find(c.begin(), c.end(), value);
+  }
+
+  template <class AssociativeContainer, class Value>
+  typename AssociativeContainer::iterator
+  find_dispatch(AssociativeContainer& c,
+                const Value& value,
+                associative_container_tag)
+  {
+    return c.find(value);
+  }
+
+  template <class Container, class Value>
+  typename Container::iterator
+  find(Container& c,
+       const Value& value)
+  {
+    return find_dispatch(c, value,
+                         graph_detail::container_category(c));
+  }
+
+  // Find (const versions)
+  template <class Container, class Value>
+  typename Container::const_iterator
+  find_dispatch(const Container& c,
+                const Value& value,
+                container_tag)
+  {
+    return std::find(c.begin(), c.end(), value);
+  }
+
+  template <class AssociativeContainer, class Value>
+  typename AssociativeContainer::const_iterator
+  find_dispatch(const AssociativeContainer& c,
+                const Value& value,
+                associative_container_tag)
+  {
+    return c.find(value);
+  }
+
+  template <class Container, class Value>
+  typename Container::const_iterator
+  find(const Container& c,
+       const Value& value)
+  {
+    return find_dispatch(c, value,
+                         graph_detail::container_category(c));
+  }
+
   // Equal range
+#if 0
+  // Make the dispatch fail if c is not an Associative Container (and thus
+  // doesn't have equal_range unless it is sorted, which we cannot check
+  // statically and is not typically true for BGL's uses of this function).
   template <class Container,
             class LessThanComparable>
   std::pair<typename Container::iterator, typename Container::iterator>
@@ -469,21 +529,22 @@
     // c must be sorted for std::equal_range to behave properly.
     return std::equal_range(c.begin(), c.end(), value);
   }
+#endif
 
-  template <class AssociativeContainer, class LessThanComparable>
+  template <class AssociativeContainer, class Value>
   std::pair<typename AssociativeContainer::iterator,
             typename AssociativeContainer::iterator>
   equal_range_dispatch(AssociativeContainer& c,
-                       const LessThanComparable& value,
+                       const Value& value,
                        associative_container_tag)
   {
     return c.equal_range(value);
   }
 
-  template <class Container, class LessThanComparable>
+  template <class Container, class Value>
   std::pair<typename Container::iterator, typename Container::iterator>
   equal_range(Container& c,
-              const LessThanComparable& value)
+              const Value& value)
   {
     return equal_range_dispatch(c, value,
                                 graph_detail::container_category(c));