Boost logo

Boost-Commit :

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>


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk