|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r51091 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-02-08 09:25:07
Author: asutton
Date: 2009-02-08 09:25:06 EST (Sun, 08 Feb 2009)
New Revision: 51091
URL: http://svn.boost.org/trac/boost/changeset/51091
Log:
Integrating SOC 2007 code
Added:
trunk/boost/graph/directed_graph.hpp (contents, props changed)
- copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp
trunk/boost/graph/numeric_values.hpp (contents, props changed)
- copied, changed from r51086, /sandbox/SOC/2007/graphs/boost/graph/numeric_values.hpp
Text files modified:
trunk/boost/graph/directed_graph.hpp | 1275 ++++++++++++++++++++-------------------
trunk/boost/graph/graph_concepts.hpp | 1044 ++++++++++++++++++--------------
trunk/boost/graph/numeric_values.hpp | 70 -
3 files changed, 1247 insertions(+), 1142 deletions(-)
Copied: trunk/boost/graph/directed_graph.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp (original)
+++ trunk/boost/graph/directed_graph.hpp 2009-02-08 09:25:06 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
@@ -13,725 +13,736 @@
namespace boost
{
- struct directed_graph_tag { };
+struct directed_graph_tag { };
- template <
- typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property
- >
- class directed_graph
- {
- typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;
- typedef property<edge_index_t, unsigned, EdgeProperty> edge_property;
-
- public:
- typedef adjacency_list<listS,
- listS,
- bidirectionalS,
- vertex_property,
- edge_property,
- GraphProperty,
- listS> graph_type;
-
- private:
- // storage selectors
- typedef typename graph_type::vertex_list_selector vertex_list_selector;
- typedef typename graph_type::edge_list_selector edge_list_selector;
- typedef typename graph_type::out_edge_list_selector out_edge_list_selector;
- typedef typename graph_type::directed_selector directed_selector;
-
- 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;
- typedef typename graph_type::vertices_size_type vertices_size_type;
- typedef typename graph_type::edges_size_type edges_size_type;
- typedef typename graph_type::degree_size_type degree_size_type;
- typedef typename graph_type::vertex_descriptor vertex_descriptor;
- typedef typename graph_type::edge_descriptor edge_descriptor;
-
- // iterator types
- typedef typename graph_type::vertex_iterator vertex_iterator;
- typedef typename graph_type::edge_iterator edge_iterator;
- typedef typename graph_type::out_edge_iterator out_edge_iterator;
- typedef typename graph_type::in_edge_iterator in_edge_iterator;
- typedef typename graph_type::adjacency_iterator adjacency_iterator;
-
- // miscellaneous types
- typedef typename graph_type::directed_category directed_category;
- 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;
-
- inline directed_graph(const GraphProperty& p = GraphProperty())
- : 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)
- { }
-
- 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)
- , m_max_edge_index(0)
- { }
-
- 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)
- {
- // 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)
- {
- if(&g != this) {
- m_graph = g.m_graph;
- m_num_vertices = g.m_num_vertices;
- m_num_edges = g.m_num_edges;
- m_max_vertex_index = g.m_max_vertex_index;
- m_max_edge_index = g.m_max_edge_index;
- }
- return *this;
- }
-
- // The impl_() methods are not part of the public interface.
- inline graph_type& impl()
- { return m_graph; }
-
- inline const graph_type& impl() const
- { return m_graph; }
-
-
- // The following methods are not part of the public interface
- inline vertices_size_type num_vertices() const
- { return m_num_vertices; }
-
- inline vertex_descriptor add_vertex()
- {
- vertex_descriptor v = boost::add_vertex(m_graph);
- boost::put(vertex_index, m_graph, v, m_max_vertex_index);
- m_num_vertices++;
- m_max_vertex_index++;
- return v;
- }
-
- inline 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)
- {
- boost::remove_vertex(v, m_graph);
- --m_num_vertices;
- }
-
- inline 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);
- ++m_num_edges;
- ++m_max_edge_index;
- }
- return ret;
- }
-
- inline 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;
- for(tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) {
- if(boost::target(*i, m_graph) == v) {
- edges.push_back(*i);
- }
- }
- // remove all edges, (u, v)
- typename std::vector<edge_descriptor>::iterator
- j = edges.begin(), j_end = edges.end();
- for( ; j != j_end; ++j) {
- remove_edge(*j);
+/**
+* The directed_graph class template is a simplified version of the BGL
+* adjacency list. This class is provided for ease of use, but may not
+* perform as well as custom-defined adjacency list classes. Instances of
+* this template model the BidirectionalGraph, VertexIndexGraph, and
+* EdgeIndexGraph concepts. The graph is also fully mutable, supporting
+* both insertions and removals.
+*
+* @note Special care must be taken when removing vertices or edges since
+* those operations can invalidate the numbering of vertices.
+*/
+template <
+ typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
+ typename GraphProperty = no_property
+>
+class directed_graph
+{
+ // 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;
+
+public:
+ typedef adjacency_list<
+ listS, listS, bidirectionalS,
+ vertex_property, edge_property, GraphProperty,
+ listS
+ > graph_type;
+
+private:
+ // storage selectors
+ typedef typename graph_type::vertex_list_selector vertex_list_selector;
+ typedef typename graph_type::edge_list_selector edge_list_selector;
+ typedef typename graph_type::out_edge_list_selector out_edge_list_selector;
+ typedef typename graph_type::directed_selector directed_selector;
+
+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;
+ typedef typename graph_type::vertices_size_type vertices_size_type;
+ typedef typename graph_type::edges_size_type edges_size_type;
+ typedef typename graph_type::degree_size_type degree_size_type;
+ typedef typename graph_type::vertex_descriptor vertex_descriptor;
+ typedef typename graph_type::edge_descriptor edge_descriptor;
+
+ // iterator types
+ typedef typename graph_type::vertex_iterator vertex_iterator;
+ typedef typename graph_type::edge_iterator edge_iterator;
+ typedef typename graph_type::out_edge_iterator out_edge_iterator;
+ typedef typename graph_type::in_edge_iterator in_edge_iterator;
+ typedef typename graph_type::adjacency_iterator adjacency_iterator;
+
+ // miscellaneous types
+ typedef typename graph_type::directed_category directed_category;
+ 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;
+
+ inline directed_graph(const GraphProperty& p = GraphProperty())
+ : 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)
+ { }
+
+ 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)
+ , m_max_edge_index(0)
+ { }
+
+ 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)
+ {
+ // 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)
+ {
+ if(&g != this) {
+ m_graph = g.m_graph;
+ m_num_vertices = g.m_num_vertices;
+ m_num_edges = g.m_num_edges;
+ m_max_vertex_index = g.m_max_vertex_index;
+ m_max_edge_index = g.m_max_edge_index;
+ }
+ return *this;
+ }
+
+ // The impl_() methods are not part of the public interface.
+ inline graph_type& impl()
+ { return m_graph; }
+
+ inline const graph_type& impl() const
+ { return m_graph; }
+
+
+ // The following methods are not part of the public interface
+ inline vertices_size_type num_vertices() const
+ { return m_num_vertices; }
+
+ inline vertex_descriptor add_vertex()
+ {
+ vertex_descriptor v = boost::add_vertex(m_graph);
+ boost::put(vertex_index, m_graph, v, m_max_vertex_index);
+ m_num_vertices++;
+ m_max_vertex_index++;
+ return v;
+ }
+
+ inline 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)
+ {
+ boost::remove_vertex(v, m_graph);
+ --m_num_vertices;
+ }
+
+ inline 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);
+ ++m_num_edges;
+ ++m_max_edge_index;
+ }
+ return ret;
+ }
+
+ inline 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;
+ for(tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) {
+ if(boost::target(*i, m_graph) == v) {
+ edges.push_back(*i);
}
}
-
- inline void remove_edge(edge_iterator i)
- {
- remove_edge(*i);
+ // remove all edges, (u, v)
+ typename std::vector<edge_descriptor>::iterator
+ j = edges.begin(), j_end = edges.end();
+ for( ; j != j_end; ++j) {
+ remove_edge(*j);
}
+ }
- inline void remove_edge(edge_descriptor e)
- {
- boost::remove_edge(e, m_graph);
- --m_num_edges;
- }
+ inline void remove_edge(edge_iterator i)
+ {
+ remove_edge(*i);
+ }
- inline vertex_index_type max_vertex_index() const
- { return m_max_vertex_index; }
+ inline void remove_edge(edge_descriptor e)
+ {
+ boost::remove_edge(e, m_graph);
+ --m_num_edges;
+ }
- inline void
- renumber_vertex_indices()
- {
- vertex_iterator i, end;
- tie(i, end) = vertices(m_graph);
- m_max_vertex_index = renumber_vertex_indices(i, end, 0);
- }
+ inline vertex_index_type max_vertex_index() const
+ { return m_max_vertex_index; }
- inline 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);
+ inline void
+ renumber_vertex_indices()
+ {
+ vertex_iterator i, end;
+ tie(i, end) = vertices(m_graph);
+ m_max_vertex_index = renumber_vertex_indices(i, end, 0);
+ }
- // remove the offending vertex and renumber everything after
- remove_vertex(*i);
- m_max_vertex_index = renumber_vertex_indices(j, end, n);
- }
+ inline 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);
- inline edge_index_type
- max_edge_index() const
- { return m_max_edge_index; }
+ // remove the offending vertex and renumber everything after
+ remove_vertex(*i);
+ m_max_vertex_index = renumber_vertex_indices(j, end, n);
+ }
- inline 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 edge_index_type
+ max_edge_index() const
+ { return m_max_edge_index; }
- inline 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);
+ inline void
+ renumber_edge_indices()
+ {
+ edge_iterator i, end;
+ tie(i, end) = edges(m_graph);
+ m_max_edge_index = renumber_edge_indices(i, end, 0);
+ }
- // remove the offending edge and renumber everything after
- remove_edge(*i);
- m_max_edge_index = renumber_edge_indices(j, end, n);
- }
+ inline 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);
- inline void
- renumber_indices()
- {
- renumber_vertex_indices();
- renumber_edge_indices();
- }
+ // remove the offending edge and renumber everything after
+ remove_edge(*i);
+ m_max_edge_index = renumber_edge_indices(j, end, n);
+ }
- // bundled property support
- #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
- vertex_bundled& operator [](vertex_descriptor v)
- { return m_graph[v]; }
-
- const vertex_bundled& 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
- { return m_graph[e]; }
- #endif
-
- // Graph concepts
- static inline vertex_descriptor null_vertex()
- { return graph_type::null_vertex(); }
+ inline void
+ renumber_indices()
+ {
+ renumber_vertex_indices();
+ renumber_edge_indices();
+ }
- inline void clear()
- {
- m_graph.clear();
- m_num_vertices = m_max_vertex_index = 0;
- m_num_edges = m_max_edge_index = 0;
- }
+ // bundled property support
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+ vertex_bundled& operator[](vertex_descriptor v)
+ { return m_graph[v]; }
- inline void swap(directed_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);
- std::swap(m_num_edges, g.m_num_edges);
- std::swap(m_max_edge_index, g.m_max_edge_index);
- }
+ const vertex_bundled& operator[](vertex_descriptor v) const
+ { return m_graph[v]; }
- private:
- inline 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);
- for( ; i != end; ++i) {
- indices[*i] = n++;
- }
- return n;
- }
+ edge_bundled& operator[](edge_descriptor e)
+ { return m_graph[e]; }
- inline vertices_size_type
- renumber_edge_indices(edge_iterator i,
- edge_iterator end,
- vertices_size_type n)
- {
- typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
- IndexMap indices = get(edge_index, m_graph);
- for( ; i != end; ++i) {
- indices[*i] = n++;
- }
- return n;
- }
+ const edge_bundled& operator[](edge_descriptor e) const
+ { return m_graph[e]; }
+#endif
- graph_type m_graph;
- vertices_size_type m_num_vertices;
- edges_size_type m_num_edges;
- vertex_index_type m_max_vertex_index;
- edge_index_type m_max_edge_index;
- };
+ // Graph concepts
+ static inline vertex_descriptor null_vertex()
+ { return graph_type::null_vertex(); }
- // 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)
+ inline void clear()
{
- return source(e, g.impl());
+ m_graph.clear();
+ m_num_vertices = m_max_vertex_index = 0;
+ m_num_edges = m_max_edge_index = 0;
}
- 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)
+ inline void swap(directed_graph& g)
{
- return target(e, g.impl());
+ m_graph.swap(g);
+ 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);
+ std::swap(m_max_edge_index, g.m_max_edge_index);
}
- 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)
+private:
+ inline vertices_size_type
+ renumber_vertex_indices(vertex_iterator i,
+ vertex_iterator end,
+ vertices_size_type n)
{
- return out_degree(v, g.impl());
+ typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
+ IndexMap indices = get(vertex_index, m_graph);
+ for( ; i != end; ++i) {
+ indices[*i] = n++;
+ }
+ return n;
}
- template <class VP, class EP, class GP>
- inline std::pair<
- typename directed_graph<VP,EP,GP>::out_edge_iterator,
- typename directed_graph<VP,EP,GP>::out_edge_iterator
- >
- out_edges(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
+ inline vertices_size_type
+ renumber_edge_indices(edge_iterator i,
+ edge_iterator end,
+ vertices_size_type n)
{
- return out_edges(v, g.impl());
+ typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
+ IndexMap indices = get(edge_index, m_graph);
+ for( ; i != end; ++i) {
+ indices[*i] = n++;
+ }
+ return n;
}
- // 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());
- }
+ graph_type m_graph;
+ vertices_size_type m_num_vertices;
+ edges_size_type m_num_edges;
+ vertex_index_type m_max_vertex_index;
+ edge_index_type m_max_edge_index;
+};
- template <class VP, class EP, class GP>
- inline std::pair<
- typename directed_graph<VP,EP,GP>::in_edge_iterator,
- typename directed_graph<VP,EP,GP>::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());
- }
+// 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());
+}
- 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,
+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 degree(v, g.impl());
- }
-
- // AdjacencyGraph concepts
- template <class VP, class EP, class GP>
- inline std::pair<
- typename directed_graph<VP,EP,GP>::adjacency_iterator,
- typename directed_graph<VP,EP,GP>::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());
- }
+{
+ return out_degree(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>
+inline std::pair<
+ typename directed_graph<VP,EP,GP>::out_edge_iterator,
+ typename directed_graph<VP,EP,GP>::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());
+}
- 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());
- }
+// 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());
+}
- // 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 <class VP, class EP, class GP>
+inline std::pair<
+ typename directed_graph<VP,EP,GP>::in_edge_iterator,
+ typename directed_graph<VP,EP,GP>::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());
+}
- template <class VP, class EP, class GP>
- inline std::pair<
- typename directed_graph<VP,EP,GP>::vertex_iterator,
- typename directed_graph<VP,EP,GP>::vertex_iterator
- >
- vertices(const directed_graph<VP,EP,GP>& 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 <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 <class VP, class EP, class GP>
- inline std::pair<
- typename directed_graph<VP,EP,GP>::edge_iterator,
- typename directed_graph<VP,EP,GP>::edge_iterator
+// AdjacencyGraph concepts
+template <class VP, class EP, class GP>
+inline std::pair<
+ typename directed_graph<VP,EP,GP>::adjacency_iterator,
+ typename directed_graph<VP,EP,GP>::adjacency_iterator
>
- edges(const directed_graph<VP,EP,GP>& g)
- {
- return edges(g.impl());
- }
-
+adjacent_vertices(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
+ const directed_graph<VP,EP,GP>& g)
+{
+ return adjacent_vertices(v, 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>
+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());
+}
- 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);
- }
+// 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 <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>::vertex_iterator,
+ typename directed_graph<VP,EP,GP>::vertex_iterator
+>
+vertices(const directed_graph<VP,EP,GP>& 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 <class VP, class EP, class GP>
+inline std::pair<
+typename directed_graph<VP,EP,GP>::edge_iterator,
+typename directed_graph<VP,EP,GP>::edge_iterator
+>
+edges(const directed_graph<VP,EP,GP>& g)
+{
+ return edges(g.impl());
+}
- 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);
- }
+// 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
- 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
+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_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_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 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)
+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);
+}
- {
- return remove_edge_if(pred, g.impl());
- }
+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, 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 <class VP, class EP, class GP, class Predicate>
- inline void
- remove_in_edge_if(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- Predicate pred,
- directed_graph<VP,EP,GP> &g)
- {
- return remove_in_edge_if(v, pred, g.impl());
- }
+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);
+}
- // 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 <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 <>
- struct vertex_property_selector<directed_graph_tag>
- {
- typedef detail::directed_graph_vertex_property_selector type;
- };
+template <class VP, class EP, class GP, class Predicate>
+inline void
+remove_edge_if(Predicate pred,
+ directed_graph<VP,EP,GP> &g)
- template <>
- struct edge_property_selector<directed_graph_tag>
- {
- typedef detail::directed_graph_edge_property_selector type;
- };
+{
+ return remove_edge_if(pred, g.impl());
+}
- // 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 <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 <class VP, class EP, class GP, typename Property, typename Key>
- inline typename property_traits<
- typename property_map<typename directed_graph<VP,EP,GP>::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, class Predicate>
+inline void
+remove_in_edge_if(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
+ Predicate pred,
+ directed_graph<VP,EP,GP> &g)
+{
+ return remove_in_edge_if(v, pred, g.impl());
+}
- 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)
+// Helper code for working with property maps
+namespace detail
+{
+ struct directed_graph_vertex_property_selector
{
- put(p, g.impl(), k, v);
- }
+ 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 <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)
+ struct directed_graph_edge_property_selector
{
- return get_property(g.impl(), p);
- }
+ 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 <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 <>
+struct vertex_property_selector<directed_graph_tag>
+{
+ typedef detail::directed_graph_vertex_property_selector type;
+};
- template <class VP, class EP, class GP, class Property, class Value>
- void
- set_property(directed_graph<VP,EP,GP>& g, Property p, Value v)
- {
- return set_property(g.impl(), p, v);
- }
+template <>
+struct edge_property_selector<directed_graph_tag>
+{
+ typedef detail::directed_graph_edge_property_selector type;
+};
-#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);
- }
+// 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 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)
- {
- typedef typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::const_type
- return_type;
- return return_type(&g, p);
- }
+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 <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 <class VP, class EP, class GP, typename Property, typename Key>
+inline typename property_traits<
+ typename property_map<typename directed_graph<VP,EP,GP>::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 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);
+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);
- }
-#endif
+}
- // Vertex index management
+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);
+}
- 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)
- { 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)
- { return g.max_vertex_index(); }
+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 <class VP, class EP, class GP>
- inline void
- renumber_vertex_indices(directed_graph<VP,EP,GP>& g)
- { g.renumber_vertex_indices(); }
+template <class VP, class EP, class GP, class Property, class Value>
+void
+set_property(directed_graph<VP,EP,GP>& g, Property p, Value v)
+{
+ return set_property(g.impl(), p, v);
+}
- template <class VP, class EP, class GP>
- inline void
- remove_vertex_and_renumber_indices(typename directed_graph<VP,EP,GP>::vertex_iterator i,
- directed_graph<VP,EP,GP>& 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)
- { 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)
- { return g.max_edge_index(); }
+#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>
- inline void
- renumber_edge_indices(directed_graph<VP,EP,GP>& g)
- { g.renumber_edge_indices(); }
+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)
+{
+typedef typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::const_type
+ return_type;
+return return_type(&g, p);
+}
- template <class VP, class EP, class GP>
- inline void
- remove_edge_and_renumber_indices(typename directed_graph<VP,EP,GP>::edge_iterator i,
- directed_graph<VP,EP,GP>& g)
- { g.remove_edge_and_renumber_indices(i); }
+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)
+{
+return get(p, g.impl(), k);
+}
- // Index management
- template <class VP, class EP, class GP>
- inline void
- renumber_indices(directed_graph<VP,EP,GP>& g)
- { g.renumber_indices(); }
+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);
}
+#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)
+{ 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)
+{ return g.max_vertex_index(); }
+
+template <class VP, class EP, class GP>
+inline void
+renumber_vertex_indices(directed_graph<VP,EP,GP>& g)
+{ g.renumber_vertex_indices(); }
+
+template <class VP, class EP, class GP>
+inline void
+remove_vertex_and_renumber_indices(typename directed_graph<VP,EP,GP>::vertex_iterator i,
+ directed_graph<VP,EP,GP>& 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)
+{ 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)
+{ return g.max_edge_index(); }
+
+template <class VP, class EP, class GP>
+inline void
+renumber_edge_indices(directed_graph<VP,EP,GP>& g)
+{ g.renumber_edge_indices(); }
+
+template <class VP, class EP, class GP>
+inline void
+remove_edge_and_renumber_indices(typename directed_graph<VP,EP,GP>::edge_iterator i,
+ directed_graph<VP,EP,GP>& g)
+{ g.remove_edge_and_renumber_indices(i); }
+
+// Index management
+template <class VP, class EP, class GP>
+inline void
+renumber_indices(directed_graph<VP,EP,GP>& g)
+{ g.renumber_indices(); }
+
+} /* namespace boost */
#endif
Modified: trunk/boost/graph/graph_concepts.hpp
==============================================================================
--- trunk/boost/graph/graph_concepts.hpp (original)
+++ trunk/boost/graph/graph_concepts.hpp 2009-02-08 09:25:06 EST (Sun, 08 Feb 2009)
@@ -3,6 +3,8 @@
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
+// Copyright 2009, Andrew Sutton
+//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
@@ -12,14 +14,14 @@
#define BOOST_GRAPH_CONCEPTS_HPP
#include <boost/config.hpp>
-#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
+#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/graph/numeric_values.hpp>
#include <boost/concept_check.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/concept/detail/concept_def.hpp>
-
namespace boost
{
// dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
@@ -34,477 +36,591 @@
&& !BOOST_WORKAROUND(__GNUC__, <= 2) \
&& !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
# define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
-#endif
+#endif
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
template <class T>
typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
-#endif
+#endif
+
+ namespace concepts {
+ BOOST_concept(MultiPassInputIterator,(T)) {
+ BOOST_CONCEPT_USAGE(MultiPassInputIterator) {
+ BOOST_CONCEPT_ASSERT((InputIterator<T>));
+ }
+ };
+
+ BOOST_concept(Graph,(G))
+ {
+ typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits<G>::directed_category directed_category;
+ typedef typename graph_traits<G>::edge_parallel_category
+ edge_parallel_category;
+
+ typedef typename graph_traits<G>::traversal_category
+ traversal_category;
+
+ BOOST_CONCEPT_USAGE(Graph)
+ {
+ BOOST_CONCEPT_ASSERT((DefaultConstructible<vertex_descriptor>));
+ BOOST_CONCEPT_ASSERT((EqualityComparable<vertex_descriptor>));
+ BOOST_CONCEPT_ASSERT((Assignable<vertex_descriptor>));
+ }
+ G g;
+ };
+
+ BOOST_concept(IncidenceGraph,(G))
+ : Graph<G>
+ {
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+ typedef typename graph_traits<G>::out_edge_iterator
+ out_edge_iterator;
+
+ typedef typename graph_traits<G>::traversal_category
+ traversal_category;
+
+ BOOST_CONCEPT_USAGE(IncidenceGraph) {
+ BOOST_CONCEPT_ASSERT((MultiPassInputIterator<out_edge_iterator>));
+ BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
+ BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
+ BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
+ BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
+ incidence_graph_tag>));
+
+ p = out_edges(u, g);
+ n = out_degree(u, g);
+ e = *p.first;
+ u = source(e, g);
+ v = target(e, g);
+ const_constraints(g);
+ }
+ void const_constraints(const G& cg) {
+ p = out_edges(u, cg);
+ n = out_degree(u, cg);
+ e = *p.first;
+ u = source(e, cg);
+ v = target(e, cg);
+ }
+ std::pair<out_edge_iterator, out_edge_iterator> p;
+ typename graph_traits<G>::vertex_descriptor u, v;
+ typename graph_traits<G>::edge_descriptor e;
+ typename graph_traits<G>::degree_size_type n;
+ G g;
+ };
+
+ BOOST_concept(BidirectionalGraph,(G))
+ : IncidenceGraph<G>
+ {
+ typedef typename graph_traits<G>::in_edge_iterator
+ in_edge_iterator;
+ typedef typename graph_traits<G>::traversal_category
+ traversal_category;
+
+ BOOST_CONCEPT_USAGE(BidirectionalGraph) {
+ BOOST_CONCEPT_ASSERT((MultiPassInputIterator<in_edge_iterator>));
+ BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
+ bidirectional_graph_tag>));
+
+ p = in_edges(v, g);
+ n = in_degree(v, g);
+ e = *p.first;
+ const_constraints(g);
+ }
+ void const_constraints(const G& cg) {
+ p = in_edges(v, cg);
+ n = in_degree(v, cg);
+ e = *p.first;
+ }
+ std::pair<in_edge_iterator, in_edge_iterator> p;
+ typename graph_traits<G>::vertex_descriptor v;
+ typename graph_traits<G>::edge_descriptor e;
+ typename graph_traits<G>::degree_size_type n;
+ G g;
+ };
+
+ BOOST_concept(AdjacencyGraph,(G))
+ : Graph<G>
+ {
+ typedef typename graph_traits<G>::adjacency_iterator
+ adjacency_iterator;
+ typedef typename graph_traits<G>::traversal_category
+ traversal_category;
+
+ BOOST_CONCEPT_USAGE(AdjacencyGraph) {
+ BOOST_CONCEPT_ASSERT((MultiPassInputIterator<adjacency_iterator>));
+ BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
+ adjacency_graph_tag>));
+
+ p = adjacent_vertices(v, g);
+ v = *p.first;
+ const_constraints(g);
+ }
+ void const_constraints(const G& cg) {
+ p = adjacent_vertices(v, cg);
+ }
+ std::pair<adjacency_iterator,adjacency_iterator> p;
+ typename graph_traits<G>::vertex_descriptor v;
+ G g;
+ };
- namespace concepts {
- BOOST_concept(MultiPassInputIterator,(T)) {
- BOOST_CONCEPT_USAGE(MultiPassInputIterator) {
- BOOST_CONCEPT_ASSERT((InputIterator<T>));
- }
- };
-
- BOOST_concept(Graph,(G))
- {
- typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<G>::directed_category directed_category;
- typedef typename graph_traits<G>::edge_parallel_category
- edge_parallel_category;
-
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
-
- BOOST_CONCEPT_USAGE(Graph)
- {
- BOOST_CONCEPT_ASSERT((DefaultConstructible<vertex_descriptor>));
- BOOST_CONCEPT_ASSERT((EqualityComparable<vertex_descriptor>));
- BOOST_CONCEPT_ASSERT((Assignable<vertex_descriptor>));
- }
- G g;
- };
-
- BOOST_concept(IncidenceGraph,(G))
- : Graph<G>
- {
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
- typedef typename graph_traits<G>::out_edge_iterator
- out_edge_iterator;
-
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
-
- BOOST_CONCEPT_USAGE(IncidenceGraph) {
- BOOST_CONCEPT_ASSERT((MultiPassInputIterator<out_edge_iterator>));
- BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
- BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
- BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
- BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
- incidence_graph_tag>));
-
- p = out_edges(u, g);
- n = out_degree(u, g);
- e = *p.first;
- u = source(e, g);
- v = target(e, g);
- const_constraints(g);
- }
- void const_constraints(const G& cg) {
- p = out_edges(u, cg);
- n = out_degree(u, cg);
- e = *p.first;
- u = source(e, cg);
- v = target(e, cg);
- }
- std::pair<out_edge_iterator, out_edge_iterator> p;
- typename graph_traits<G>::vertex_descriptor u, v;
- typename graph_traits<G>::edge_descriptor e;
- typename graph_traits<G>::degree_size_type n;
- G g;
- };
-
- BOOST_concept(BidirectionalGraph,(G))
- : IncidenceGraph<G>
- {
- typedef typename graph_traits<G>::in_edge_iterator
- in_edge_iterator;
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
-
- BOOST_CONCEPT_USAGE(BidirectionalGraph) {
- BOOST_CONCEPT_ASSERT((MultiPassInputIterator<in_edge_iterator>));
- BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
- bidirectional_graph_tag>));
-
- p = in_edges(v, g);
- n = in_degree(v, g);
- e = *p.first;
- const_constraints(g);
- }
- void const_constraints(const G& cg) {
- p = in_edges(v, cg);
- n = in_degree(v, cg);
- e = *p.first;
- }
- std::pair<in_edge_iterator, in_edge_iterator> p;
- typename graph_traits<G>::vertex_descriptor v;
- typename graph_traits<G>::edge_descriptor e;
- typename graph_traits<G>::degree_size_type n;
- G g;
- };
-
- BOOST_concept(AdjacencyGraph,(G))
- : Graph<G>
- {
- typedef typename graph_traits<G>::adjacency_iterator
- adjacency_iterator;
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
-
- BOOST_CONCEPT_USAGE(AdjacencyGraph) {
- BOOST_CONCEPT_ASSERT((MultiPassInputIterator<adjacency_iterator>));
- BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
- adjacency_graph_tag>));
-
- p = adjacent_vertices(v, g);
- v = *p.first;
- const_constraints(g);
- }
- void const_constraints(const G& cg) {
- p = adjacent_vertices(v, cg);
- }
- std::pair<adjacency_iterator,adjacency_iterator> p;
- typename graph_traits<G>::vertex_descriptor v;
- G g;
- };
-
- BOOST_concept(VertexListGraph,(G))
- : Graph<G>
- {
- typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
-
- BOOST_CONCEPT_USAGE(VertexListGraph) {
- BOOST_CONCEPT_ASSERT((MultiPassInputIterator<vertex_iterator>));
- BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
- vertex_list_graph_tag>));
+ BOOST_concept(VertexListGraph,(G))
+ : Graph<G>
+ {
+ typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
+ typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
+ typedef typename graph_traits<G>::traversal_category
+ traversal_category;
+
+ BOOST_CONCEPT_USAGE(VertexListGraph) {
+ BOOST_CONCEPT_ASSERT((MultiPassInputIterator<vertex_iterator>));
+ BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
+ vertex_list_graph_tag>));
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
- // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
- // you want to use vector_as_graph, it is! I'm sure the graph
- // library leaves these out all over the place. Probably a
- // redesign involving specializing a template with a static
- // member function is in order :(
- using boost::vertices;
-#endif
- p = vertices(g);
- v = *p.first;
- const_constraints(g);
- }
- void const_constraints(const G& cg) {
+ // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
+ // you want to use vector_as_graph, it is! I'm sure the graph
+ // library leaves these out all over the place. Probably a
+ // redesign involving specializing a template with a static
+ // member function is in order :(
+ using boost::vertices;
+#endif
+ p = vertices(g);
+ v = *p.first;
+ const_constraints(g);
+ }
+ void const_constraints(const G& cg) {
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
- // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
- // you want to use vector_as_graph, it is! I'm sure the graph
- // library leaves these out all over the place. Probably a
- // redesign involving specializing a template with a static
- // member function is in order :(
- using boost::vertices;
-#endif
-
- p = vertices(cg);
- v = *p.first;
- V = num_vertices(cg);
- }
- std::pair<vertex_iterator,vertex_iterator> p;
- typename graph_traits<G>::vertex_descriptor v;
- G g;
- vertices_size_type V;
- };
-
- BOOST_concept(EdgeListGraph,(G))
- : Graph<G>
- {
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
- typedef typename graph_traits<G>::edge_iterator edge_iterator;
- typedef typename graph_traits<G>::edges_size_type edges_size_type;
- typedef typename graph_traits<G>::traversal_category
- traversal_category;
-
- BOOST_CONCEPT_USAGE(EdgeListGraph) {
- BOOST_CONCEPT_ASSERT((MultiPassInputIterator<edge_iterator>));
- BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
- BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
- BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
- BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
- edge_list_graph_tag>));
-
- p = edges(g);
- e = *p.first;
- u = source(e, g);
- v = target(e, g);
- const_constraints(g);
- }
- void const_constraints(const G& cg) {
- p = edges(cg);
- E = num_edges(cg);
- e = *p.first;
- u = source(e, cg);
- v = target(e, cg);
- }
- std::pair<edge_iterator,edge_iterator> p;
- typename graph_traits<G>::vertex_descriptor u, v;
- typename graph_traits<G>::edge_descriptor e;
- edges_size_type E;
- G g;
- };
-
- BOOST_concept(VertexAndEdgeListGraph,(G))
- : VertexListGraph<G>
- , EdgeListGraph<G>
- {
- };
-
- // Where to put the requirement for this constructor?
- // G g(n_vertices);
- // Not in mutable graph, then LEDA graph's can't be models of
- // MutableGraph.
-
- BOOST_concept(EdgeMutableGraph,(G))
- {
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
-
- BOOST_CONCEPT_USAGE(EdgeMutableGraph) {
- p = add_edge(u, v, g);
- remove_edge(u, v, g);
- remove_edge(e, g);
- clear_vertex(v, g);
- }
- G g;
- edge_descriptor e;
- std::pair<edge_descriptor, bool> p;
- typename graph_traits<G>::vertex_descriptor u, v;
- };
-
- BOOST_concept(VertexMutableGraph,(G))
- {
-
- BOOST_CONCEPT_USAGE(VertexMutableGraph) {
- v = add_vertex(g);
- remove_vertex(v, g);
- }
- G g;
- typename graph_traits<G>::vertex_descriptor u, v;
- };
-
- BOOST_concept(MutableGraph,(G))
- : EdgeMutableGraph<G>
- , VertexMutableGraph<G>
- {
- };
-
- template <class edge_descriptor>
- struct dummy_edge_predicate {
- bool operator()(const edge_descriptor&) const {
- return false;
- }
- };
-
- BOOST_concept(MutableIncidenceGraph,(G))
- : MutableGraph<G>
- {
- BOOST_CONCEPT_USAGE(MutableIncidenceGraph) {
- remove_edge(iter, g);
- remove_out_edge_if(u, p, g);
- }
- G g;
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- typename boost::graph_traits<G>::vertex_descriptor u;
- typename boost::graph_traits<G>::out_edge_iterator iter;
- };
-
- BOOST_concept(MutableBidirectionalGraph,(G))
- : MutableIncidenceGraph<G>
- {
- BOOST_CONCEPT_USAGE(MutableBidirectionalGraph)
- {
- remove_in_edge_if(u, p, g);
- }
- G g;
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- typename boost::graph_traits<G>::vertex_descriptor u;
- };
-
- BOOST_concept(MutableEdgeListGraph,(G))
- : EdgeMutableGraph<G>
- {
- BOOST_CONCEPT_USAGE(MutableEdgeListGraph) {
- remove_edge_if(p, g);
- }
- G g;
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- };
-
- BOOST_concept(VertexMutablePropertyGraph,(G))
- : VertexMutableGraph<G>
- {
- BOOST_CONCEPT_USAGE(VertexMutablePropertyGraph) {
- v = add_vertex(vp, g);
- }
- G g;
- typename graph_traits<G>::vertex_descriptor v;
- typename vertex_property<G>::type vp;
- };
-
- BOOST_concept(EdgeMutablePropertyGraph,(G))
- : EdgeMutableGraph<G>
- {
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
-
- BOOST_CONCEPT_USAGE(EdgeMutablePropertyGraph) {
- p = add_edge(u, v, ep, g);
- }
- G g;
- std::pair<edge_descriptor, bool> p;
- typename graph_traits<G>::vertex_descriptor u, v;
- typename edge_property<G>::type ep;
- };
-
- BOOST_concept(AdjacencyMatrix,(G))
- : Graph<G>
- {
- typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
-
- BOOST_CONCEPT_USAGE(AdjacencyMatrix) {
- p = edge(u, v, g);
- const_constraints(g);
- }
- void const_constraints(const G& cg) {
- p = edge(u, v, cg);
- }
- typename graph_traits<G>::vertex_descriptor u, v;
- std::pair<edge_descriptor, bool> p;
- G g;
- };
-
- BOOST_concept(ReadablePropertyGraph,(G)(X)(Property))
- : Graph<G>
- {
- typedef typename property_map<G, Property>::const_type const_Map;
-
- BOOST_CONCEPT_USAGE(ReadablePropertyGraph)
- {
- BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<const_Map, X>));
-
- const_constraints(g);
- }
- void const_constraints(const G& cg) {
- const_Map pmap = get(Property(), cg);
- pval = get(Property(), cg, x);
- ignore_unused_variable_warning(pmap);
- }
- G g;
- X x;
- typename property_traits<const_Map>::value_type pval;
- };
-
- BOOST_concept(PropertyGraph,(G)(X)(Property))
- : ReadablePropertyGraph<G, X, Property>
- {
- typedef typename property_map<G, Property>::type Map;
- BOOST_CONCEPT_USAGE(PropertyGraph) {
- BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<Map, X>));
-
- Map pmap = get(Property(), g);
- pval = get(Property(), g, x);
- put(Property(), g, x, pval);
- ignore_unused_variable_warning(pmap);
- }
- G g;
- X x;
- typename property_traits<Map>::value_type pval;
- };
-
- BOOST_concept(LvaluePropertyGraph,(G)(X)(Property))
- : ReadablePropertyGraph<G, X, Property>
- {
- typedef typename property_map<G, Property>::type Map;
- typedef typename property_map<G, Property>::const_type const_Map;
-
- BOOST_CONCEPT_USAGE(LvaluePropertyGraph) {
- BOOST_CONCEPT_ASSERT((LvaluePropertyMapConcept<const_Map, X>));
-
- pval = get(Property(), g, x);
- put(Property(), g, x, pval);
- }
- G g;
- X x;
- typename property_traits<Map>::value_type pval;
- };
-
- // This needs to move out of the graph library
- BOOST_concept(Buffer,(B))
- {
- BOOST_CONCEPT_USAGE(Buffer) {
- b.push(t);
- b.pop();
- typename B::value_type& v = b.top();
- const_constraints(b);
- ignore_unused_variable_warning(v);
- }
- void const_constraints(const B& cb) {
- const typename B::value_type& v = cb.top();
- n = cb.size();
- bool e = cb.empty();
- ignore_unused_variable_warning(v);
- ignore_unused_variable_warning(e);
- }
- typename B::size_type n;
- typename B::value_type t;
- B b;
- };
-
- BOOST_concept(ColorValue,(C))
- : EqualityComparable<C>
- , DefaultConstructible<C>
- {
- BOOST_CONCEPT_USAGE(ColorValue) {
- c = color_traits<C>::white();
- c = color_traits<C>::gray();
- c = color_traits<C>::black();
- }
- C c;
- };
-
- BOOST_concept(BasicMatrix,(M)(I)(V))
- {
- BOOST_CONCEPT_USAGE(BasicMatrix) {
- V& elt = A[i][j];
- const_constraints(A);
- ignore_unused_variable_warning(elt);
- }
- void const_constraints(const M& cA) {
- const V& elt = cA[i][j];
- ignore_unused_variable_warning(elt);
- }
- M A;
- I i, j;
- };
-
- } // end namespace concepts
-
- using boost::concepts::MultiPassInputIteratorConcept;
- using boost::concepts::GraphConcept;
- using boost::concepts::IncidenceGraphConcept;
- using boost::concepts::BidirectionalGraphConcept;
- using boost::concepts::AdjacencyGraphConcept;
- using boost::concepts::VertexListGraphConcept;
- using boost::concepts::EdgeListGraphConcept;
- using boost::concepts::VertexAndEdgeListGraphConcept;
- using boost::concepts::EdgeMutableGraphConcept;
- using boost::concepts::VertexMutableGraphConcept;
- using boost::concepts::MutableGraphConcept;
- using boost::concepts::MutableIncidenceGraphConcept;
- using boost::concepts::MutableBidirectionalGraphConcept;
- using boost::concepts::MutableEdgeListGraphConcept;
- using boost::concepts::VertexMutablePropertyGraphConcept;
- using boost::concepts::EdgeMutablePropertyGraphConcept;
- using boost::concepts::AdjacencyMatrixConcept;
- using boost::concepts::ReadablePropertyGraphConcept;
- using boost::concepts::PropertyGraphConcept;
- using boost::concepts::LvaluePropertyGraphConcept;
- using boost::concepts::BufferConcept;
- using boost::concepts::ColorValueConcept;
- using boost::concepts::BasicMatrixConcept;
-} // namespace boost
+ // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
+ // you want to use vector_as_graph, it is! I'm sure the graph
+ // library leaves these out all over the place. Probably a
+ // redesign involving specializing a template with a static
+ // member function is in order :(
+ using boost::vertices;
+#endif
+
+ p = vertices(cg);
+ v = *p.first;
+ V = num_vertices(cg);
+ }
+ std::pair<vertex_iterator,vertex_iterator> p;
+ typename graph_traits<G>::vertex_descriptor v;
+ G g;
+ vertices_size_type V;
+ };
+
+ BOOST_concept(EdgeListGraph,(G))
+ : Graph<G>
+ {
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+ typedef typename graph_traits<G>::edge_iterator edge_iterator;
+ typedef typename graph_traits<G>::edges_size_type edges_size_type;
+ typedef typename graph_traits<G>::traversal_category
+ traversal_category;
+
+ BOOST_CONCEPT_USAGE(EdgeListGraph) {
+ BOOST_CONCEPT_ASSERT((MultiPassInputIterator<edge_iterator>));
+ BOOST_CONCEPT_ASSERT((DefaultConstructible<edge_descriptor>));
+ BOOST_CONCEPT_ASSERT((EqualityComparable<edge_descriptor>));
+ BOOST_CONCEPT_ASSERT((Assignable<edge_descriptor>));
+ BOOST_CONCEPT_ASSERT((Convertible<traversal_category,
+ edge_list_graph_tag>));
+
+ p = edges(g);
+ e = *p.first;
+ u = source(e, g);
+ v = target(e, g);
+ const_constraints(g);
+ }
+ void const_constraints(const G& cg) {
+ p = edges(cg);
+ E = num_edges(cg);
+ e = *p.first;
+ u = source(e, cg);
+ v = target(e, cg);
+ }
+ std::pair<edge_iterator,edge_iterator> p;
+ typename graph_traits<G>::vertex_descriptor u, v;
+ typename graph_traits<G>::edge_descriptor e;
+ edges_size_type E;
+ G g;
+ };
+
+ BOOST_concept(VertexAndEdgeListGraph,(G))
+ : VertexListGraph<G>
+ , EdgeListGraph<G>
+ {
+ };
+
+ // Where to put the requirement for this constructor?
+ // G g(n_vertices);
+ // Not in mutable graph, then LEDA graph's can't be models of
+ // MutableGraph.
+ BOOST_concept(EdgeMutableGraph,(G))
+ {
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+
+ BOOST_CONCEPT_USAGE(EdgeMutableGraph) {
+ p = add_edge(u, v, g);
+ remove_edge(u, v, g);
+ remove_edge(e, g);
+ clear_vertex(v, g);
+ }
+ G g;
+ edge_descriptor e;
+ std::pair<edge_descriptor, bool> p;
+ typename graph_traits<G>::vertex_descriptor u, v;
+ };
+
+ BOOST_concept(VertexMutableGraph,(G))
+ {
+
+ BOOST_CONCEPT_USAGE(VertexMutableGraph) {
+ v = add_vertex(g);
+ remove_vertex(v, g);
+ }
+ G g;
+ typename graph_traits<G>::vertex_descriptor u, v;
+ };
+
+ BOOST_concept(MutableGraph,(G))
+ : EdgeMutableGraph<G>
+ , VertexMutableGraph<G>
+ {
+ };
+
+ template <class edge_descriptor>
+ struct dummy_edge_predicate {
+ bool operator()(const edge_descriptor&) const {
+ return false;
+ }
+ };
+
+ BOOST_concept(MutableIncidenceGraph,(G))
+ : MutableGraph<G>
+ {
+ BOOST_CONCEPT_USAGE(MutableIncidenceGraph) {
+ remove_edge(iter, g);
+ remove_out_edge_if(u, p, g);
+ }
+ G g;
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+ dummy_edge_predicate<edge_descriptor> p;
+ typename boost::graph_traits<G>::vertex_descriptor u;
+ typename boost::graph_traits<G>::out_edge_iterator iter;
+ };
+
+ BOOST_concept(MutableBidirectionalGraph,(G))
+ : MutableIncidenceGraph<G>
+ {
+ BOOST_CONCEPT_USAGE(MutableBidirectionalGraph)
+ {
+ remove_in_edge_if(u, p, g);
+ }
+ G g;
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+ dummy_edge_predicate<edge_descriptor> p;
+ typename boost::graph_traits<G>::vertex_descriptor u;
+ };
+
+ BOOST_concept(MutableEdgeListGraph,(G))
+ : EdgeMutableGraph<G>
+ {
+ BOOST_CONCEPT_USAGE(MutableEdgeListGraph) {
+ remove_edge_if(p, g);
+ }
+ G g;
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+ dummy_edge_predicate<edge_descriptor> p;
+ };
+
+ BOOST_concept(VertexMutablePropertyGraph,(G))
+ : VertexMutableGraph<G>
+ {
+ BOOST_CONCEPT_USAGE(VertexMutablePropertyGraph) {
+ v = add_vertex(vp, g);
+ }
+ G g;
+ typename graph_traits<G>::vertex_descriptor v;
+ typename vertex_property<G>::type vp;
+ };
+
+ BOOST_concept(EdgeMutablePropertyGraph,(G))
+ : EdgeMutableGraph<G>
+ {
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+
+ BOOST_CONCEPT_USAGE(EdgeMutablePropertyGraph) {
+ p = add_edge(u, v, ep, g);
+ }
+ G g;
+ std::pair<edge_descriptor, bool> p;
+ typename graph_traits<G>::vertex_descriptor u, v;
+ typename edge_property<G>::type ep;
+ };
+
+ BOOST_concept(AdjacencyMatrix,(G))
+ : Graph<G>
+ {
+ typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
+
+ BOOST_CONCEPT_USAGE(AdjacencyMatrix) {
+ p = edge(u, v, g);
+ const_constraints(g);
+ }
+ void const_constraints(const G& cg) {
+ p = edge(u, v, cg);
+ }
+ typename graph_traits<G>::vertex_descriptor u, v;
+ std::pair<edge_descriptor, bool> p;
+ G g;
+ };
+
+ BOOST_concept(ReadablePropertyGraph,(G)(X)(Property))
+ : Graph<G>
+ {
+ typedef typename property_map<G, Property>::const_type const_Map;
+
+ BOOST_CONCEPT_USAGE(ReadablePropertyGraph)
+ {
+ BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept<const_Map, X>));
+
+ const_constraints(g);
+ }
+ void const_constraints(const G& cg) {
+ const_Map pmap = get(Property(), cg);
+ pval = get(Property(), cg, x);
+ ignore_unused_variable_warning(pmap);
+ }
+ G g;
+ X x;
+ typename property_traits<const_Map>::value_type pval;
+ };
+
+ BOOST_concept(PropertyGraph,(G)(X)(Property))
+ : ReadablePropertyGraph<G, X, Property>
+ {
+ typedef typename property_map<G, Property>::type Map;
+ BOOST_CONCEPT_USAGE(PropertyGraph) {
+ BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept<Map, X>));
+
+ Map pmap = get(Property(), g);
+ pval = get(Property(), g, x);
+ put(Property(), g, x, pval);
+ ignore_unused_variable_warning(pmap);
+ }
+ G g;
+ X x;
+ typename property_traits<Map>::value_type pval;
+ };
+
+ BOOST_concept(LvaluePropertyGraph,(G)(X)(Property))
+ : ReadablePropertyGraph<G, X, Property>
+ {
+ typedef typename property_map<G, Property>::type Map;
+ typedef typename property_map<G, Property>::const_type const_Map;
+
+ BOOST_CONCEPT_USAGE(LvaluePropertyGraph) {
+ BOOST_CONCEPT_ASSERT((LvaluePropertyMapConcept<const_Map, X>));
+
+ pval = get(Property(), g, x);
+ put(Property(), g, x, pval);
+ }
+ G g;
+ X x;
+ typename property_traits<Map>::value_type pval;
+ };
+
+ // The *IndexGraph concepts are "semantic" graph concpepts. These can be
+ // applied to describe any graph that has an index map that can be accessed
+ // using the get(*_index, g) method. For example, adjacency lists with
+ // VertexSet == vecS are implicitly models of this concept.
+ //
+ // NOTE: We could require an associated type vertex_index_type, but that
+ // would mean propagating that type name into graph_traits and all of the
+ // other graph implementations. Much easier to simply call it unsigned.
+
+ BOOST_concept(VertexIndexGraph,(Graph))
+ {
+ BOOST_CONCEPT_USAGE(VertexIndexGraph)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename property_map<Graph, vertex_index_t>::type Map;
+ typedef unsigned Index; // This could be Graph::vertex_index_type
+ Map m = get(vertex_index, g);
+ Index x = get(vertex_index, g, Vertex());
+ ignore_unused_variable_warning(x);
+
+ // This is relaxed
+ renumber_vertex_indices(g);
+
+ const_constraints(g);
+ }
+ void const_constraints(const Graph& g)
+ {
+ typedef typename property_map<Graph, vertex_index_t>::const_type Map;
+ Map m = get(vertex_index, g);
+ ignore_unused_variable_warning(m);
+ }
+ private:
+ Graph g;
+ };
+
+ BOOST_concept(EdgeIndexGraph,(Graph))
+ {
+ BOOST_CONCEPT_USAGE(EdgeIndexGraph)
+ {
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+ typedef typename property_map<Graph, edge_index_t>::type Map;
+ typedef unsigned Index; // This could be Graph::vertex_index_type
+ Map m = get(edge_index, g);
+ Index x = get(edge_index, g, Edge());
+ ignore_unused_variable_warning(x);
+
+ // This is relaxed
+ renumber_edge_indices(g);
+
+ const_constraints(g);
+ }
+ void const_constraints(const Graph& g)
+ {
+ typedef typename property_map<Graph, edge_index_t>::const_type Map;
+ Map m = get(edge_index, g);
+ ignore_unused_variable_warning(m);
+ }
+ private:
+ Graph g;
+ };
+
+ // This needs to move out of the graph library
+ BOOST_concept(Buffer,(B))
+ {
+ BOOST_CONCEPT_USAGE(Buffer) {
+ b.push(t);
+ b.pop();
+ typename B::value_type& v = b.top();
+ const_constraints(b);
+ ignore_unused_variable_warning(v);
+ }
+ void const_constraints(const B& cb) {
+ const typename B::value_type& v = cb.top();
+ n = cb.size();
+ bool e = cb.empty();
+ ignore_unused_variable_warning(v);
+ ignore_unused_variable_warning(e);
+ }
+ typename B::size_type n;
+ typename B::value_type t;
+ B b;
+ };
+
+ BOOST_concept(ColorValue,(C))
+ : EqualityComparable<C>
+ , DefaultConstructible<C>
+ {
+ BOOST_CONCEPT_USAGE(ColorValue) {
+ c = color_traits<C>::white();
+ c = color_traits<C>::gray();
+ c = color_traits<C>::black();
+ }
+ C c;
+ };
+
+ BOOST_concept(BasicMatrix,(M)(I)(V))
+ {
+ BOOST_CONCEPT_USAGE(BasicMatrix) {
+ V& elt = A[i][j];
+ const_constraints(A);
+ ignore_unused_variable_warning(elt);
+ }
+ void const_constraints(const M& cA) {
+ const V& elt = cA[i][j];
+ ignore_unused_variable_warning(elt);
+ }
+ M A;
+ I i, j;
+ };
+
+ // The following concepts describe aspects of numberic values and measure
+ // functions. We're extending the notion of numeric values to include
+ // emulation for zero and infinity.
+
+ BOOST_concept(NumericValue,(Numeric))
+ {
+ BOOST_CONCEPT_USAGE(NumericValue)
+ {
+ function_requires< DefaultConstructible<Numeric> >();
+ function_requires< CopyConstructible<Numeric> >();
+ numeric_values<Numeric>::zero();
+ numeric_values<Numeric>::infinity();
+ }
+ };
+
+ BOOST_concept(DegreeMeasure,(Measure)(Graph))
+ {
+ BOOST_CONCEPT_USAGE(DegreeMeasure)
+ {
+ typedef typename Measure::degree_type Degree;
+ typedef typename Measure::vertex_type Vertex;
+
+ Degree d = m(Vertex(), g);
+ ignore_unused_variable_warning(d);
+ }
+ private:
+ Measure m;
+ Graph g;
+ };
+
+ BOOST_concept(DistanceMeasure,(Measure)(Graph))
+ {
+ BOOST_CONCEPT_USAGE(DistanceMeasure)
+ {
+ typedef typename Measure::distance_type Distance;
+ typedef typename Measure::result_type Result;
+ Result r = m(Distance(), g);
+ ignore_unused_variable_warning(r);
+ }
+ private:
+ Measure m;
+ Graph g;
+ };
+
+} /* namespace concepts */
+
+using boost::concepts::MultiPassInputIteratorConcept;
+
+// Graph concepts
+using boost::concepts::GraphConcept;
+using boost::concepts::IncidenceGraphConcept;
+using boost::concepts::BidirectionalGraphConcept;
+using boost::concepts::AdjacencyGraphConcept;
+using boost::concepts::VertexListGraphConcept;
+using boost::concepts::EdgeListGraphConcept;
+using boost::concepts::VertexAndEdgeListGraphConcept;
+using boost::concepts::EdgeMutableGraphConcept;
+using boost::concepts::VertexMutableGraphConcept;
+using boost::concepts::MutableGraphConcept;
+using boost::concepts::MutableIncidenceGraphConcept;
+using boost::concepts::MutableBidirectionalGraphConcept;
+using boost::concepts::MutableEdgeListGraphConcept;
+using boost::concepts::VertexMutablePropertyGraphConcept;
+using boost::concepts::EdgeMutablePropertyGraphConcept;
+using boost::concepts::AdjacencyMatrixConcept;
+using boost::concepts::ReadablePropertyGraphConcept;
+using boost::concepts::PropertyGraphConcept;
+using boost::concepts::LvaluePropertyGraphConcept;
+using boost::concepts::VertexIndexGraphConcept;
+using boost::concepts::EdgeIndexGraphConcept;
+
+// Utility concepts
+using boost::concepts::BufferConcept;
+using boost::concepts::ColorValueConcept;
+using boost::concepts::BasicMatrixConcept;
+using boost::concepts::NumericValueConcept;
+using boost::concepts::DistanceMeasureConcept;
+using boost::concepts::DegreeMeasureConcept;
+
+} /* namespace boost */
#include <boost/concept/detail/concept_undef.hpp>
#endif /* BOOST_GRAPH_CONCEPTS_H */
Copied: trunk/boost/graph/numeric_values.hpp (from r51086, /sandbox/SOC/2007/graphs/boost/graph/numeric_values.hpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/boost/graph/numeric_values.hpp (original)
+++ trunk/boost/graph/numeric_values.hpp 2009-02-08 09:25:06 EST (Sun, 08 Feb 2009)
@@ -1,4 +1,4 @@
-// (C) Copyright Andrew Sutton 2007
+// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
@@ -12,63 +12,41 @@
namespace boost
{
- // This generic type reports various numeric values for
- // some type. This must be specialized for non-numeric
- // types such that the return values have the equivalent
- // semantics of zero and infinity. This classd essentially
- // builds abstractions for zero and infinity out of types
- // that don't necessarily support it.
- //
- // Specializations are provided for float and double types
- // since they actually have an infinity value.
+#define BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(type) \
+ template <> struct numeric_values<type> { \
+ typedef type value_type; \
+ static type zero() { return 0.0; } \
+ static type infinity() { return std::numeric_limits<type>::infinity(); } \
+ };
+ /**
+ * This generic type reports various numeric values for some type. In the
+ * general case, numeric values simply treat their maximum value as infinity
+ * and the default-constructed value as 0.
+ *
+ * Specializations of this template can redefine the notions of zero and
+ * infinity for various types. For example, the class is specialized for
+ * floating point types to use the built in notion of infinity.
+ */
template <typename T>
struct numeric_values
{
typedef T value_type;
- static inline T zero()
+ static T zero()
{ return T(); }
- static inline T infinity()
+ static T infinity()
{ return std::numeric_limits<T>::max(); }
};
- template <>
- struct numeric_values<float>
- {
- typedef float value_type;
-
- static inline float zero()
- { return float(0.0); }
-
- static inline float infinity()
- { return std::numeric_limits<float>::infinity(); }
- };
-
- template <>
- struct numeric_values<double>
- {
- typedef double value_type;
-
- static inline double zero()
- { return double(0.0); }
-
- static inline double infinity()
- { return std::numeric_limits<double>::infinity(); }
- };
-
- template <>
- struct numeric_values<long double>
- {
- typedef long double value_type;
-
- static inline long double zero()
- { return value_type(0.0); }
+ // Specializations for floating point types refer to 0.0 and their infinity
+ // value defined by numeric_limits.
+ BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(float);
+ BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(double);
+ BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT(long double);
- static inline long double infinity()
- { return std::numeric_limits<long double>::infinity(); }
- };
+#undef BOOST_GRAPH_SPECIALIZE_NUMERIC_VALUE
}
#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