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& 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>