Subject: [Boost-commit] svn:boost r81770 - in trunk/boost: graph pending
From: jewillco_at_[hidden]
Date: 2012-12-07 14:29:13
Author: jewillco
Date: 2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
New Revision: 81770
URL: http://svn.boost.org/trac/boost/changeset/81770
Log:
Fixed directed_graph and undirected_graph handling of vertex_all and edge_all properties
Text files modified:
trunk/boost/graph/directed_graph.hpp | 133 +++++++++++++++++++++++++++------------
trunk/boost/graph/undirected_graph.hpp | 92 +++++++++++++++++++++++++--
trunk/boost/pending/property.hpp | 21 ++++++
3 files changed, 197 insertions(+), 49 deletions(-)
Modified: trunk/boost/graph/directed_graph.hpp
==============================================================================
--- trunk/boost/graph/directed_graph.hpp (original)
+++ trunk/boost/graph/directed_graph.hpp 2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
@@ -9,6 +9,10 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/pending/property.hpp>
+#include <boost/property_map/transform_value_property_map.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
namespace boost
{
@@ -27,8 +31,8 @@
*/
template <
typename VertexProp = no_property,
- typename EdgeProp= no_property,
- typename GraphProp= no_property>
+ typename EdgeProp = no_property,
+ typename GraphProp = no_property>
class directed_graph
{
public:
@@ -39,15 +43,14 @@
typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
-private:
- // Wrap the user-specified properties with an index.
- typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
- typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
-
+public:
+ // Embed indices into the vertex type.
+ typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
+ typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
public:
typedef adjacency_list<
listS, listS, bidirectionalS,
- vertex_property, edge_property, GraphProp,
+ internal_vertex_property, internal_edge_property, GraphProp,
listS
> graph_type;
@@ -80,8 +83,8 @@
typedef typename graph_type::edge_parallel_category edge_parallel_category;
typedef typename graph_type::traversal_category traversal_category;
- typedef unsigned vertex_index_type;
- typedef unsigned edge_index_type;
+ typedef std::size_t vertex_index_type;
+ typedef std::size_t edge_index_type;
directed_graph(GraphProp const& p = GraphProp())
: m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
@@ -137,6 +140,7 @@
vertices_size_type num_vertices() const
{ return m_num_vertices; }
+
private:
// This helper function manages the attribution of vertex indices.
vertex_descriptor make_index(vertex_descriptor v) {
@@ -150,7 +154,7 @@
{ return make_index(boost::add_vertex(m_graph)); }
vertex_descriptor add_vertex(vertex_property_type const& p)
- { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+ { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
void clear_vertex(vertex_descriptor v)
{
@@ -186,7 +190,7 @@
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v, edge_property_type const& p)
- { return make_index(boost::add_edge(u, v, edge_property(0u, p), m_graph)); }
+ { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
void remove_edge(vertex_descriptor u, vertex_descriptor v)
{
@@ -516,37 +520,32 @@
DIRECTED_GRAPH& g)
{ return remove_in_edge_if(v, pred, g.impl()); }
-// Helper code for working with property maps
-namespace detail
-{
- struct directed_graph_vertex_property_selector {
- template <class DirectedGraph, class Property, class Tag>
- struct bind_ {
- typedef typename DirectedGraph::graph_type Graph;
- typedef property_map<Graph, Tag> PropertyMap;
- typedef typename PropertyMap::type type;
- typedef typename PropertyMap::const_type const_type;
- };
- };
-
- struct directed_graph_edge_property_selector {
- template <class DirectedGraph, class Property, class Tag>
- struct bind_ {
- typedef typename DirectedGraph::graph_type Graph;
- typedef property_map<Graph, Tag> PropertyMap;
- typedef typename PropertyMap::type type;
- typedef typename PropertyMap::const_type const_type;
- };
- };
-}
+template <DIRECTED_GRAPH_PARAMS, typename Property>
+struct property_map<DIRECTED_GRAPH, Property>: property_map<typename DIRECTED_GRAPH::graph_type, Property> {};
-template <>
-struct vertex_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_vertex_property_selector type; };
-
-template <>
-struct edge_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_edge_property_selector type; };
+template <DIRECTED_GRAPH_PARAMS>
+struct property_map<DIRECTED_GRAPH, vertex_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::type>
+ type;
+};
+
+template <DIRECTED_GRAPH_PARAMS>
+struct property_map<DIRECTED_GRAPH, edge_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::type>
+ type;
+};
// PropertyGraph concepts
template <DIRECTED_GRAPH_PARAMS, typename Property>
@@ -559,6 +558,26 @@
get(Property p, DIRECTED_GRAPH const& g)
{ return get(p, g.impl()); }
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::type
+get(vertex_all_t, DIRECTED_GRAPH& g)
+{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type
+get(vertex_all_t, DIRECTED_GRAPH const& g)
+{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, edge_all_t>::type
+get(edge_all_t, DIRECTED_GRAPH& g)
+{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type
+get(edge_all_t, DIRECTED_GRAPH const& g)
+{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key>
inline typename property_traits<
typename property_map<
@@ -568,10 +587,40 @@
get(Property p, DIRECTED_GRAPH const& g, Key const& k)
{ return get(p, g.impl(), k); }
+template <DIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename DIRECTED_GRAPH::graph_type, vertex_all_t
+ >::const_type
+>::value_type
+get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(vertex_all, g.impl(), k).m_base; }
+
+template <DIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename DIRECTED_GRAPH::graph_type, edge_all_t
+ >::const_type
+>::value_type
+get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(edge_all, g.impl(), k).m_base; }
+
template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
{ put(p, g.impl(), k, v); }
+template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(vertex_all, g.impl(), k,
+ typename DIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
+}
+
+template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(edge_all, g.impl(), k,
+ typename DIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
+}
+
template <DIRECTED_GRAPH_PARAMS, class Property>
typename graph_property<DIRECTED_GRAPH, Property>::type&
get_property(DIRECTED_GRAPH& g, Property p)
Modified: trunk/boost/graph/undirected_graph.hpp
==============================================================================
--- trunk/boost/graph/undirected_graph.hpp (original)
+++ trunk/boost/graph/undirected_graph.hpp 2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
@@ -9,6 +9,10 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/pending/property.hpp>
+#include <boost/property_map/transform_value_property_map.hpp>
+#include <boost/type_traits.hpp>
+#include <boost/mpl/if.hpp>
namespace boost
{
@@ -39,16 +43,16 @@
typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
-private:
+public:
// Embed indices into the vertex type.
- typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
- typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
+ typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
+ typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
public:
typedef adjacency_list<listS,
listS,
undirectedS,
- vertex_property,
- edge_property,
+ internal_vertex_property,
+ internal_edge_property,
GraphProp,
listS> graph_type;
private:
@@ -151,7 +155,7 @@
{ return make_index(boost::add_vertex(m_graph)); }
vertex_descriptor add_vertex(vertex_property_type const& p)
- { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+ { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
void clear_vertex(vertex_descriptor v) {
std::pair<out_edge_iterator, out_edge_iterator>
@@ -188,7 +192,7 @@
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
edge_property_type const& p)
- { return make_index(boost::add_edge(u, v, edge_property(0u, p), m_graph)); }
+ { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
void remove_edge(vertex_descriptor u, vertex_descriptor v) {
// find all edges, (u, v)
@@ -525,6 +529,30 @@
template <UNDIRECTED_GRAPH_PARAMS, typename Property>
struct property_map<UNDIRECTED_GRAPH, Property>: property_map<typename UNDIRECTED_GRAPH::graph_type, Property> {};
+template <UNDIRECTED_GRAPH_PARAMS>
+struct property_map<UNDIRECTED_GRAPH, vertex_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::type>
+ type;
+};
+
+template <UNDIRECTED_GRAPH_PARAMS>
+struct property_map<UNDIRECTED_GRAPH, edge_all_t> {
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
+ const_type;
+ typedef transform_value_property_map<
+ detail::remove_first_property,
+ typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::type>
+ type;
+};
+
// PropertyGraph concepts
template <UNDIRECTED_GRAPH_PARAMS, typename Property>
inline typename property_map<UNDIRECTED_GRAPH, Property>::type
@@ -536,6 +564,26 @@
get(Property p, UNDIRECTED_GRAPH const& g)
{ return get(p, g.impl()); }
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type
+get(vertex_all_t, UNDIRECTED_GRAPH& g)
+{ return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type
+get(vertex_all_t, UNDIRECTED_GRAPH const& g)
+{ return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type
+get(edge_all_t, UNDIRECTED_GRAPH& g)
+{ return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type
+get(edge_all_t, UNDIRECTED_GRAPH const& g)
+{ return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
+
template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key>
inline typename property_traits<
typename property_map<
@@ -545,10 +593,40 @@
get(Property p, UNDIRECTED_GRAPH const& g, Key const& k)
{ return get(p, g.impl(), k); }
+template <UNDIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename UNDIRECTED_GRAPH::graph_type, vertex_all_t
+ >::const_type
+>::value_type
+get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(vertex_all, g.impl(), k).m_base; }
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Key>
+inline typename property_traits<
+ typename property_map<
+ typename UNDIRECTED_GRAPH::graph_type, edge_all_t
+ >::const_type
+>::value_type
+get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(edge_all, g.impl(), k).m_base; }
+
template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
{ put(p, g.impl(), k, v); }
+template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(vertex_all, g.impl(), k,
+ typename UNDIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
+}
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
+inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(edge_all, g.impl(), k,
+ typename UNDIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
+}
+
template <UNDIRECTED_GRAPH_PARAMS, class Property>
inline typename graph_property<UNDIRECTED_GRAPH, Property>::type&
get_property(UNDIRECTED_GRAPH& g, Property p)
Modified: trunk/boost/pending/property.hpp
==============================================================================
--- trunk/boost/pending/property.hpp (original)
+++ trunk/boost/pending/property.hpp 2012-12-07 14:29:12 EST (Fri, 07 Dec 2012)
@@ -244,6 +244,27 @@
} // namespace detail
+namespace detail {
+ // Stuff for directed_graph and undirected_graph to skip over their first
+ // vertex_index and edge_index properties when providing vertex_all and
+ // edge_all; make sure you know the exact structure of your properties if you
+ // use there.
+ struct remove_first_property {
+ template <typename F>
+ struct result {
+ typedef typename boost::function_traits<F>::arg1_type a1;
+ typedef typename boost::remove_reference<a1>::type non_ref;
+ typedef typename non_ref::next_type nx;
+ typedef typename boost::mpl::if_<boost::is_const<non_ref>, boost::add_const<nx>, nx>::type with_const;
+ typedef typename boost::add_reference<with_const>::type type;
+ };
+ template <typename Prop>
+ typename Prop::next_type& operator()(Prop& p) const {return p.m_base;}
+ template <typename Prop>
+ const typename Prop::next_type& operator()(const Prop& p) const {return p.m_base;}
+ };
+}
+
} // namesapce boost
#endif /* BOOST_PROPERTY_HPP */