[Boost-commit] svn:boost r57928 - in trunk: boost/graph libs/graph/doc

Subject: [Boost-commit] svn:boost r57928 - in trunk: boost/graph libs/graph/doc
From: jewillco_at_[hidden]
Date: 2009-11-25 16:56:37

Author: jewillco
Date: 2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
New Revision: 57928
URL: http://svn.boost.org/trac/boost/changeset/57928

Log:
Added lookup_edge() function as wrapper for graphs that do not model AdjacencyMatrix; changed functions to use it instead of edge(); added is_adjacency_matrix traits class; updated docs to reflect Adjacency Matrix requirements and suggestions; fixes #3266
Added:
   trunk/boost/graph/lookup_edge.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/bron_kerbosch_all_cliques.hpp |    10 ++++------                              
   trunk/boost/graph/clustering_coefficient.hpp    |     7 ++++---                                 
   trunk/boost/graph/graph_traits.hpp              |    10 ++++++++++                              
   trunk/boost/graph/kolmogorov_max_flow.hpp       |     3 ++-                                     
   trunk/boost/graph/metric_tsp_approx.hpp         |     3 ++-                                     
   trunk/libs/graph/doc/kolmogorov_max_flow.html   |     4 +++-                                    
   trunk/libs/graph/doc/transitive_closure.html    |     5 +++--                                   
   7 files changed, 28 insertions(+), 14 deletions(-)

Modified: trunk/boost/graph/bron_kerbosch_all_cliques.hpp
==============================================================================
--- trunk/boost/graph/bron_kerbosch_all_cliques.hpp	(original)
+++ trunk/boost/graph/bron_kerbosch_all_cliques.hpp	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -12,6 +12,7 @@
 #include <boost/config.hpp>
 
 #include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/lookup_edge.hpp>
 
 #include <boost/concept/detail/concept_def.hpp>
 namespace boost {
@@ -125,9 +126,7 @@
                             typename graph_traits<Graph>::vertex_descriptor v,
                             typename graph_traits<Graph>::undirected_category)
     {
-        function_requires< AdjacencyMatrixConcept<Graph> >();
-
-        return edge(u, v, g).second;
+        return lookup_edge(u, v, g).second;
     }
 
     template <typename Graph>
@@ -137,13 +136,12 @@
                             typename graph_traits<Graph>::vertex_descriptor v,
                             typename graph_traits<Graph>::directed_category)
     {
-        function_requires< AdjacencyMatrixConcept<Graph> >();
         // Note that this could alternate between using an || to determine
         // full connectivity. I believe that this should produce strongly
         // connected components. Note that using && instead of || will
         // change the results to a fully connected subgraph (i.e., symmetric
         // edges between all vertices s.t., if a->b, then b->a.
-        return edge(u, v, g).second && edge(v, u, g).second;
+        return lookup_edge(u, v, g).second && lookup_edge(v, u, g).second;
     }
 
     template <typename Graph, typename Container>
@@ -189,7 +187,7 @@
             for(ni = nots.begin(); ni != nend; ++ni) {
                 for(ci = cands.begin(); ci != cend; ++ci) {
                     // if we don't find an edge, then we're okay.
-                    if(!edge(*ni, *ci, g).second) break;
+                    if(!lookup_edge(*ni, *ci, g).second) break;
                 }
                 // if we iterated all the way to the end, then *ni
                 // is connected to all *ci

Modified: trunk/boost/graph/clustering_coefficient.hpp
==============================================================================
--- trunk/boost/graph/clustering_coefficient.hpp	(original)
+++ trunk/boost/graph/clustering_coefficient.hpp	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -10,6 +10,7 @@
 #include <boost/utility.hpp>
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/lookup_edge.hpp>
 
 namespace boost
 {
@@ -42,8 +43,8 @@
 
     {
         function_requires< AdjacencyMatrixConcept<Graph> >();
-        return (edge(u, v, g).second ? 1 : 0) +
-                (edge(v, u, g).second ? 1 : 0);
+        return (lookup_edge(u, v, g).second ? 1 : 0) +
+                (lookup_edge(v, u, g).second ? 1 : 0);
     }
 
     // This template matches undirectedS
@@ -55,7 +56,7 @@
                 undirected_tag)
     {
         function_requires< AdjacencyMatrixConcept<Graph> >();
-        return edge(u, v, g).second ? 1 : 0;
+        return lookup_edge(u, v, g).second ? 1 : 0;
     }
 }
 

Modified: trunk/boost/graph/graph_traits.hpp
==============================================================================
--- trunk/boost/graph/graph_traits.hpp	(original)
+++ trunk/boost/graph/graph_traits.hpp	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -181,6 +181,16 @@
             >::value
         >
     { };
+
+    template <typename Graph>
+    struct is_adjacency_matrix
+        : mpl::bool_<
+            is_convertible<
+                typename graph_traits<Graph>::traversal_category,
+                adjacency_matrix_tag
+            >::value
+        >
+    { };
     //@}
 
     /** @name Directed Graph Traits

Modified: trunk/boost/graph/kolmogorov_max_flow.hpp
==============================================================================
--- trunk/boost/graph/kolmogorov_max_flow.hpp	(original)
+++ trunk/boost/graph/kolmogorov_max_flow.hpp	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -46,6 +46,7 @@
 #include <boost/none_t.hpp>
 #include <boost/graph/graph_concepts.hpp>
 #include <boost/graph/named_function_params.hpp>
+#include <boost/graph/lookup_edge.hpp>
 
 namespace boost {
   namespace detail {
@@ -161,7 +162,7 @@
               }
               edge_descriptor to_sink;
               bool is_there;
-              tie(to_sink, is_there) = edge(current_node, m_sink, m_g);
+              tie(to_sink, is_there) = lookup_edge(current_node, m_sink, m_g);
               if(is_there){
                 tEdgeVal cap_from_source = m_res_cap_map[from_source];
                 tEdgeVal cap_to_sink = m_res_cap_map[to_sink];

Added: trunk/boost/graph/lookup_edge.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/lookup_edge.hpp	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -0,0 +1,48 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University
+// Author: Jeremiah Willcock
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#ifndef BOOST_GRAPH_LOOKUP_EDGE_HPP
+#define BOOST_GRAPH_LOOKUP_EDGE_HPP
+
+#include <utility>
+#include <boost/config.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <boost/graph/graph_traits.hpp>
+
+// lookup_edge: a function that acts like edge() but falls back to out_edges()
+// and a search when edge() is not provided.
+
+namespace boost {
+
+  template <typename Graph>
+  std::pair<typename boost::graph_traits<Graph>::edge_descriptor, bool>
+  lookup_edge(typename boost::graph_traits<Graph>::vertex_descriptor src,
+              typename boost::graph_traits<Graph>::vertex_descriptor tgt,
+              const Graph& g,
+              typename boost::enable_if<is_adjacency_matrix<Graph>, int>::type = 0) {
+    return edge(src, tgt, g);
+  }
+
+  template <typename Graph>
+  std::pair<typename boost::graph_traits<Graph>::edge_descriptor, bool>
+  lookup_edge(typename boost::graph_traits<Graph>::vertex_descriptor src,
+              typename boost::graph_traits<Graph>::vertex_descriptor tgt,
+              const Graph& g,
+              typename boost::disable_if<is_adjacency_matrix<Graph>, int>::type = 0) {
+    typedef typename boost::graph_traits<Graph>::out_edge_iterator it;
+    typedef typename boost::graph_traits<Graph>::edge_descriptor edesc;
+    std::pair<it, it> oe = out_edges(src, g);
+    for (; oe.first != oe.second; ++oe.first) {
+      edesc e = *oe.first;
+      if (target(e, g) == tgt) return std::make_pair(e, true);
+    }
+    return std::make_pair(edesc(), false);
+  }
+
+}

Modified: trunk/boost/graph/metric_tsp_approx.hpp
==============================================================================
--- trunk/boost/graph/metric_tsp_approx.hpp	(original)
+++ trunk/boost/graph/metric_tsp_approx.hpp	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -34,6 +34,7 @@
 #include <boost/graph/graph_as_tree.hpp>
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/prim_minimum_spanning_tree.hpp>
+#include <boost/graph/lookup_edge.hpp>
 
 
 namespace boost
@@ -284,7 +285,7 @@
                 // would require revisiting the core algorithm.
                 Edge e;
                 bool found;
-                tie(e, found) = edge(previous_, v, g);
+                tie(e, found) = lookup_edge(previous_, v, g);
                 if(!found) {
                     throw not_complete();
                 }

Modified: trunk/libs/graph/doc/kolmogorov_max_flow.html
==============================================================================
--- trunk/libs/graph/doc/kolmogorov_max_flow.html	(original)
+++ trunk/libs/graph/doc/kolmogorov_max_flow.html	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -216,7 +216,9 @@
 <A HREF="VertexListGraph.html">Vertex List Graph</A>, <A HREF="EdgeListGraph.html">Edge
 List Graph</A> and Incidence Graph.
 For each edge <I>(u,v)</I> in the graph, the reverse edge <I>(v,u)</I>
-must also be in the graph. 
+must also be in the graph.  Performance of the algorithm will be slightly
+improved if the graph type also models <a href="AdjacencyMatrix.html">Adjacency
+Matrix</a>.
 </BLOCKQUOTE>
 <P>IN: <TT>vertex_descriptor src</TT> 
 </P>

Modified: trunk/libs/graph/doc/transitive_closure.html
==============================================================================
--- trunk/libs/graph/doc/transitive_closure.html	(original)
+++ trunk/libs/graph/doc/transitive_closure.html	2009-11-25 16:56:36 EST (Wed, 25 Nov 2009)
@@ -56,8 +56,9 @@
 IN: <tt>const Graph&amp; g</tt>
 <blockquote>
  A directed graph, where the <tt>Graph</tt> type must model the
- Vertex List Graph
- and Adjacency Graph concepts.<br>
+ Vertex List Graph,
+ Adjacency Graph,
+ and Adjacency Matrix concepts.<br>
 
   <b>Python</b>: The parameter is named <tt>graph</tt>.
 </blockquote>