|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r76049 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2011-12-18 15:53:28
Author: jewillco
Date: 2011-12-18 15:53:26 EST (Sun, 18 Dec 2011)
New Revision: 76049
URL: http://svn.boost.org/trac/boost/changeset/76049
Log:
Added documented way to get underlying edge descriptor from a reverse_graph; changed name of member to prevent future use
Text files modified:
trunk/boost/graph/copy.hpp | 24 +++++-----
trunk/boost/graph/properties.hpp | 2
trunk/boost/graph/reverse_graph.hpp | 88 +++++++++++++++++++++++++++++++++------
trunk/libs/graph/doc/reverse_graph.html | 29 ++++++++++++
trunk/libs/graph/test/reverse_graph_cc.cpp | 2
5 files changed, 117 insertions(+), 28 deletions(-)
Modified: trunk/boost/graph/copy.hpp
==============================================================================
--- trunk/boost/graph/copy.hpp (original)
+++ trunk/boost/graph/copy.hpp 2011-12-18 15:53:26 EST (Sun, 18 Dec 2011)
@@ -55,17 +55,17 @@
namespace detail {
// Hack to make transpose_graph work with the same interface as before
- template <typename Desc>
+ template <typename Graph, typename Desc>
struct remove_reverse_edge_descriptor {
typedef Desc type;
- static Desc convert(const Desc& d) {return d;}
+ static Desc convert(const Desc& d, const Graph&) {return d;}
};
- template <typename Desc>
- struct remove_reverse_edge_descriptor<reverse_graph_edge_descriptor<Desc> > {
+ template <typename Graph, typename Desc>
+ struct remove_reverse_edge_descriptor<Graph, reverse_graph_edge_descriptor<Desc> > {
typedef Desc type;
- static Desc convert(const reverse_graph_edge_descriptor<Desc>& d) {
- return d.underlying_desc;
+ static Desc convert(const reverse_graph_edge_descriptor<Desc>& d, const Graph& g) {
+ return get(edge_underlying, g, d);
}
};
@@ -155,7 +155,7 @@
CopyVertex copy_vertex, CopyEdge copy_edge,
Orig2CopyVertexIndexMap orig2copy, IndexMap)
{
- typedef remove_reverse_edge_descriptor<typename graph_traits<Graph>::edge_descriptor> cvt;
+ typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt;
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
typename graph_traits<MutableGraph>::vertex_descriptor
@@ -170,7 +170,7 @@
boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
get(orig2copy, target(*ei, g_in)),
g_out);
- copy_edge(cvt::convert(*ei), new_e);
+ copy_edge(cvt::convert(*ei, g_in), new_e);
}
}
};
@@ -185,7 +185,7 @@
CopyVertex copy_vertex, CopyEdge copy_edge,
Orig2CopyVertexIndexMap orig2copy, IndexMap)
{
- typedef remove_reverse_edge_descriptor<typename graph_traits<Graph>::edge_descriptor> cvt;
+ typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt;
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g_in); vi != vi_end; ++vi) {
typename graph_traits<MutableGraph>::vertex_descriptor
@@ -201,7 +201,7 @@
boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei, g_in)),
get(orig2copy, target(*ei, g_in)),
g_out);
- copy_edge(cvt::convert(*ei), new_e);
+ copy_edge(cvt::convert(*ei, g_in), new_e);
}
}
}
@@ -218,7 +218,7 @@
Orig2CopyVertexIndexMap orig2copy,
IndexMap index_map)
{
- typedef remove_reverse_edge_descriptor<typename graph_traits<Graph>::edge_descriptor> cvt;
+ typedef remove_reverse_edge_descriptor<Graph, typename graph_traits<Graph>::edge_descriptor> cvt;
typedef color_traits<default_color_type> Color;
std::vector<default_color_type>
color(num_vertices(g_in), Color::white());
@@ -238,7 +238,7 @@
boost::tie(new_e, inserted) = add_edge(get(orig2copy, source(*ei,g_in)),
get(orig2copy, target(*ei,g_in)),
g_out);
- copy_edge(cvt::convert(*ei), new_e);
+ copy_edge(cvt::convert(*ei, g_in), new_e);
}
}
color[get(index_map, *vi)] = Color::black();
Modified: trunk/boost/graph/properties.hpp
==============================================================================
--- trunk/boost/graph/properties.hpp (original)
+++ trunk/boost/graph/properties.hpp 2011-12-18 15:53:26 EST (Sun, 18 Dec 2011)
@@ -115,6 +115,7 @@
BOOST_DEF_PROPERTY(vertex, lowpoint);
BOOST_DEF_PROPERTY(vertex, potential);
BOOST_DEF_PROPERTY(vertex, update);
+ BOOST_DEF_PROPERTY(vertex, underlying);
BOOST_DEF_PROPERTY(edge, reverse);
BOOST_DEF_PROPERTY(edge, capacity);
BOOST_DEF_PROPERTY(edge, flow);
@@ -123,6 +124,7 @@
BOOST_DEF_PROPERTY(edge, discover_time);
BOOST_DEF_PROPERTY(edge, update);
BOOST_DEF_PROPERTY(edge, finished);
+ BOOST_DEF_PROPERTY(edge, underlying);
BOOST_DEF_PROPERTY(graph, visitor);
// These tags are used for property bundles
Modified: trunk/boost/graph/reverse_graph.hpp
==============================================================================
--- trunk/boost/graph/reverse_graph.hpp (original)
+++ trunk/boost/graph/reverse_graph.hpp 2011-12-18 15:53:26 EST (Sun, 18 Dec 2011)
@@ -27,30 +27,32 @@
template <typename EdgeDesc>
class reverse_graph_edge_descriptor {
public:
- EdgeDesc underlying_desc;
+ EdgeDesc underlying_descx; // Odd name is because this needs to be public but shouldn't be exposed to users anymore
+
+ private:
typedef EdgeDesc base_descriptor_type;
public:
- explicit reverse_graph_edge_descriptor(const EdgeDesc& underlying_desc = EdgeDesc())
- : underlying_desc(underlying_desc) {}
+ explicit reverse_graph_edge_descriptor(const EdgeDesc& underlying_descx = EdgeDesc())
+ : underlying_descx(underlying_descx) {}
friend bool operator==(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
- return a.underlying_desc == b.underlying_desc;
+ return a.underlying_descx == b.underlying_descx;
}
friend bool operator!=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
- return a.underlying_desc != b.underlying_desc;
+ return a.underlying_descx != b.underlying_descx;
}
friend bool operator<(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
- return a.underlying_desc < b.underlying_desc;
+ return a.underlying_descx < b.underlying_descx;
}
friend bool operator>(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
- return a.underlying_desc > b.underlying_desc;
+ return a.underlying_descx > b.underlying_descx;
}
friend bool operator<=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
- return a.underlying_desc <= b.underlying_desc;
+ return a.underlying_descx <= b.underlying_descx;
}
friend bool operator>=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
- return a.underlying_desc >= b.underlying_desc;
+ return a.underlying_descx >= b.underlying_descx;
}
};
@@ -80,7 +82,7 @@
template <typename Desc>
struct get_underlying_descriptor_from_reverse_descriptor<reverse_graph_edge_descriptor<Desc> > {
typedef Desc type;
- static Desc convert(const reverse_graph_edge_descriptor<Desc>& d) {return d.underlying_desc;}
+ static Desc convert(const reverse_graph_edge_descriptor<Desc>& d) {return d.underlying_descx;}
};
template <bool isEdgeList> struct choose_rev_edge_iter { };
@@ -311,14 +313,14 @@
inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
source(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
{
- return target(e.underlying_desc, g.m_g);
+ return target(e.underlying_descx, g.m_g);
}
template <class Edge, class BidirectionalGraph, class GRef>
inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
target(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
{
- return source(e.underlying_desc, g.m_g);
+ return source(e.underlying_descx, g.m_g);
}
@@ -340,18 +342,18 @@
friend reference
get(const reverse_graph_edge_property_map& m,
const key_type& e) {
- return get(m.underlying_pm, e.underlying_desc);
+ return get(m.underlying_pm, e.underlying_descx);
}
friend void
put(const reverse_graph_edge_property_map& m,
const key_type& e,
const value_type& v) {
- put(m.underlying_pm, e.underlying_desc, v);
+ put(m.underlying_pm, e.underlying_descx, v);
}
reference operator[](const key_type& k) {
- return (this->underlying_pm)[k.underlying_desc];
+ return (this->underlying_pm)[k.underlying_descx];
}
};
@@ -419,6 +421,62 @@
put(get(p, g), k, val);
}
+// Get the underlying descriptor from a reverse_graph's wrapped edge descriptor
+
+namespace detail {
+ template <class E>
+ struct underlying_edge_desc_map_type {
+ E operator[](const reverse_graph_edge_descriptor<E>& k) const {
+ return k.underlying_descx;
+ }
+ };
+
+ template <class E>
+ E
+ get(underlying_edge_desc_map_type<E> m,
+ const reverse_graph_edge_descriptor<E>& k)
+ {
+ return m[k];
+ }
+};
+
+template <class E>
+struct property_traits<detail::underlying_edge_desc_map_type<E> > {
+ typedef detail::reverse_graph_edge_descriptor<E> key_type;
+ typedef E value_type;
+ typedef const E& reference;
+ typedef readable_property_map_tag category;
+};
+
+template <class Graph, class GRef>
+struct property_map<reverse_graph<Graph, GRef>, edge_underlying_t> {
+ private:
+ typedef typename graph_traits<Graph>::edge_descriptor ed;
+
+ public:
+ typedef detail::underlying_edge_desc_map_type<ed> type;
+ typedef detail::underlying_edge_desc_map_type<ed> const_type;
+};
+
+template <class Graph, class GRef>
+detail::underlying_edge_desc_map_type<typename graph_traits<Graph>::edge_descriptor>
+get(edge_underlying_t,
+ const reverse_graph<Graph,GRef>& g)
+{
+ return detail::underlying_edge_desc_map_type<typename graph_traits<Graph>::edge_descriptor>();
+}
+
+template <class Graph, class GRef>
+typename graph_traits<Graph>::edge_descriptor
+get(edge_underlying_t,
+ const reverse_graph<Graph,GRef>& g,
+ const typename graph_traits<reverse_graph<Graph, GRef> >::edge_descriptor& k)
+{
+ return k.underlying_descx;
+}
+
+// Access to wrapped graph's graph properties
+
template<typename BidirectionalGraph, typename GRef, typename Tag,
typename Value>
inline void
Modified: trunk/libs/graph/doc/reverse_graph.html
==============================================================================
--- trunk/libs/graph/doc/reverse_graph.html (original)
+++ trunk/libs/graph/doc/reverse_graph.html 2011-12-18 15:53:26 EST (Sun, 18 Dec 2011)
@@ -27,7 +27,7 @@
a BidirectionalGraph,
effectively transposing the graph. The construction of the
<tt>reverse_graph</tt> is constant time, providing a highly efficient
-way to obtain a transposed-view of a graph.
+way to obtain a transposed view of a graph.
<H3>Example</H3>
@@ -215,6 +215,16 @@
<hr>
+<tt>property_map<reverse_graph, edge_underlying_t>::type</tt><br>
+and<br>
+<tt>property_map<reverse_graph, edge_underlying_t>::const_type</tt>
+<br><br>
+An edge property type mapping from edge descriptors in the <tt>reverse_graph</tt> to
+edge descriptors in the underlying <tt>BidirectionalGraph</tt> object.
+
+<hr>
+
+
<H2>Member Functions</H2>
<hr>
@@ -359,6 +369,16 @@
<hr>
<pre>
+property_map<reverse_graph, edge_underlying_t>::const_type
+get(PropertyTag, const reverse_graph& g)
+</pre>
+Returns a property map object that converts from edge descriptors in the
+<tt>reverse_graph</tt> to edge descriptors in the underlying
+<tt>BidirectionalGraph</tt> object.
+
+<hr>
+
+<pre>
template <class PropertyTag, class X>
typename property_traits<property_map<reverse_graph, PropertyTag>::const_type>::value_type
get(PropertyTag, const reverse_graph& g, X x)
@@ -368,6 +388,13 @@
<hr>
<pre>
+typename graph_traits<BidirectionalGraph>::edge_descriptor
+get(edge_underlying_t, const reverse_graph& g, edge_descriptor e)
+</pre>
+This returns the underlying edge descriptor for the edge <tt>e</tt> in the <tt>reverse_graph</tt>.
+<hr>
+
+<pre>
template <class PropertyTag, class X, class Value>
void
put(PropertyTag, const reverse_graph& g, X x, const Value& value)
Modified: trunk/libs/graph/test/reverse_graph_cc.cpp
==============================================================================
--- trunk/libs/graph/test/reverse_graph_cc.cpp (original)
+++ trunk/libs/graph/test/reverse_graph_cc.cpp 2011-12-18 15:53:26 EST (Sun, 18 Dec 2011)
@@ -28,6 +28,7 @@
typedef graph_traits<Graph>::edge_descriptor Edge;
function_requires< ReadablePropertyGraphConcept<Graph, Vertex, vertex_color_t> >();
function_requires< ReadablePropertyGraphConcept<Graph, Edge, edge_weight_t> >();
+ function_requires< ReadablePropertyGraphConcept<Graph, Edge, edge_underlying_t> >();
AdjList g;
Graph gr(g);
get_property(gr, graph_name_t());
@@ -45,6 +46,7 @@
typedef graph_traits<Graph>::edge_descriptor Edge;
function_requires< PropertyGraphConcept<Graph, Vertex, vertex_color_t> >();
function_requires< PropertyGraphConcept<Graph, Edge, edge_weight_t> >();
+ function_requires< ReadablePropertyGraphConcept<Graph, Edge, edge_underlying_t> >();
AdjList g;
Graph gr(g);
get_property(gr, graph_name_t());
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