|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r52912 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-05-11 13:40:01
Author: asutton
Date: 2009-05-11 13:40:00 EDT (Mon, 11 May 2009)
New Revision: 52912
URL: http://svn.boost.org/trac/boost/changeset/52912
Log:
Fixing a number of bugs with the declaration of graph parameters.
Fixed an edge-counting bug in directed_graph::remove_vertex.
Text files modified:
trunk/boost/graph/directed_graph.hpp | 694 ++++++++++++++++--------------------
trunk/boost/graph/undirected_graph.hpp | 739 +++++++++++++++++----------------------
2 files changed, 639 insertions(+), 794 deletions(-)
Modified: trunk/boost/graph/directed_graph.hpp
==============================================================================
--- trunk/boost/graph/directed_graph.hpp (original)
+++ trunk/boost/graph/directed_graph.hpp 2009-05-11 13:40:00 EDT (Mon, 11 May 2009)
@@ -27,19 +27,26 @@
* those operations can invalidate the numbering of vertices.
*/
template <
- typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property>
+ typename VertexProp = no_property,
+ typename EdgeProp= no_property,
+ typename GraphProp= no_property>
class directed_graph
{
+public:
+ typedef typename graph_detail::vertex_prop<VertexProp>::type vertex_property_type;
+ typedef typename graph_detail::vertex_prop<VertexProp>::bundle vertex_bundled;
+ typedef typename graph_detail::edge_prop<EdgeProp>::type edge_property_type;
+ typedef typename graph_detail::edge_prop<EdgeProp>::bundle edge_bundled;
+
+private:
// Wrap the user-specified properties with an index.
- typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;
- typedef property<edge_index_t, unsigned, EdgeProperty> edge_property;
+ typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
+ typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
public:
typedef adjacency_list<
listS, listS, bidirectionalS,
- vertex_property, edge_property, GraphProperty,
+ vertex_property, edge_property, GraphProp,
listS
> graph_type;
@@ -52,13 +59,7 @@
public:
typedef directed_graph_tag graph_tag;
-
- // types for properties and bundling
typedef typename graph_type::graph_property_type graph_property_type;
- typedef typename graph_type::vertex_property_type vertex_property_type;
- typedef typename graph_type::edge_property_type edge_property_type;
- typedef typename graph_type::vertex_bundled vertex_bundled;
- typedef typename graph_type::edge_bundled edge_bundled;
// more commonly used graph types
typedef typename graph_type::stored_vertex stored_vertex;
@@ -83,50 +84,39 @@
typedef unsigned vertex_index_type;
typedef unsigned edge_index_type;
- inline directed_graph(const GraphProperty& p = GraphProperty())
- : m_graph(p)
- , m_num_vertices(0)
- , m_num_edges(0)
- , m_max_vertex_index(0)
+ directed_graph(GraphProp const& p = GraphProp())
+ : m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
, m_max_edge_index(0)
{ }
- inline directed_graph(const directed_graph& x)
- : m_graph(x)
- , m_num_vertices(x.m_num_vertices)
- , m_num_edges(x.m_num_edges)
- , m_max_vertex_index(x.m_max_vertex_index)
- , m_max_edge_index(x.m_max_edge_index)
+ directed_graph(directed_graph const& x)
+ : m_graph(x), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
+ , m_max_vertex_index(x.m_max_vertex_index), m_max_edge_index(x.m_max_edge_index)
{ }
- inline directed_graph(vertices_size_type n,
- const GraphProperty& p = GraphProperty())
- : m_graph(n, p)
- , m_num_vertices(n)
- , m_num_edges(0)
- , m_max_vertex_index(n)
+ directed_graph(vertices_size_type n, GraphProp const& p = GraphProp())
+ : m_graph(n, p), m_num_vertices(n), m_num_edges(0), m_max_vertex_index(n)
, m_max_edge_index(0)
- { }
+ { renumber_vertex_indices(); }
template <typename EdgeIterator>
- inline directed_graph(EdgeIterator f,
- EdgeIterator l,
- vertices_size_type n,
- edges_size_type m = 0,
- const GraphProperty& p = GraphProperty())
- : m_graph(f, l, n, m, p)
- , m_num_vertices(n)
- , m_num_edges(0)
- , m_max_vertex_index(n)
- , m_max_edge_index(0)
+ directed_graph(EdgeIterator f,
+ EdgeIterator l,
+ vertices_size_type n,
+ edges_size_type m = 0,
+ GraphProp const& p = GraphProp())
+ : m_graph(f, l, n, m, p), m_num_vertices(n), m_num_edges(0)
+ , m_max_vertex_index(n), m_max_edge_index(0)
{
+ // Unfortunately, we have to renumber the entire graph.
+ renumber_indices();
+
// Can't always guarantee that the number of edges is actually
// m if distance(f, l) != m (or is undefined).
m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
}
- inline directed_graph& operator=(const directed_graph& g)
- {
+ directed_graph& operator=(directed_graph const& g) {
if(&g != this) {
m_graph = g.m_graph;
m_num_vertices = g.m_num_vertices;
@@ -138,57 +128,68 @@
}
// The impl_() methods are not part of the public interface.
- inline graph_type& impl()
+ graph_type& impl()
{ return m_graph; }
- inline const graph_type& impl() const
+ graph_type const& impl() const
{ return m_graph; }
-
// The following methods are not part of the public interface
- inline vertices_size_type num_vertices() const
+ vertices_size_type num_vertices() const
{ return m_num_vertices; }
- inline vertex_descriptor add_vertex()
- {
- vertex_descriptor v = boost::add_vertex(m_graph);
+private:
+ // This helper function manages the attribution of vertex indices.
+ vertex_descriptor make_index(vertex_descriptor v) {
boost::put(vertex_index, m_graph, v, m_max_vertex_index);
m_num_vertices++;
m_max_vertex_index++;
return v;
}
+public:
+ vertex_descriptor add_vertex()
+ { return make_index(boost::add_vertex(m_graph)); }
- inline void clear_vertex(vertex_descriptor v)
+ vertex_descriptor add_vertex(vertex_property_type const& p)
+ { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+
+ void clear_vertex(vertex_descriptor v)
{
- std::pair<out_edge_iterator, out_edge_iterator>
- p = boost::out_edges(v, m_graph);
- m_num_edges -= std::distance(p.first, p.second);
+ m_num_edges -= boost::degree(v, m_graph);
boost::clear_vertex(v, m_graph);
}
- inline void remove_vertex(vertex_descriptor v)
+ void remove_vertex(vertex_descriptor v)
{
boost::remove_vertex(v, m_graph);
--m_num_vertices;
}
- inline edges_size_type num_edges() const
+ edges_size_type num_edges() const
{ return m_num_edges; }
- inline std::pair<edge_descriptor, bool>
- add_edge(vertex_descriptor u,
- vertex_descriptor v)
- {
- std::pair<edge_descriptor, bool> ret = boost::add_edge(u, v, m_graph);
- if(ret.second) {
- boost::put(edge_index, m_graph, ret.first, m_max_edge_index);
+private:
+ // A helper fucntion for managing edge index attributes.
+ std::pair<edge_descriptor, bool> const&
+ make_index(std::pair<edge_descriptor, bool> const& x)
+ {
+ if(x.second) {
+ boost::put(edge_index, m_graph, x.first, m_max_edge_index);
++m_num_edges;
++m_max_edge_index;
}
- return ret;
+ return x;
}
+public:
+ std::pair<edge_descriptor, bool>
+ add_edge(vertex_descriptor u, vertex_descriptor v)
+ { return make_index(boost::add_edge(u, v, m_graph)); }
+
+ 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)); }
- inline void remove_edge(vertex_descriptor u, vertex_descriptor v)
+ void remove_edge(vertex_descriptor u, vertex_descriptor v)
{
// find all edges, (u, v)
std::vector<edge_descriptor> edges;
@@ -206,21 +207,21 @@
}
}
- inline void remove_edge(edge_iterator i)
+ void remove_edge(edge_iterator i)
{
remove_edge(*i);
}
- inline void remove_edge(edge_descriptor e)
+ void remove_edge(edge_descriptor e)
{
boost::remove_edge(e, m_graph);
--m_num_edges;
}
- inline vertex_index_type max_vertex_index() const
+ vertex_index_type max_vertex_index() const
{ return m_max_vertex_index; }
- inline void
+ void
renumber_vertex_indices()
{
vertex_iterator i, end;
@@ -228,7 +229,7 @@
m_max_vertex_index = renumber_vertex_indices(i, end, 0);
}
- inline void
+ void
remove_vertex_and_renumber_indices(vertex_iterator i)
{
vertex_iterator j = next(i), end = vertices(m_graph).second;
@@ -239,11 +240,11 @@
m_max_vertex_index = renumber_vertex_indices(j, end, n);
}
- inline edge_index_type
+ edge_index_type
max_edge_index() const
{ return m_max_edge_index; }
- inline void
+ void
renumber_edge_indices()
{
edge_iterator i, end;
@@ -251,7 +252,7 @@
m_max_edge_index = renumber_edge_indices(i, end, 0);
}
- inline void
+ void
remove_edge_and_renumber_indices(edge_iterator i)
{
edge_iterator j = next(i), end = edges(m_graph).second;
@@ -262,7 +263,7 @@
m_max_edge_index = renumber_edge_indices(j, end, n);
}
- inline void
+ void
renumber_indices()
{
renumber_vertex_indices();
@@ -274,28 +275,28 @@
vertex_bundled& operator[](vertex_descriptor v)
{ return m_graph[v]; }
- const vertex_bundled& operator[](vertex_descriptor v) const
+ vertex_bundled const& operator[](vertex_descriptor v) const
{ return m_graph[v]; }
edge_bundled& operator[](edge_descriptor e)
{ return m_graph[e]; }
- const edge_bundled& operator[](edge_descriptor e) const
+ edge_bundled const& operator[](edge_descriptor e) const
{ return m_graph[e]; }
#endif
// Graph concepts
- static inline vertex_descriptor null_vertex()
+ static vertex_descriptor null_vertex()
{ return graph_type::null_vertex(); }
- inline void clear()
+ void clear()
{
m_graph.clear();
m_num_vertices = m_max_vertex_index = 0;
m_num_edges = m_max_edge_index = 0;
}
- inline void swap(directed_graph& g)
+ void swap(directed_graph& g)
{
m_graph.swap(g);
std::swap(m_num_vertices, g.m_num_vertices);
@@ -305,7 +306,7 @@
}
private:
- inline vertices_size_type
+ vertices_size_type
renumber_vertex_indices(vertex_iterator i,
vertex_iterator end,
vertices_size_type n)
@@ -318,7 +319,7 @@
return n;
}
- inline vertices_size_type
+ vertices_size_type
renumber_edge_indices(edge_iterator i,
edge_iterator end,
vertices_size_type n)
@@ -338,237 +339,186 @@
edge_index_type m_max_edge_index;
};
-// IncidenceGraph concepts
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::vertex_descriptor
-source(typename directed_graph<VP,EP,GP>::edge_descriptor e,
- const directed_graph<VP,EP,GP> &g)
-{
- return source(e, g.impl());
-}
-
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::vertex_descriptor
-target(typename directed_graph<VP,EP,GP>::edge_descriptor e,
- const directed_graph<VP,EP,GP> &g)
-{
- return target(e, g.impl());
-}
+#define DIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
+#define DIRECTED_GRAPH directed_graph<VP,EP,GP>
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::degree_size_type
-out_degree(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
-{
- return out_degree(v, g.impl());
-}
+// IncidenceGraph concepts
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::vertex_descriptor
+source(typename DIRECTED_GRAPH::edge_descriptor e,
+ DIRECTED_GRAPH const& g)
+{ return source(e, g.impl()); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::vertex_descriptor
+target(typename DIRECTED_GRAPH::edge_descriptor e,
+ DIRECTED_GRAPH const& g)
+{ return target(e, g.impl()); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::degree_size_type
+out_degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
+{ return out_degree(v, g.impl()); }
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename directed_graph<VP,EP,GP>::out_edge_iterator,
- typename directed_graph<VP,EP,GP>::out_edge_iterator
+ typename DIRECTED_GRAPH::out_edge_iterator,
+ typename DIRECTED_GRAPH::out_edge_iterator
>
-out_edges(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
-{
- return out_edges(v, g.impl());
-}
+out_edges(typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH const& g)
+{ return out_edges(v, g.impl()); }
// BidirectionalGraph concepts
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::degree_size_type
-in_degree(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
-{
- return in_degree(v, g.impl());
-}
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::degree_size_type
+in_degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
+{ return in_degree(v, g.impl()); }
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename directed_graph<VP,EP,GP>::in_edge_iterator,
- typename directed_graph<VP,EP,GP>::in_edge_iterator
+ typename DIRECTED_GRAPH::in_edge_iterator,
+ typename DIRECTED_GRAPH::in_edge_iterator
>
-in_edges(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
-{
- return in_edges(v, g.impl());
-}
+in_edges(typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH const& g)
+{ return in_edges(v, g.impl()); }
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::degree_size_type
-degree(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
-{
- return degree(v, g.impl());
-}
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::degree_size_type
+degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
+{ return degree(v, g.impl()); }
// AdjacencyGraph concepts
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename directed_graph<VP,EP,GP>::adjacency_iterator,
- typename directed_graph<VP,EP,GP>::adjacency_iterator
+ typename DIRECTED_GRAPH::adjacency_iterator,
+ typename DIRECTED_GRAPH::adjacency_iterator
>
-adjacent_vertices(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP>& g)
-{
- return adjacent_vertices(v, g.impl());
-}
-
-template <class VP, class EP, class GP>
-typename directed_graph<VP,EP,GP>::vertex_descriptor
-vertex(typename directed_graph<VP,EP,GP>::vertices_size_type n,
- const directed_graph<VP,EP,GP>& g)
-{
- return vertex(g.impl());
-}
-
-template <class VP, class EP, class GP>
-std::pair<typename directed_graph<VP,EP,GP>::edge_descriptor, bool>
-edge(typename directed_graph<VP,EP,GP>::vertex_descriptor u,
- typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP>& g)
-{
- return edge(u, v, g.impl());
-}
+adjacent_vertices(typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH const& g)
+{ return adjacent_vertices(v, g.impl()); }
+
+template <DIRECTED_GRAPH_PARAMS>
+typename DIRECTED_GRAPH::vertex_descriptor
+vertex(typename DIRECTED_GRAPH::vertices_size_type n,
+ DIRECTED_GRAPH const& g)
+{ return vertex(g.impl()); }
+
+template <DIRECTED_GRAPH_PARAMS>
+std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
+edge(typename DIRECTED_GRAPH::vertex_descriptor u,
+ typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH const& g)
+{ return edge(u, v, g.impl()); }
// VertexListGraph concepts
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::vertices_size_type
-num_vertices(const directed_graph<VP,EP,GP>& g)
-{
- return g.num_vertices();
-}
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::vertices_size_type
+num_vertices(DIRECTED_GRAPH const& g)
+{ return g.num_vertices(); }
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename directed_graph<VP,EP,GP>::vertex_iterator,
- typename directed_graph<VP,EP,GP>::vertex_iterator
+ typename DIRECTED_GRAPH::vertex_iterator,
+ typename DIRECTED_GRAPH::vertex_iterator
>
-vertices(const directed_graph<VP,EP,GP>& g)
-{
- return vertices(g.impl());
-}
+vertices(DIRECTED_GRAPH const& g)
+{ return vertices(g.impl()); }
// EdgeListGraph concepts
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::edges_size_type
-num_edges(const directed_graph<VP,EP,GP>& g)
-{
- return g.num_edges();
-}
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::edges_size_type
+num_edges(DIRECTED_GRAPH const& g)
+{ return g.num_edges(); }
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
-typename directed_graph<VP,EP,GP>::edge_iterator,
-typename directed_graph<VP,EP,GP>::edge_iterator
+ typename DIRECTED_GRAPH::edge_iterator,
+ typename DIRECTED_GRAPH::edge_iterator
>
-edges(const directed_graph<VP,EP,GP>& g)
-{
- return edges(g.impl());
-}
-
+edges(DIRECTED_GRAPH const& g)
+{ return edges(g.impl()); }
// MutableGraph concepts
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::vertex_descriptor
-add_vertex(directed_graph<VP,EP,GP> &g)
-{
- return g.add_vertex();
-}
-
-
-template <class VP, class EP, class GP>
-inline void
-clear_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
-directed_graph<VP,EP,GP> &g)
-{
- return g.clear_vertex(v);
-}
-
-template <class VP, class EP, class GP>
-inline void
-remove_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- directed_graph<VP,EP,GP> &g)
-{
- return g.remove_vertex(v);
-}
-
-
-
-template <class VP, class EP, class GP>
-inline std::pair<typename directed_graph<VP,EP,GP>::edge_descriptor, bool>
-add_edge(typename directed_graph<VP,EP,GP>::vertex_descriptor u,
- typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- directed_graph<VP,EP,GP> &g)
-{
- return g.add_edge(u, v);
-}
-
-
-template <class VP, class EP, class GP>
-inline void
-remove_edge(typename directed_graph<VP,EP,GP>::vertex_descriptor u,
- typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- directed_graph<VP,EP,GP> &g)
-{
- return g.remove_edge(u, v);
-}
-
-
-template <class VP, class EP, class GP>
-inline void
-remove_edge(typename directed_graph<VP,EP,GP>::edge_descriptor e,
- directed_graph<VP,EP,GP> &g)
-{
- return g.remove_edge(e);
-}
-
-
-template <class VP, class EP, class GP>
-inline void
-remove_edge(typename directed_graph<VP,EP,GP>::edge_iterator i,
- directed_graph<VP,EP,GP> &g)
-{
- return g.remove_edge(i);
-}
-
-template <class VP, class EP, class GP, class Predicate>
-inline void
-remove_edge_if(Predicate pred,
- directed_graph<VP,EP,GP> &g)
-
-{
- return remove_edge_if(pred, g.impl());
-}
-
-
-template <class VP, class EP, class GP, class Predicate>
-inline void
-remove_out_edge_if(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- Predicate pred,
- directed_graph<VP,EP,GP> &g)
-{
- return remove_out_edge_if(v, pred, g.impl());
-}
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::vertex_descriptor
+add_vertex(DIRECTED_GRAPH& g)
+{ return g.add_vertex(); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::vertex_descriptor
+add_vertex(typename DIRECTED_GRAPH::vertex_property_type const& p,
+ DIRECTED_GRAPH& g)
+{ return g.add_vertex(p); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline void
+clear_vertex(typename DIRECTED_GRAPH::vertex_descriptor v,
+DIRECTED_GRAPH& g)
+{ return g.clear_vertex(v); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline void
+remove_vertex(typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH& g)
+{ return g.remove_vertex(v); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
+add_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
+ typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH& g)
+{ return g.add_edge(u, v); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
+add_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
+ typename DIRECTED_GRAPH::vertex_descriptor v,
+ typename DIRECTED_GRAPH::edge_property_type const& p,
+ DIRECTED_GRAPH& g)
+{ return g.add_edge(u, v, p); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline void remove_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
+ typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH& g)
+{ return g.remove_edge(u, v); }
+
+
+template <DIRECTED_GRAPH_PARAMS>
+inline void remove_edge(typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH& g)
+{ return g.remove_edge(e); }
+
+template <DIRECTED_GRAPH_PARAMS>
+inline void remove_edge(typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g)
+{ return g.remove_edge(i); }
+
+template <DIRECTED_GRAPH_PARAMS, class Predicate>
+inline void remove_edge_if(Predicate pred, DIRECTED_GRAPH& g)
+{ return remove_edge_if(pred, g.impl()); }
+
+template <DIRECTED_GRAPH_PARAMS, class Predicate>
+inline void
+remove_out_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
+ Predicate pred,
+ DIRECTED_GRAPH& g)
+{ return remove_out_edge_if(v, pred, g.impl()); }
-template <class VP, class EP, class GP, class Predicate>
+template <DIRECTED_GRAPH_PARAMS, class Predicate>
inline void
-remove_in_edge_if(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
+remove_in_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
Predicate pred,
- directed_graph<VP,EP,GP> &g)
-{
- return remove_in_edge_if(v, pred, g.impl());
-}
+ 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
- {
+ struct directed_graph_vertex_property_selector {
template <class DirectedGraph, class Property, class Tag>
- struct bind_
- {
+ struct bind_ {
typedef typename DirectedGraph::graph_type Graph;
typedef property_map<Graph, Tag> PropertyMap;
typedef typename PropertyMap::type type;
@@ -576,11 +526,9 @@
};
};
- struct directed_graph_edge_property_selector
- {
+ struct directed_graph_edge_property_selector {
template <class DirectedGraph, class Property, class Tag>
- struct bind_
- {
+ struct bind_ {
typedef typename DirectedGraph::graph_type Graph;
typedef property_map<Graph, Tag> PropertyMap;
typedef typename PropertyMap::type type;
@@ -591,157 +539,137 @@
template <>
struct vertex_property_selector<directed_graph_tag>
-{
- typedef detail::directed_graph_vertex_property_selector type;
-};
+{ typedef detail::directed_graph_vertex_property_selector type; };
template <>
struct edge_property_selector<directed_graph_tag>
-{
- typedef detail::directed_graph_edge_property_selector type;
-};
+{ typedef detail::directed_graph_edge_property_selector type; };
// PropertyGraph concepts
-template <class VP, class EP, class GP, typename Property>
-inline typename property_map<directed_graph<VP,EP,GP>, Property>::type
-get(Property p, directed_graph<VP,EP,GP>& g)
-{
- return get(p, g.impl());
-}
-
-template <class VP, class EP, class GP, typename Property>
-inline typename property_map<directed_graph<VP,EP,GP>, Property>::const_type
-get(Property p, const directed_graph<VP,EP,GP>& g)
-{
- return get(p, g.impl());
-}
+template <DIRECTED_GRAPH_PARAMS, typename Property>
+inline typename property_map<DIRECTED_GRAPH, Property>::type
+get(Property p, DIRECTED_GRAPH& g)
+{ return get(p, g.impl()); }
+
+template <DIRECTED_GRAPH_PARAMS, typename Property>
+inline typename property_map<DIRECTED_GRAPH, Property>::const_type
+get(Property p, DIRECTED_GRAPH const& g)
+{ return get(p, g.impl()); }
-template <class VP, class EP, class GP, typename Property, typename Key>
+template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key>
inline typename property_traits<
- typename property_map<typename directed_graph<VP,EP,GP>::graph_type, Property>::const_type
+ typename property_map<
+ typename DIRECTED_GRAPH::graph_type, Property
+ >::const_type
>::value_type
-get(Property p, const directed_graph<VP,EP,GP> &g, const Key& k)
-{
- return get(p, g.impl(), k);
-}
-
-template <class VP, class EP, class GP, typename Property, typename Key, typename Value>
-inline void
-put(Property p, directed_graph<VP,EP,GP> &g, const Key& k, const Value& v)
-{
- put(p, g.impl(), k, v);
-}
-
-template <class VP, class EP, class GP, class Property>
-typename graph_property<directed_graph<VP,EP,GP>, Property>::type&
-get_property(directed_graph<VP,EP,GP>& g, Property p)
-{
- return get_property(g.impl(), p);
-}
+get(Property p, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(p, g.impl(), k); }
-template <class VP, class EP, class GP, class Property>
-const typename graph_property<directed_graph<VP,EP,GP>, Property>::type&
-get_property(const directed_graph<VP,EP,GP>& g, Property p)
-{
- return get_property(g.impl(), p);
-}
+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, class Property>
+typename graph_property<DIRECTED_GRAPH, Property>::type&
+get_property(DIRECTED_GRAPH& g, Property p)
+{ return get_property(g.impl(), p); }
+
+template <DIRECTED_GRAPH_PARAMS, class Property>
+typename graph_property<DIRECTED_GRAPH, Property>::type const&
+get_property(DIRECTED_GRAPH const& g, Property p)
+{ return get_property(g.impl(), p); }
-template <class VP, class EP, class GP, class Property, class Value>
+template <DIRECTED_GRAPH_PARAMS, class Property, class Value>
void
-set_property(directed_graph<VP,EP,GP>& g, Property p, Value v)
-{
- return set_property(g.impl(), p, v);
-}
+set_property(DIRECTED_GRAPH& g, Property p, Value v)
+{ return set_property(g.impl(), p, v); }
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
-template <class VP, class EP, class GP, typename Type, typename Bundle>
-inline typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::type
-get(Type Bundle::* p, directed_graph<VP,EP,GP>& g)
-{
-typedef typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::type
- return_type;
-return return_type(&g, p);
-}
-template <class VP, class EP, class GP, typename Type, typename Bundle>
-inline typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::const_type
-get(Type Bundle::* p, const directed_graph<VP,EP,GP>& g)
+template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle>
+inline typename property_map<DIRECTED_GRAPH, Type Bundle::*>::type
+get(Type Bundle::* p, DIRECTED_GRAPH& g)
{
-typedef typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::const_type
- return_type;
-return return_type(&g, p);
+ typedef typename property_map<
+ DIRECTED_GRAPH, Type Bundle::*
+ >::type return_type;
+ return return_type(&g, p);
}
-template <class VP, class EP, class GP, typename Type, typename Bundle, typename Key>
-inline Type
-get(Type Bundle::* p, const directed_graph<VP,EP,GP> &g, const Key& k)
+template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle>
+inline typename property_map<DIRECTED_GRAPH, Type Bundle::*>::const_type
+get(Type Bundle::* p, DIRECTED_GRAPH const& g)
{
-return get(p, g.impl(), k);
+ typedef typename property_map<
+ DIRECTED_GRAPH, Type Bundle::*
+ >::const_type return_type;
+ return return_type(&g, p);
}
-template <class VP, class EP, class GP, typename Type, typename Bundle, typename Key, typename Value>
-inline void
-put(Type Bundle::* p, directed_graph<VP,EP,GP> &g, const Key& k, const Value& v)
-{
-// put(get(p, g.impl()), k, v);
-put(p, g.impl(), k, v);
-}
+template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key>
+inline Type get(Type Bundle::* p, DIRECTED_GRAPH const& g, Key const& k)
+{ return get(p, g.impl(), k); }
+
+template <DIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key, typename Value>
+inline void put(Type Bundle::* p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(p, g.impl(), k, v); }
+
#endif
// Vertex index management
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::vertex_index_type
-get_vertex_index(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP>& g)
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::vertex_index_type
+get_vertex_index(typename DIRECTED_GRAPH::vertex_descriptor v,
+ DIRECTED_GRAPH const& g)
{ return get(vertex_index, g, v); }
-template <class VP, class EP, class GP>
-typename directed_graph<VP,EP,GP>::vertex_index_type
-max_vertex_index(const directed_graph<VP,EP,GP>& g)
+template <DIRECTED_GRAPH_PARAMS>
+typename DIRECTED_GRAPH::vertex_index_type
+max_vertex_index(DIRECTED_GRAPH const& g)
{ return g.max_vertex_index(); }
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline void
-renumber_vertex_indices(directed_graph<VP,EP,GP>& g)
+renumber_vertex_indices(DIRECTED_GRAPH& g)
{ g.renumber_vertex_indices(); }
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline void
-remove_vertex_and_renumber_indices(typename directed_graph<VP,EP,GP>::vertex_iterator i,
- directed_graph<VP,EP,GP>& g)
+remove_vertex_and_renumber_indices(typename DIRECTED_GRAPH::vertex_iterator i,
+ DIRECTED_GRAPH& g)
{ g.remove_vertex_and_renumber_indices(i); }
// Edge index management
-
-template <class VP, class EP, class GP>
-inline typename directed_graph<VP,EP,GP>::edge_index_type
-get_edge_index(typename directed_graph<VP,EP,GP>::edge_descriptor v,
- const directed_graph<VP,EP,GP>& g)
+template <DIRECTED_GRAPH_PARAMS>
+inline typename DIRECTED_GRAPH::edge_index_type
+get_edge_index(typename DIRECTED_GRAPH::edge_descriptor v, DIRECTED_GRAPH const& g)
{ return get(edge_index, g, v); }
-template <class VP, class EP, class GP>
-typename directed_graph<VP,EP,GP>::edge_index_type
-max_edge_index(const directed_graph<VP,EP,GP>& g)
+template <DIRECTED_GRAPH_PARAMS>
+typename DIRECTED_GRAPH::edge_index_type
+max_edge_index(DIRECTED_GRAPH const& g)
{ return g.max_edge_index(); }
-template <class VP, class EP, class GP>
-inline void
-renumber_edge_indices(directed_graph<VP,EP,GP>& g)
+template <DIRECTED_GRAPH_PARAMS>
+inline void renumber_edge_indices(DIRECTED_GRAPH& g)
{ g.renumber_edge_indices(); }
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline void
-remove_edge_and_renumber_indices(typename directed_graph<VP,EP,GP>::edge_iterator i,
- directed_graph<VP,EP,GP>& g)
+remove_edge_and_renumber_indices(typename DIRECTED_GRAPH::edge_iterator i,
+ DIRECTED_GRAPH& g)
{ g.remove_edge_and_renumber_indices(i); }
// Index management
-template <class VP, class EP, class GP>
+template <DIRECTED_GRAPH_PARAMS>
inline void
-renumber_indices(directed_graph<VP,EP,GP>& g)
+renumber_indices(DIRECTED_GRAPH& g)
{ g.renumber_indices(); }
+#undef DIRECTED_GRAPH_PARAMS
+#undef DIRECTED_GRAPH
+
} /* namespace boost */
#endif
Modified: trunk/boost/graph/undirected_graph.hpp
==============================================================================
--- trunk/boost/graph/undirected_graph.hpp (original)
+++ trunk/boost/graph/undirected_graph.hpp 2009-05-11 13:40:00 EDT (Mon, 11 May 2009)
@@ -11,6 +11,11 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
+// NOTE: The retag_property_list is used to "normalize" a proeprty such that
+// any non-property conforming parameter is wrapped in a vertex_bundle
+// property. For example (with bad syntax) retag<property<X>> -> property<X>,
+// but retag<foo> -> property<vertex_bundle_t, foo>.
+
namespace boost
{
struct undirected_graph_tag { };
@@ -27,22 +32,28 @@
* those operations can invalidate the numbering of vertices.
*/
template <
- typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property>
+ typename VertexProp = no_property,
+ typename EdgeProp= no_property,
+ typename GraphProp = no_property>
class undirected_graph
{
- typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;
- typedef property<edge_index_t, unsigned, EdgeProperty> edge_property;
+public:
+ typedef typename graph_detail::vertex_prop<VertexProp>::type vertex_property_type;
+ typedef typename graph_detail::vertex_prop<VertexProp>::bundle vertex_bundled;
+ typedef typename graph_detail::edge_prop<EdgeProp>::type edge_property_type;
+ typedef typename graph_detail::edge_prop<EdgeProp>::bundle edge_bundled;
+
+private:
+ typedef property<vertex_index_t, unsigned, vertex_property_type> vertex_property;
+ typedef property<edge_index_t, unsigned, edge_property_type> edge_property;
public:
typedef adjacency_list<listS,
listS,
undirectedS,
vertex_property,
edge_property,
- GraphProperty,
+ GraphProp,
listS> graph_type;
-
private:
// storage selectors
typedef typename graph_type::vertex_list_selector vertex_list_selector;
@@ -52,13 +63,7 @@
public:
typedef undirected_graph_tag graph_tag;
-
- // types for properties and bundling
typedef typename graph_type::graph_property_type graph_property_type;
- typedef typename graph_type::vertex_property_type vertex_property_type;
- typedef typename graph_type::edge_property_type edge_property_type;
- typedef typename graph_type::vertex_bundled vertex_bundled;
- typedef typename graph_type::edge_bundled edge_bundled;
// more commonly used graph types
typedef typename graph_type::stored_vertex stored_vertex;
@@ -80,53 +85,43 @@
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;
- inline undirected_graph(const GraphProperty& p = GraphProperty())
- : m_graph(p)
- , m_num_vertices(0)
- , m_num_edges(0)
- , m_max_vertex_index(0)
+ inline undirected_graph(GraphProp const& p = GraphProp())
+ : m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
, m_max_edge_index(0)
{ }
- inline undirected_graph(const undirected_graph& x)
- : m_graph(x)
- , m_num_vertices(x.m_num_vertices)
- , m_num_edges(x.m_num_edges)
- , m_max_vertex_index(x.m_max_vertex_index)
- , m_max_edge_index(x.m_max_edge_index)
+ inline undirected_graph(undirected_graph const& x)
+ : m_graph(x), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
+ , m_max_vertex_index(x.m_max_vertex_index), m_max_edge_index(x.m_max_edge_index)
{ }
inline undirected_graph(vertices_size_type n,
- const GraphProperty& p = GraphProperty())
- : m_graph(n, p)
- , m_num_vertices(n)
- , m_num_edges(0)
- , m_max_vertex_index(n)
+ GraphProp const& p = GraphProp())
+ : m_graph(n, p), m_num_vertices(n), m_num_edges(0), m_max_vertex_index(n)
, m_max_edge_index(0)
- { }
+ { renumber_vertex_indices(); }
template <typename EdgeIterator>
inline undirected_graph(EdgeIterator f,
EdgeIterator l,
vertices_size_type n,
edges_size_type m = 0,
- const GraphProperty& p = GraphProperty())
- : m_graph(f, l, n, m, p)
- , m_num_vertices(n)
- , m_num_edges(0)
- , m_max_vertex_index(n)
- , m_max_edge_index(0)
+ GraphProp const& p = GraphProp())
+ : m_graph(f, l, n, m, p), m_num_vertices(n), m_num_edges(0)
+ , m_max_vertex_index(n), m_max_edge_index(0)
{
+ // Unfortunately, we have to renumber to ensure correct indexing.
+ renumber_indices();
+
// Can't always guarantee that the number of edges is actually
// m if distance(f, l) != m (or is undefined).
m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
}
- inline undirected_graph& operator =(const undirected_graph& g)
- {
+ undirected_graph& operator =(undirected_graph const& g) {
if(&g != this) {
m_graph = g.m_graph;
m_num_vertices = g.m_num_vertices;
@@ -137,58 +132,70 @@
}
// The impl_() methods are not part of the public interface.
- inline graph_type& impl()
+ graph_type& impl()
{ return m_graph; }
- inline const graph_type& impl() const
+ graph_type const& impl() const
{ return m_graph; }
-
// The following methods are not part of the public interface
- inline vertices_size_type num_vertices() const
+ vertices_size_type num_vertices() const
{ return m_num_vertices; }
- inline vertex_descriptor add_vertex()
- {
- vertex_descriptor v = boost::add_vertex(m_graph);
+
+private:
+ // This helper function manages the attribution of vertex indices.
+ vertex_descriptor make_index(vertex_descriptor v) {
boost::put(vertex_index, m_graph, v, m_max_vertex_index);
m_num_vertices++;
m_max_vertex_index++;
return v;
}
+public:
+ vertex_descriptor add_vertex()
+ { return make_index(boost::add_vertex(m_graph)); }
- inline void clear_vertex(vertex_descriptor v)
- {
+ vertex_descriptor add_vertex(vertex_property_type const& p)
+ { return make_index(boost::add_vertex(vertex_property(0u, p), m_graph)); }
+
+ void clear_vertex(vertex_descriptor v) {
std::pair<out_edge_iterator, out_edge_iterator>
p = boost::out_edges(v, m_graph);
m_num_edges -= std::distance(p.first, p.second);
boost::clear_vertex(v, m_graph);
}
- inline void remove_vertex(vertex_descriptor v)
- {
+ void remove_vertex(vertex_descriptor v) {
boost::remove_vertex(v, m_graph);
--m_num_vertices;
}
- inline edges_size_type num_edges() const
+ edges_size_type num_edges() const
{ return m_num_edges; }
- inline std::pair<edge_descriptor, bool>
- add_edge(vertex_descriptor u,
- vertex_descriptor v)
+private:
+ // A helper fucntion for managing edge index attributes.
+ std::pair<edge_descriptor, bool> const&
+ make_index(std::pair<edge_descriptor, bool> const& x)
{
- std::pair<edge_descriptor, bool> ret = boost::add_edge(u, v, m_graph);
- if(ret.second) {
- boost::put(edge_index, m_graph, ret.first, m_max_edge_index);
+ if(x.second) {
+ boost::put(edge_index, m_graph, x.first, m_max_edge_index);
++m_num_edges;
++m_max_edge_index;
}
- return ret;
+ return x;
}
+public:
+ std::pair<edge_descriptor, bool>
+ add_edge(vertex_descriptor u, vertex_descriptor v)
+ { return make_index(boost::add_edge(u, v, m_graph)); }
+
+ 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)); }
- inline void remove_edge(vertex_descriptor u, vertex_descriptor v)
- {
+ void remove_edge(vertex_descriptor u, vertex_descriptor v) {
// find all edges, (u, v)
std::vector<edge_descriptor> edges;
out_edge_iterator i, i_end;
@@ -205,30 +212,25 @@
}
}
- inline void remove_edge(edge_iterator i)
- {
+ void remove_edge(edge_iterator i) {
remove_edge(*i);
}
- inline void remove_edge(edge_descriptor e)
- {
+ void remove_edge(edge_descriptor e) {
boost::remove_edge(e, m_graph);
--m_num_edges;
}
- inline vertex_index_type max_vertex_index() const
+ vertex_index_type max_vertex_index() const
{ return m_max_vertex_index; }
- inline void renumber_vertex_indices()
- {
+ void renumber_vertex_indices() {
vertex_iterator i, i_end;
tie(i, i_end) = vertices(m_graph);
m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
}
- inline void
- remove_vertex_and_renumber_indices(vertex_iterator i)
- {
+ void remove_vertex_and_renumber_indices(vertex_iterator i) {
vertex_iterator j = next(i), end = vertices(m_graph).second;
vertex_index_type n = get(vertex_index, m_graph, *i);
@@ -238,19 +240,16 @@
}
- inline edge_index_type max_edge_index() const
+ edge_index_type max_edge_index() const
{ return m_max_edge_index; }
- inline void renumber_edge_indices()
- {
+ void renumber_edge_indices() {
edge_iterator i, end;
tie(i, end) = edges(m_graph);
m_max_edge_index = renumber_edge_indices(i, end, 0);
}
- inline void
- remove_edge_and_renumber_indices(edge_iterator i)
- {
+ void remove_edge_and_renumber_indices(edge_iterator i) {
edge_iterator j = next(i), end = edges(m_graph.second);
edge_index_type n = get(edge_index, m_graph, *i);
@@ -259,40 +258,37 @@
m_max_edge_index = renumber_edge_indices(j, end, n);
}
- inline void renumber_indices()
- {
+ void renumber_indices() {
renumber_vertex_indices();
renumber_edge_indices();
}
// bundled property support
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
- vertex_bundled& operator [](vertex_descriptor v)
+ vertex_bundled& operator[](vertex_descriptor v)
{ return m_graph[v]; }
- const vertex_bundled& operator [](vertex_descriptor v) const
+ vertex_bundled const& operator[](vertex_descriptor v) const
{ return m_graph[v]; }
- edge_bundled& operator [](edge_descriptor e)
+ edge_bundled& operator[](edge_descriptor e)
{ return m_graph[e]; }
- const edge_bundled& operator [](edge_descriptor e) const
+ edge_bundled const& operator[](edge_descriptor e) const
{ return m_graph[e]; }
#endif
// Graph concepts
- static inline vertex_descriptor null_vertex()
+ static vertex_descriptor null_vertex()
{ return graph_type::null_vertex(); }
- inline void clear()
- {
+ void clear() {
m_graph.clear();
m_num_vertices = m_max_vertex_index = 0;
m_num_edges = m_max_edge_index = 0;
}
- inline void swap(undirected_graph& g)
- {
+ void swap(undirected_graph& g) {
m_graph.swap(g);
std::swap(m_num_vertices, g.m_num_vertices);
std::swap(m_max_vertex_index, g.m_max_vertex_index);
@@ -301,10 +297,9 @@
}
private:
- inline vertices_size_type
- renumber_vertex_indices(vertex_iterator i,
- vertex_iterator end,
- vertices_size_type n)
+ vertices_size_type renumber_vertex_indices(vertex_iterator i,
+ vertex_iterator end,
+ vertices_size_type n)
{
typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
IndexMap indices = get(vertex_index, m_graph);
@@ -314,10 +309,9 @@
return n;
}
- inline edges_size_type
- renumber_edge_indices(edge_iterator i,
- edge_iterator end,
- edges_size_type n)
+ edges_size_type renumber_edge_indices(edge_iterator i,
+ edge_iterator end,
+ edges_size_type n)
{
typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
IndexMap indices = get(edge_index, m_graph);
@@ -334,257 +328,204 @@
edge_index_type m_max_edge_index;
};
-// IncidenceGraph concepts
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
-source(typename undirected_graph<VP,EP,GP>::edge_descriptor e,
- const undirected_graph<VP,EP,GP> &g)
-{
- return source(e, g.impl());
-}
+#define UNDIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
+#define UNDIRECTED_GRAPH undirected_graph<VP,EP,GP>
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
-target(typename undirected_graph<VP,EP,GP>::edge_descriptor e,
- const undirected_graph<VP,EP,GP> &g)
-{
- return target(e, g.impl());
-}
-
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::degree_size_type
-out_degree(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
-{
- return out_degree(v, g.impl());
-}
+// IncidenceGraph concepts
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::vertex_descriptor
+source(typename UNDIRECTED_GRAPH::edge_descriptor e,
+ UNDIRECTED_GRAPH const& g)
+{ return source(e, g.impl()); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::vertex_descriptor
+target(typename UNDIRECTED_GRAPH::edge_descriptor e,
+ UNDIRECTED_GRAPH const& g)
+{ return target(e, g.impl()); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::degree_size_type
+out_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return out_degree(v, g.impl()); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::out_edge_iterator,
- typename undirected_graph<VP,EP,GP>::out_edge_iterator
+ typename UNDIRECTED_GRAPH::out_edge_iterator,
+ typename UNDIRECTED_GRAPH::out_edge_iterator
>
-out_edges(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
-{
- return out_edges(v, g.impl());
-}
+out_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return out_edges(v, g.impl()); }
// BidirectionalGraph concepts
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::degree_size_type
-in_degree(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
-{
- return in_degree(v, g.impl());
-}
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::degree_size_type
+in_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return in_degree(v, g.impl()); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::in_edge_iterator,
- typename undirected_graph<VP,EP,GP>::in_edge_iterator
+ typename UNDIRECTED_GRAPH::in_edge_iterator,
+ typename UNDIRECTED_GRAPH::in_edge_iterator
>
-in_edges(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
-{
- return in_edges(v, g.impl());
-}
-
+in_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return in_edges(v, g.impl()); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::out_edge_iterator,
- typename undirected_graph<VP,EP,GP>::out_edge_iterator
+ typename UNDIRECTED_GRAPH::out_edge_iterator,
+ typename UNDIRECTED_GRAPH::out_edge_iterator
>
-incident_edges(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
-{
- return out_edges(v, g.impl());
-}
-
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::degree_size_type
-degree(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
-{
- return degree(v, g.impl());
-}
+incident_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return out_edges(v, g.impl()); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::degree_size_type
+degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return degree(v, g.impl()); }
// AdjacencyGraph concepts
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::adjacency_iterator,
- typename undirected_graph<VP,EP,GP>::adjacency_iterator
+ typename UNDIRECTED_GRAPH::adjacency_iterator,
+ typename UNDIRECTED_GRAPH::adjacency_iterator
>
-adjacent_vertices(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
-{
- return adjacent_vertices(v, g.impl());
-}
-
-template <class VP, class EP, class GP>
-typename undirected_graph<VP,EP,GP>::vertex_descriptor
-vertex(typename undirected_graph<VP,EP,GP>::vertices_size_type n,
- const undirected_graph<VP,EP,GP>& g)
-{
- return vertex(g.impl());
-}
-
-template <class VP, class EP, class GP>
-std::pair<typename undirected_graph<VP,EP,GP>::edge_descriptor, bool>
-edge(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
- typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
-{
- return edge(u, v, g.impl());
-}
+adjacent_vertices(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return adjacent_vertices(v, g.impl()); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+typename UNDIRECTED_GRAPH::vertex_descriptor
+vertex(typename UNDIRECTED_GRAPH::vertices_size_type n,
+ UNDIRECTED_GRAPH const& g)
+{ return vertex(g.impl()); }
+
+template <UNDIRECTED_GRAPH_PARAMS>
+std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
+edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
+ typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
+{ return edge(u, v, g.impl()); }
// VertexListGraph concepts
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::vertices_size_type
-num_vertices(const undirected_graph<VP,EP,GP>& g)
-{
- return g.num_vertices();
-}
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::vertices_size_type
+num_vertices(UNDIRECTED_GRAPH const& g)
+{ return g.num_vertices(); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::vertex_iterator,
- typename undirected_graph<VP,EP,GP>::vertex_iterator
+ typename UNDIRECTED_GRAPH::vertex_iterator,
+ typename UNDIRECTED_GRAPH::vertex_iterator
>
-vertices(const undirected_graph<VP,EP,GP>& g)
-{
- return vertices(g.impl());
-}
+vertices(UNDIRECTED_GRAPH const& g)
+{ return vertices(g.impl()); }
// EdgeListGraph concepts
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::edges_size_type
-num_edges(const undirected_graph<VP,EP,GP>& g)
-{
- return g.num_edges();
-}
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::edges_size_type
+num_edges(UNDIRECTED_GRAPH const& g)
+{ return g.num_edges(); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline std::pair<
-typename undirected_graph<VP,EP,GP>::edge_iterator,
-typename undirected_graph<VP,EP,GP>::edge_iterator
+ typename UNDIRECTED_GRAPH::edge_iterator,
+ typename UNDIRECTED_GRAPH::edge_iterator
>
-edges(const undirected_graph<VP,EP,GP>& g)
-{
- return edges(g.impl());
-}
-
+edges(UNDIRECTED_GRAPH const& g)
+{ return edges(g.impl()); }
// MutableGraph concepts
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
-add_vertex(undirected_graph<VP,EP,GP> &g)
-{
- return g.add_vertex();
-}
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::vertex_descriptor
+add_vertex(UNDIRECTED_GRAPH& g)
+{ return g.add_vertex(); }
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::vertex_descriptor
+add_vertex(typename UNDIRECTED_GRAPH::vertex_property_type const& p,
+ UNDIRECTED_GRAPH& g)
+{ return g.add_vertex(p); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-clear_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
-undirected_graph<VP,EP,GP> &g)
-{
- return g.clear_vertex(v);
-}
+clear_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH& g)
+{ return g.clear_vertex(v); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-remove_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- undirected_graph<VP,EP,GP> &g)
-{
- return g.remove_vertex(v);
-}
+remove_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g)
+{ return g.remove_vertex(v); }
+template <UNDIRECTED_GRAPH_PARAMS>
+inline std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
+add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
+ typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH& g)
+{ return g.add_edge(u, v); }
+template <UNDIRECTED_GRAPH_PARAMS>
+inline std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
+add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
+ typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ typename UNDIRECTED_GRAPH::edge_property_type const& p,
+ UNDIRECTED_GRAPH& g)
+{ return g.add_edge(u, v, p); }
-template <class VP, class EP, class GP>
-inline std::pair<typename undirected_graph<VP,EP,GP>::edge_descriptor, bool>
-add_edge(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
- typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- undirected_graph<VP,EP,GP> &g)
-{
- return g.add_edge(u, v);
-}
-
-
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-remove_edge(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
- typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- undirected_graph<VP,EP,GP> &g)
-{
- return g.remove_edge(u, v);
-}
-
-
-template <class VP, class EP, class GP>
-inline void
-remove_edge(typename undirected_graph<VP,EP,GP>::edge_descriptor e,
- undirected_graph<VP,EP,GP> &g)
-{
- return g.remove_edge(e);
-}
-
+remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
+ typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH& g)
+{ return g.remove_edge(u, v); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-remove_edge(typename undirected_graph<VP,EP,GP>::edge_iterator i,
- undirected_graph<VP,EP,GP> &g)
-{
- return g.remove_edge(i);
-}
+remove_edge(typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH& g)
+{ return g.remove_edge(e); }
-template <class VP, class EP, class GP, class Predicate>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-remove_edge_if(Predicate pred,
- undirected_graph<VP,EP,GP> &g)
-
-{
- return remove_edge_if(pred, g.impl());
-}
+remove_edge(typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g)
+{ return g.remove_edge(i); }
+template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
+inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g)
+{ return remove_edge_if(pred, g.impl()); }
-template <class VP, class EP, class GP, class Predicate>
+template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
inline void
-remove_incident_edge_if(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+remove_incident_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
Predicate pred,
- undirected_graph<VP,EP,GP> &g)
-{
- return remove_out_edge_if(v, pred, g.impl());
-}
+ UNDIRECTED_GRAPH& g)
+{ return remove_out_edge_if(v, pred, g.impl()); }
-template <class VP, class EP, class GP, class Predicate>
+template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
inline void
-remove_out_edge_if(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- Predicate pred,
- undirected_graph<VP,EP,GP> &g)
-{
- return remove_out_edge_if(v, pred, g.impl());
-}
-
-template <class VP, class EP, class GP, class Predicate>
-inline void
-remove_in_edge_if(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- Predicate pred,
- undirected_graph<VP,EP,GP> &g)
-{
- return remove_in_edge_if(v, pred, g.impl());
-}
+remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ Predicate pred,
+ UNDIRECTED_GRAPH& g)
+{ return remove_out_edge_if(v, pred, g.impl()); }
+
+template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
+inline void
+remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ Predicate pred,
+ UNDIRECTED_GRAPH& g)
+{ return remove_in_edge_if(v, pred, g.impl()); }
// Helper code for working with property maps
-namespace detail
-{
- struct undirected_graph_vertex_property_selector
- {
+namespace detail {
+ struct undirected_graph_vertex_property_selector {
template <class UndirectedGraph, class Property, class Tag>
- struct bind_
- {
+ struct bind_ {
typedef typename UndirectedGraph::graph_type Graph;
typedef property_map<Graph, Tag> PropertyMap;
typedef typename PropertyMap::type type;
@@ -592,175 +533,151 @@
};
};
- struct undirected_graph_edge_property_selector
- {
+ struct undirected_graph_edge_property_selector {
template <class UndirectedGraph, class Property, class Tag>
- struct bind_
- {
+ struct bind_ {
typedef typename UndirectedGraph::graph_type Graph;
typedef property_map<Graph, Tag> PropertyMap;
typedef typename PropertyMap::type type;
typedef typename PropertyMap::const_type const_type;
};
};
-}
+} // namespace detail
template <>
struct vertex_property_selector<undirected_graph_tag>
-{
- typedef detail::undirected_graph_vertex_property_selector type;
-};
+{ typedef detail::undirected_graph_vertex_property_selector type; };
template <>
struct edge_property_selector<undirected_graph_tag>
-{
- typedef detail::undirected_graph_edge_property_selector type;
-};
+{ typedef detail::undirected_graph_edge_property_selector type; };
// PropertyGraph concepts
-template <class VP, class EP, class GP, typename Property>
-inline typename property_map<undirected_graph<VP,EP,GP>, Property>::type
-get(Property p, undirected_graph<VP,EP,GP>& g)
-{
- return get(p, g.impl());
-}
-
-template <class VP, class EP, class GP, typename Property>
-inline typename property_map<undirected_graph<VP,EP,GP>, Property>::const_type
-get(Property p, const undirected_graph<VP,EP,GP>& g)
-{
- return get(p, g.impl());
-}
+template <UNDIRECTED_GRAPH_PARAMS, typename Property>
+inline typename property_map<UNDIRECTED_GRAPH, Property>::type
+get(Property p, UNDIRECTED_GRAPH& g)
+{ return get(p, g.impl()); }
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Property>
+inline typename property_map<UNDIRECTED_GRAPH, Property>::const_type
+get(Property p, UNDIRECTED_GRAPH const& g)
+{ return get(p, g.impl()); }
-template <class VP, class EP, class GP, typename Property, typename Key>
+template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key>
inline typename property_traits<
- typename property_map<typename undirected_graph<VP,EP,GP>::graph_type, Property>::const_type
+ typename property_map<
+ typename UNDIRECTED_GRAPH::graph_type, Property
+ >::const_type
>::value_type
-get(Property p, const undirected_graph<VP,EP,GP> &g, const Key& k)
-{
- return get(p, g.impl(), k);
-}
-
-template <class VP, class EP, class GP, typename Property, typename Key, typename Value>
-inline void
-put(Property p, undirected_graph<VP,EP,GP> &g, const Key& k, const Value& v)
-{
- put(p, g.impl(), k, v);
-}
-
-template <class VP, class EP, class GP, class Property>
-typename graph_property<undirected_graph<VP,EP,GP>, Property>::type&
-get_property(undirected_graph<VP,EP,GP>& g, Property p)
-{
- return get_property(g.impl(), p);
-}
+get(Property p, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(p, g.impl(), k); }
-template <class VP, class EP, class GP, class Property>
-const typename graph_property<undirected_graph<VP,EP,GP>, Property>::type&
-get_property(const undirected_graph<VP,EP,GP>& g, Property p)
-{
- return get_property(g.impl(), p);
-}
-
-template <class VP, class EP, class GP, class Property, class Value>
-void
-set_property(undirected_graph<VP,EP,GP>& g, Property p, Value v)
-{
- return set_property(g.impl(), p, v);
-}
+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, class Property>
+inline typename graph_property<UNDIRECTED_GRAPH, Property>::type&
+get_property(UNDIRECTED_GRAPH& g, Property p)
+{ return get_property(g.impl(), p); }
+
+template <UNDIRECTED_GRAPH_PARAMS, class Property>
+inline typename graph_property<UNDIRECTED_GRAPH, Property>::type const&
+get_property(UNDIRECTED_GRAPH const& g, Property p)
+{ return get_property(g.impl(), p); }
+
+template <UNDIRECTED_GRAPH_PARAMS, class Property, class Value>
+inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v)
+{ return set_property(g.impl(), p, v); }
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
-template <class VP, class EP, class GP, typename Type, typename Bundle>
-inline typename property_map<undirected_graph<VP,EP,GP>, Type Bundle::*>::type
-get(Type Bundle::* p, undirected_graph<VP,EP,GP>& g)
-{
-typedef typename property_map<undirected_graph<VP,EP,GP>, Type Bundle::*>::type
- return_type;
-return return_type(&g, p);
+template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle>
+inline typename property_map<UNDIRECTED_GRAPH, Type Bundle::*>::type
+get(Type Bundle::* p, UNDIRECTED_GRAPH& g) {
+ typedef typename property_map<
+ UNDIRECTED_GRAPH, Type Bundle::*
+ >::type return_type;
+ return return_type(&g, p);
+}
+
+template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle>
+inline typename property_map<UNDIRECTED_GRAPH, Type Bundle::*>::const_type
+get(Type Bundle::* p, UNDIRECTED_GRAPH const& g) {
+ typedef typename property_map<
+ UNDIRECTED_GRAPH, Type Bundle::*
+ >::const_type return_type;
+ return return_type(&g, p);
}
-template <class VP, class EP, class GP, typename Type, typename Bundle>
-inline typename property_map<undirected_graph<VP,EP,GP>, Type Bundle::*>::const_type
-get(Type Bundle::* p, const undirected_graph<VP,EP,GP>& g)
-{
-typedef typename property_map<undirected_graph<VP,EP,GP>, Type Bundle::*>::const_type
- return_type;
-return return_type(&g, p);
-}
-
-template <class VP, class EP, class GP, typename Type, typename Bundle, typename Key>
+template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key>
inline Type
-get(Type Bundle::* p, const undirected_graph<VP,EP,GP> &g, const Key& k)
-{
-return get(p, g.impl(), k);
-}
+get(Type Bundle::* p, UNDIRECTED_GRAPH const& g, Key const& k)
+{ return get(p, g.impl(), k); }
-template <class VP, class EP, class GP, typename Type, typename Bundle, typename Key, typename Value>
+template <UNDIRECTED_GRAPH_PARAMS, typename Type, typename Bundle, typename Key, typename Value>
inline void
-put(Type Bundle::* p, undirected_graph<VP,EP,GP> &g, const Key& k, const Value& v)
-{
-// put(get(p, g.impl()), k, v);
-put(p, g.impl(), k, v);
-}
+put(Type Bundle::* p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
+{ put(p, g.impl(), k, v); }
#endif
-// Vertex index management
+// Indexed Vertex graph
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::vertex_index_type
-get_vertex_index(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::vertex_index_type
+get_vertex_index(typename UNDIRECTED_GRAPH::vertex_descriptor v,
+ UNDIRECTED_GRAPH const& g)
{ return get(vertex_index, g, v); }
-template <class VP, class EP, class GP>
-typename undirected_graph<VP,EP,GP>::vertex_index_type
-max_vertex_index(const undirected_graph<VP,EP,GP>& g)
+template <UNDIRECTED_GRAPH_PARAMS>
+typename UNDIRECTED_GRAPH::vertex_index_type
+max_vertex_index(UNDIRECTED_GRAPH const& g)
{ return g.max_vertex_index(); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-renumber_vertex_indices(undirected_graph<VP,EP,GP>& g)
+renumber_vertex_indices(UNDIRECTED_GRAPH& g)
{ g.renumber_vertex_indices(); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-remove_vertex_and_renumber_indices(typename undirected_graph<VP,EP,GP>::vertex_iterator i,
- undirected_graph<VP,EP,GP>& g)
+remove_vertex_and_renumber_indices(typename UNDIRECTED_GRAPH::vertex_iterator i,
+ UNDIRECTED_GRAPH& g)
{ g.remove_vertex_and_renumber_indices(i); }
// Edge index management
-template <class VP, class EP, class GP>
-inline typename undirected_graph<VP,EP,GP>::edge_index_type
-get_edge_index(typename undirected_graph<VP,EP,GP>::edge_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
+template <UNDIRECTED_GRAPH_PARAMS>
+inline typename UNDIRECTED_GRAPH::edge_index_type
+get_edge_index(typename UNDIRECTED_GRAPH::edge_descriptor v,
+ UNDIRECTED_GRAPH const& g)
{ return get(edge_index, g, v); }
-template <class VP, class EP, class GP>
-typename undirected_graph<VP,EP,GP>::edge_index_type
-max_edge_index(const undirected_graph<VP,EP,GP>& g)
+template <UNDIRECTED_GRAPH_PARAMS>
+typename UNDIRECTED_GRAPH::edge_index_type
+max_edge_index(UNDIRECTED_GRAPH const& g)
{ return g.max_edge_index(); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-renumber_edge_indices(undirected_graph<VP,EP,GP>& g)
-{
- g.renumber_edge_indices();
-}
+renumber_edge_indices(UNDIRECTED_GRAPH& g)
+{ g.renumber_edge_indices(); }
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-remove_edge_and_renumber_indices(typename undirected_graph<VP,EP,GP>::edge_iterator i,
- undirected_graph<VP,EP,GP>& g)
+remove_edge_and_renumber_indices(typename UNDIRECTED_GRAPH::edge_iterator i,
+ UNDIRECTED_GRAPH& g)
{ g.remove_edge_and_renumber_indices(i); }
// Index management
-template <class VP, class EP, class GP>
+template <UNDIRECTED_GRAPH_PARAMS>
inline void
-renumber_indices(undirected_graph<VP,EP,GP>& g)
+renumber_indices(UNDIRECTED_GRAPH& g)
{ g.renumber_indices(); }
+#undef UNDIRECTED_GRAPH_PARAMS
+#undef UNDIRECTED_GRAPH
+
} /* namespace boost */
#endif
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