summaryrefslogtreecommitdiff
path: root/boost/graph/directed_graph.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/graph/directed_graph.hpp')
-rw-r--r--boost/graph/directed_graph.hpp135
1 files changed, 92 insertions, 43 deletions
diff --git a/boost/graph/directed_graph.hpp b/boost/graph/directed_graph.hpp
index 250d0b63d7..2c56a4e0f8 100644
--- a/boost/graph/directed_graph.hpp
+++ b/boost/graph/directed_graph.hpp
@@ -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 @@ struct directed_graph_tag { };
*/
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 @@ public:
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 @@ public:
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 @@ public:
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 @@ public:
{ 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 @@ public:
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)
{
@@ -303,7 +307,7 @@ public:
void swap(directed_graph& g)
{
- m_graph.swap(g);
+ m_graph.swap(g.m_graph);
std::swap(m_num_vertices, g.m_num_vertices);
std::swap(m_max_vertex_index, g.m_max_vertex_index);
std::swap(m_num_edges, g.m_num_edges);
@@ -516,37 +520,32 @@ remove_in_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
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 <>
-struct vertex_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_vertex_property_selector type; };
+template <DIRECTED_GRAPH_PARAMS, typename Property>
+struct property_map<DIRECTED_GRAPH, Property>: property_map<typename DIRECTED_GRAPH::graph_type, Property> {};
+
+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 <>
-struct edge_property_selector<directed_graph_tag>
-{ typedef detail::directed_graph_edge_property_selector 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 @@ inline typename property_map<DIRECTED_GRAPH, Property>::const_type
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 @@ inline typename property_traits<
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)
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-07 18:03:45 +0000