|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-06-15 12:10:29
Author: asutton
Date: 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
New Revision: 7064
URL: http://svn.boost.org/trac/boost/changeset/7064
Log:
Added rationale and stub of a reference guide for undirected graphs.
Added a quickbook proposal for a vertex indexing suite.
Implemented vertex index management for [un]directed graphs.
Fixed all the examples to use the new property map code.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/indexing.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
sandbox/SOC/2007/graphs/libs/graph/test/index.cpp
sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp
sandbox/SOC/2007/graphs/libs/graph/test/properties.cpp
sandbox/SOC/2007/graphs/libs/graph/test/range.cpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp | 328 ++++++++++++++++++++++++++++++++-------
sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp | 323 ++++++++++++++++++++++++++++++++-------
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk | 15 +
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp | 39 ++--
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp | 20 -
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files | 4
sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp | 47 ----
sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp | 8
sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp | 48 +----
9 files changed, 592 insertions(+), 240 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -8,9 +8,12 @@
#define BOOST_GRAPH_DIRECTED_GRAPH_HPP
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/properties.hpp>
namespace boost
{
+ struct directed_graph_tag {};
+
template <
typename VertexProperty = no_property,
typename EdgeProperty = no_property,
@@ -18,73 +21,179 @@
>
class directed_graph
{
+ typedef boost::property<vertex_index_t, int, VertexProperty> vertex_property;
+
public:
typedef adjacency_list<listS,
listS,
bidirectionalS,
- VertexProperty,
+ vertex_property,
EdgeProperty,
GraphProperty,
- listS> type;
+ listS> graph_type;
private:
- type m_graph;
-
+ // 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;
+
+ typedef typename property_traits<
+ typename property_map<graph_type, vertex_index_t>::const_type
+ >::value_type
+ vertex_index_type;
public:
- typedef typename type::graph_tag graph_tag;
+ typedef directed_graph_tag graph_tag;
// types for properties and bundling
- typedef typename type::graph_property_type graph_property_type;
- typedef typename type::vertex_property_type vertex_property_type;
- typedef typename type::edge_property_type edge_property_type;
- typedef typename type::vertex_bundled vertex_bundled;
- typedef typename type::edge_bundled edge_bundled;
+ 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 type::stored_vertex stored_vertex;
- typedef typename type::vertices_size_type vertices_size_type;
- typedef typename type::edges_size_type edges_size_type;
- typedef typename type::degree_size_type degree_size_type;
- typedef typename type::vertex_descriptor vertex_descriptor;
- typedef typename type::edge_descriptor edge_descriptor;
-
- // storage selectors
- typedef typename type::vertex_list_selector vertex_list_selector;
- typedef typename type::edge_list_selector edge_list_selector;
- typedef typename type::out_edge_list_selector out_edge_list_selector;
- typedef typename type::directed_selector directed_selector;
+ 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 type::vertex_iterator vertex_iterator;
- typedef typename type::edge_iterator edge_iterator;
- typedef typename type::out_edge_iterator out_edge_iterator;
- typedef typename type::in_edge_iterator in_edge_iterator;
- typedef typename type::adjacency_iterator adjacency_iterator;
+ 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 type::directed_category directed_category;
- typedef typename type::edge_parallel_category edge_parallel_category;
- typedef typename type::traversal_category traversal_category;
+ 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;
inline directed_graph(const GraphProperty& p = GraphProperty())
: m_graph(p)
+ , m_num_vertices(0)
+ , m_num_edges(0)
+ , m_max_vertex_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)
{}
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)
{}
- inline type& impl()
+ 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;
+ }
+ return *this;
+ }
+
+ // The impl_() methods are not part of the public interface.
+ inline graph_type& impl()
{ return m_graph; }
- inline const type& impl() const
+ 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) {
+ ++m_num_edges;
+ }
+ 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);
+ }
+ }
+
+ inline void remove_edge(edge_iterator i)
+ {
+ remove_edge(*i);
+ }
+
+ inline void remove_edge(edge_descriptor e)
+ {
+ boost::remove_edge(e, m_graph);
+ --m_num_edges;
+ }
+
+ inline vertex_index_type max_vertex_index() const
+ { return m_max_vertex_index; }
+
+ inline void renumber_vertex_indices()
+ {
+ vertex_iterator i, i_end;
+ m_max_vertex_index = 0;
+ for(tie(i, i_end) = vertices(m_graph); i != i_end; ++i) {
+ put(vertex_index, m_graph, *i, m_max_vertex_index++);
+ }
+ }
+
// bundled property support
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
vertex_bundled& operator [](vertex_descriptor v)
@@ -102,7 +211,13 @@
// Graph concepts
static inline vertex_descriptor null_vertex()
- { return type::null_vertex(); }
+ { return graph_type::null_vertex(); }
+
+ private:
+ graph_type m_graph;
+ vertices_size_type m_num_vertices;
+ edges_size_type m_num_edges;
+ vertex_index_type m_max_vertex_index;
};
// IncidenceGraph concepts
@@ -176,7 +291,7 @@
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)
+ const directed_graph<VP,EP,GP>& g)
{
return adjacent_vertices(v, g.impl());
}
@@ -186,7 +301,7 @@
inline typename directed_graph<VP,EP,GP>::vertices_size_type
num_vertices(const directed_graph<VP,EP,GP>& g)
{
- return num_vertices(g.impl());
+ return g.num_vertices();
}
template <class VP, class EP, class GP>
@@ -204,7 +319,7 @@
inline typename directed_graph<VP,EP,GP>::edges_size_type
num_edges(const directed_graph<VP,EP,GP>& g)
{
- return num_edges(g.impl());
+ return g.num_edges();
}
template <class VP, class EP, class GP>
@@ -223,25 +338,24 @@
inline typename directed_graph<VP,EP,GP>::vertex_descriptor
add_vertex(directed_graph<VP,EP,GP> &g)
{
- return add_vertex(g.impl());
+ return g.add_vertex();
}
template <class VP, class EP, class GP>
inline void
- clear_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor u,
+ clear_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
directed_graph<VP,EP,GP> &g)
{
- return clear_vertex(u, g.impl());
+ return g.clear_vertex(v);
}
-
template <class VP, class EP, class GP>
inline void
- remove_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor u,
+ remove_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
directed_graph<VP,EP,GP> &g)
{
- return emove_vertex(u, g.impl());
+ return g.remove_vertex(v);
}
@@ -252,7 +366,7 @@
typename directed_graph<VP,EP,GP>::vertex_descriptor v,
directed_graph<VP,EP,GP> &g)
{
- return add_edge(u, v, g.impl());
+ return g.add_edge(u, v);
}
@@ -262,7 +376,7 @@
typename directed_graph<VP,EP,GP>::vertex_descriptor v,
directed_graph<VP,EP,GP> &g)
{
- return remove_edge(u, v, g.impl());
+ return g.remove_edge(u, v);
}
@@ -271,7 +385,7 @@
remove_edge(typename directed_graph<VP,EP,GP>::edge_descriptor e,
directed_graph<VP,EP,GP> &g)
{
- return remove_edge(e, g.impl());
+ return g.remove_edge(e);
}
@@ -280,7 +394,7 @@
remove_edge(typename directed_graph<VP,EP,GP>::edge_iterator i,
directed_graph<VP,EP,GP> &g)
{
- return remove_edge(i, g.impl());
+ return g.remove_edge(i);
}
template <class VP, class EP, class GP, class Predicate>
@@ -311,16 +425,57 @@
return remove_in_edge_if(v, pred, g.impl());
}
+
+ // Helper code for working with property maps
+ namespace detail
+ {
+ struct directed_graph_vertex_property_selector
+ {
+ template <class DirectedGraph, class Property, class Tag>
+ struct bind_
+ {
+ typedef typename DirectedGraph::graph_type Graph;
+ typedef property_map<Graph, Tag> PropertyMap;
+ typedef typename PropertyMap::type type;
+ typedef typename PropertyMap::const_type const_type;
+ };
+ };
+
+ struct directed_graph_edge_property_selector
+ {
+ template <class DirectedGraph, class Property, class Tag>
+ struct bind_
+ {
+ typedef typename DirectedGraph::graph_type Graph;
+ typedef property_map<Graph, Tag> PropertyMap;
+ typedef typename PropertyMap::type type;
+ typedef typename PropertyMap::const_type const_type;
+ };
+ };
+ }
+
+ template <>
+ struct vertex_property_selector<directed_graph_tag>
+ {
+ typedef detail::directed_graph_vertex_property_selector type;
+ };
+
+ template <>
+ struct edge_property_selector<directed_graph_tag>
+ {
+ typedef detail::directed_graph_edge_property_selector type;
+ };
+
// PropertyGraph concepts
template <class VP, class EP, class GP, typename Property>
- inline typename property_map<typename directed_graph<VP,EP,GP>::type, Property>::type
+ 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<typename directed_graph<VP,EP,GP>::type, Property>::const_type
+ 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());
@@ -328,36 +483,83 @@
template <class VP, class EP, class GP, typename Property, typename Key>
inline typename property_traits<
- typename property_map<typename directed_graph<VP,EP,GP>::type, Property>::const_type
+ 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 g.get(p, g.impl(), 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)
{
- g.put(p, g.impl(), k, v);
+ put(p, g.impl(), k, v);
}
- // MutablePropertyGraph concepts
- template <class VP, class EP, class GP, typename Property>
- inline typename directed_graph<VP,EP,GP>::vertex_descriptor
- add_vertex(const Property& vp, directed_graph<VP,EP,GP>& g)
+#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)
{
- return add_vertex(vp, g.impl());
+ 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 Property>
- 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,
- const Property& ep,
- directed_graph<VP,EP,GP> &g)
+ 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 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);
+ }
+
+ 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
+
+ template <class VP, class EP, class GP>
+ inline typename property_traits<
+ typename property_map<
+ typename directed_graph<VP,EP,GP>::graph_type, vertex_index_t
+ >::const_type
+ >::value_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>
+ inline typename property_traits<
+ typename property_map<
+ typename directed_graph<VP,EP,GP>::graph_type, vertex_index_t
+ >::const_type
+ >::value_type
+ max_vertex_index(const directed_graph<VP,EP,GP>& g)
+ {
+ return g.max_vertex_index();
+ }
+
+ template <class VP, class EP, class GP>
+ void
+ renumber_vertex_indices(directed_graph<VP,EP,GP>& g)
{
- return add_edge(u, v, ep, g.impl());
+ g.renumber_vertex_indices();
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -8,9 +8,12 @@
#define BOOST_GRAPH_UNDIRECTED_GRAPH_HPP
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/properties.hpp>
namespace boost
{
+ struct undirected_graph_tag {};
+
template <
typename VertexProperty = no_property,
typename EdgeProperty = no_property,
@@ -18,72 +21,179 @@
>
class undirected_graph
{
+ typedef boost::property<vertex_index_t, int, VertexProperty> vertex_property;
+
public:
typedef adjacency_list<listS,
listS,
undirectedS,
- VertexProperty,
+ vertex_property,
EdgeProperty,
GraphProperty,
- listS> type;
+ listS> graph_type;
private:
- type m_graph;
-
+ // 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;
+
+ typedef typename property_traits<
+ typename property_map<graph_type, vertex_index_t>::const_type
+ >::value_type
+ vertex_index_type;
public:
- typedef typename type::graph_tag graph_tag;
+ typedef undirected_graph_tag graph_tag;
// types for properties and bundling
- typedef typename type::graph_property_type graph_property_type;
- typedef typename type::vertex_property_type vertex_property_type;
- typedef typename type::edge_property_type edge_property_type;
- typedef typename type::vertex_bundled vertex_bundled;
- typedef typename type::edge_bundled edge_bundled;
+ 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 type::stored_vertex stored_vertex;
- typedef typename type::vertices_size_type vertices_size_type;
- typedef typename type::edges_size_type edges_size_type;
- typedef typename type::degree_size_type degree_size_type;
- typedef typename type::vertex_descriptor vertex_descriptor;
- typedef typename type::edge_descriptor edge_descriptor;
-
- // storage selectors
- typedef typename type::vertex_list_selector vertex_list_selector;
- typedef typename type::edge_list_selector edge_list_selector;
- typedef typename type::out_edge_list_selector out_edge_list_selector;
- typedef typename type::directed_selector directed_selector;
+ 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 type::vertex_iterator vertex_iterator;
- typedef typename type::edge_iterator edge_iterator;
- typedef typename type::out_edge_iterator out_edge_iterator;
- typedef typename type::in_edge_iterator in_edge_iterator;
- typedef typename type::adjacency_iterator adjacency_iterator;
+ 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 type::directed_category directed_category;
- typedef typename type::edge_parallel_category edge_parallel_category;
- typedef typename type::traversal_category traversal_category;
+ 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;
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(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)
{}
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)
{}
- inline type& impl()
+ inline undirected_graph& operator =(const undirected_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;
+ }
+ return *this;
+ }
+
+ // The impl_() methods are not part of the public interface.
+ inline graph_type& impl()
{ return m_graph; }
- inline const type& impl() const
+ 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) {
+ ++m_num_edges;
+ }
+ 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);
+ }
+ }
+
+ inline void remove_edge(edge_iterator i)
+ {
+ remove_edge(*i);
+ }
+
+ inline void remove_edge(edge_descriptor e)
+ {
+ boost::remove_edge(e, m_graph);
+ --m_num_edges;
+ }
+
+ inline vertex_index_type max_vertex_index() const
+ { return m_max_vertex_index; }
+
+ inline void renumber_vertex_indices()
+ {
+ vertex_iterator i, i_end;
+ m_max_vertex_index = 0;
+ for(tie(i, i_end) = vertices(m_graph); i != i_end; ++i) {
+ put(vertex_index, m_graph, *i, m_max_vertex_index++);
+ }
+ }
+
// bundled property support
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
vertex_bundled& operator [](vertex_descriptor v)
@@ -101,7 +211,13 @@
// Graph concepts
static inline vertex_descriptor null_vertex()
- { return type::null_vertex(); }
+ { return graph_type::null_vertex(); }
+
+ private:
+ graph_type m_graph;
+ vertices_size_type m_num_vertices;
+ edges_size_type m_num_edges;
+ vertex_index_type m_max_vertex_index;
};
// IncidenceGraph concepts
@@ -185,7 +301,7 @@
inline typename undirected_graph<VP,EP,GP>::vertices_size_type
num_vertices(const undirected_graph<VP,EP,GP>& g)
{
- return num_vertices(g.impl());
+ return g.num_vertices();
}
template <class VP, class EP, class GP>
@@ -203,7 +319,7 @@
inline typename undirected_graph<VP,EP,GP>::edges_size_type
num_edges(const undirected_graph<VP,EP,GP>& g)
{
- return num_edges(g.impl());
+ return g.num_edges();
}
template <class VP, class EP, class GP>
@@ -222,25 +338,24 @@
inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
add_vertex(undirected_graph<VP,EP,GP> &g)
{
- return add_vertex(g.impl());
+ return g.add_vertex();
}
template <class VP, class EP, class GP>
inline void
- clear_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
+ clear_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
undirected_graph<VP,EP,GP> &g)
{
- return clear_vertex(u, g.impl());
+ return g.clear_vertex(v);
}
-
template <class VP, class EP, class GP>
inline void
- remove_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
+ remove_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
undirected_graph<VP,EP,GP> &g)
{
- return remove_vertex(u, g.impl());
+ return g.remove_vertex(v);
}
@@ -251,7 +366,7 @@
typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
undirected_graph<VP,EP,GP> &g)
{
- return add_edge(u, v, g.impl());
+ return g.add_edge(u, v);
}
@@ -261,7 +376,7 @@
typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
undirected_graph<VP,EP,GP> &g)
{
- return remove_edge(u, v, g.impl());
+ return g.remove_edge(u, v);
}
@@ -270,7 +385,7 @@
remove_edge(typename undirected_graph<VP,EP,GP>::edge_descriptor e,
undirected_graph<VP,EP,GP> &g)
{
- return remove_edge(e, g.impl());
+ return g.remove_edge(e);
}
@@ -279,7 +394,7 @@
remove_edge(typename undirected_graph<VP,EP,GP>::edge_iterator i,
undirected_graph<VP,EP,GP> &g)
{
- return remove_edge(i, g.impl());
+ return g.remove_edge(i);
}
template <class VP, class EP, class GP, class Predicate>
@@ -310,16 +425,57 @@
return remove_in_edge_if(v, pred, g.impl());
}
+
+ // Helper code for working with property maps
+ namespace detail
+ {
+ struct undirected_graph_vertex_property_selector
+ {
+ template <class UndirectedGraph, class Property, class Tag>
+ 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;
+ };
+ };
+
+ struct undirected_graph_edge_property_selector
+ {
+ template <class UndirectedGraph, class Property, class Tag>
+ 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;
+ };
+ };
+ }
+
+ template <>
+ struct vertex_property_selector<undirected_graph_tag>
+ {
+ typedef detail::undirected_graph_vertex_property_selector type;
+ };
+
+ template <>
+ struct edge_property_selector<undirected_graph_tag>
+ {
+ typedef detail::undirected_graph_edge_property_selector type;
+ };
+
// PropertyGraph concepts
template <class VP, class EP, class GP, typename Property>
- inline typename property_map<typename undirected_graph<VP,EP,GP>::type, Property>::type
+ 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<typename undirected_graph<VP,EP,GP>::type, Property>::const_type
+ 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());
@@ -327,7 +483,7 @@
template <class VP, class EP, class GP, typename Property, typename Key>
inline typename property_traits<
- typename property_map<typename undirected_graph<VP,EP,GP>::type, Property>::const_type
+ typename property_map<typename undirected_graph<VP,EP,GP>::graph_type, Property>::const_type
>::value_type
get(Property p, const undirected_graph<VP,EP,GP> &g, const Key& k)
{
@@ -341,22 +497,69 @@
put(p, g.impl(), k, v);
}
- // MutablePropertyGraph concepts
- template <class VP, class EP, class GP, typename Property>
- inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
- add_vertex(const Property& vp, undirected_graph<VP,EP,GP>& g)
+#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)
{
- return add_vertex(vp, g.impl());
+ typedef typename property_map<undirected_graph<VP,EP,GP>, Type Bundle::*>::type
+ return_type;
+ return return_type(&g, p);
}
- template <class VP, class EP, class GP, typename Property>
- 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,
- const Property& ep,
- undirected_graph<VP,EP,GP> &g)
+ 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>
+ inline Type
+ get(Type Bundle::* 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 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);
+ }
+#endif
+
+ template <class VP, class EP, class GP>
+ inline typename property_traits<
+ typename property_map<
+ typename undirected_graph<VP,EP,GP>::graph_type, vertex_index_t
+ >::const_type
+ >::value_type
+ get_vertex_index(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ const undirected_graph<VP,EP,GP>& g)
+ {
+ return get(vertex_index, g, v);
+ }
+
+ template <class VP, class EP, class GP>
+ inline typename property_traits<
+ typename property_map<
+ typename undirected_graph<VP,EP,GP>::graph_type, vertex_index_t
+ >::const_type
+ >::value_type
+ max_vertex_index(const undirected_graph<VP,EP,GP>& g)
+ {
+ return g.max_vertex_index();
+ }
+
+ template <class VP, class EP, class GP>
+ void
+ renumber_vertex_indices(undirected_graph<VP,EP,GP>& g)
{
- return g.add_edge(u, v, g.impl(), ep);
+ g.renumber_vertex_indices();
}
}
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/indexing.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/indexing.qbk 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -0,0 +1,112 @@
+ [/
+ / Copyright (c) 2007 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)
+ /]
+
+[section Managed Vertex Indexing]
+One of the most misleading aspects of the Boost.Graph library is that in many cases
+we treat vertex descriptors as vertex indices. Many of the examples simply assume
+that descriptor is an integral type (which in most examples it is) and that the
+descriptor value magically corresponds to the index into the vector into which the
+vertex is added (which in most cases it does). Unfortunately, this is quite misleading
+and can be trivially invalidated using a core algorithm in the following manner:
+
+ vertex_descriptor u = add_vertex(g);
+ vertex_descriptor v = add_vertex(g);
+ remove_vertex(u, g);
+ breadth_first_search(g, v, make_bfs_visitor(null_visitor())); // CRASH!
+
+This will probably result in a segmentation fault because of the algorithm's use
+of exterior property maps. Specifically, this algorithm uses an externior /color/
+property declared similarly to:
+
+ vector<color> colors(num_vertices(g));
+
+Unfortunately, the only remaining vertex has index 1, which means when the algorithm
+runs this line of code:
+
+ if(colors[get(vertex_index, g, v)] == BLACK) ...
+
+Oops. That index isn't in the bounds of the array, and so this may result in a
+crashed program. Somewhat ironically, this problem is trivially solved by simple
+/renumbering/ the vertex indices before calling the algorithm.
+
+[h3 The Vertex Indexing Suite]
+Because of the near-ubiquitous approach of accessing exterior properties via
+vector indices, it seems logical that the Boost.Graph Library provide facilities
+for making this easier. This set proposed set of features addresses three common
+indexing problems:
+
+# The fact that `undirected_graph`s, `directed_graph`s, and `adjacency_list`s
+using `listS` as a vertex storage selector do not have vertex indices by
+default - which means that there are precious few algorithms these classes
+will work with out of the box. The current solution is to manually define and
+manage these property maps.
+# The easy invalidation of indices on destructive graph operations (i.e, removing
+a vertex). It should be easy to reset the indices of a graph to a continuous
+integral range after a number of remove_vertex() operations.
+# The inability to correctly identify bounds on exterior property map for
+a graph that has had vertices removed (without first renumbering the indices).
+
+The first part of the proposal requires a change to the `undirected_graph` and
+`directed_graph` class. Specifically, that they provide a default property map
+for vertex indices. This functionality can be propogated to the `adjancency_list`
+class (with `listS` vertex storage) at a later time.
+
+There are also three new graph functions in the proposed suite. These functions
+all require their graph parameters to be a model of PropertyGraph, with a
+a property map for the `vertex_index` as part of the graph itself.
+
+[table
+ [[Function] [Description]]
+ [
+ [`get_vertex_index(v, g)`]
+ [
+ This is an alias for `get(vertex_index, g, v)` and provided for
+ convenience rather than added functionality.
+ ]
+ [`max_vertex_index(g)`]
+ [
+ This returns the total number of indices allocated for the vertices
+ of the graph /g/. The last vertex added to a graph will always have
+ the index `max_vertex_index(g) - 1`. The return type for this function
+ is the value type of the `vertex_index` property map, which is
+ typically an integer type.
+ ]
+ [`renumber_vertex_indices(g)`]
+ [
+ Renumber the indices in the vertex index map of /g/ such that the
+ index of each vertex is in the range \[0, num_vertices(g)). Also,
+ after calling this function, max_vertex_index(g) == num_vertices(g).
+ ]
+ ]
+]
+
+Implementing these three functions will allow more flexible algorithms for
+mutable graphs. Specifically, this model relaxes many of the constraints that
+vertices have indices in the range \[0, num_vertices(g)). Instead, algorithms
+can require indices in the range \[0, max_vertex_index(g)).
+
+As a downside, this relaxed constraint will result in over-sized vectors whose
+items may not correspond to vertices within the graph. However, if the algorithms
+employ vectors as exterior properties, there is probably a good chance that the
+difference in vector size and capacity will subsume space required by
+overallocating for missing vertices. Furthermore, correct use of the
+`get_vertex_index(v,g)` function will promote more correct accessing of
+said vectors. Since all valid vertex descriptors have valid and correct
+indices, there is no possibility of accessing an element in an exterior
+property that does not correspond to a valid vertex. As an added bonus,
+the explicit name should improve readability significantly and discourage
+new (and experienced?) developers from doing this:
+
+ vertex_descriptor v = add_vertex(g);
+ colors[v] = ...
+
+which, for non-trivial programs is in fact, incorrect.
+
+This proposal is implemented in this form for the `undirected_graph` and
+`directed_graph classes. Comments are welcome.
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -43,7 +43,9 @@
property<vertex_index_t, int, VertexProperties>
-Works great.
+Works great except in the case of the MutablePropertyGraph functions. Basically,
+I have no idea how to specify the value of a vertex property in this form. It's
+kind of weird...
[h4 Automatic Indexing and Re-indexing]
If the `undirected_graph` and `directed_graph` classes have implicit index
@@ -95,4 +97,15 @@
we automatically renumber vertices on the next vertex removal (or something
like that).
+[h4 Removing Edges]
+There is no great documentation for the actual behavior of the `remove_edge(u, v, g)`
+function. For example, in the `adjacency_list` reference page, it simply states that
+it removes "the" edge connecting the vertices /u/ and /v/. What if there are multiple
+edges connecting the two vertices? Does this remove all of them or some selection
+thereof.
+
+The correct answer, I think, is that it should remove all such edges. If a programmer
+needs finer-grained control he or she can easily use the remove_edge(e, g) function
+where /e/ is an edge descriptor.
+
[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -0,0 +1,48 @@
+ [/
+ / Copyright (c) 2007 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)
+ /]
+
+[section Undirected Graph Reference]
+
+*TODO*: I should probably document somewhere that out_edges() and in_edges()
+are equivalent for this function. Is it important? I don't know, maybe.
+
+[h3 Members]
+The following tables define and describe the members of the `undirected_graph`
+class.
+
+[h4 Associated Types]
+
+[table
+ [[Member] [Where Defined] [Description]]
+ [
+ [`vertex_descriptor`]
+ [Graph]
+ [An opaque type whose values are used to access vertices and their properties.]
+ ]
+ [
+ [`edge_descriptor`]
+ [Graph]
+ [An opaque type whose values are used to access edges and their properties.]
+ ]
+ [
+ [`directed_category`]
+ [Graph]
+ [Indicates the graph has undirected edges. It's type is `undirected_tag`.]
+ ]
+ [
+ [`edge_parallel_category`]
+ [Graph]
+ [...]
+ ]
+ [
+ [`traversal_category`]
+ [Graph]
+ [...]
+ ]
+]
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -6,6 +6,7 @@
// std includes
#include <iostream>
+#include <iomanip>
#include <string>
#include <map>
@@ -20,15 +21,14 @@
struct Target
{
- int index;
string name;
};
typedef directed_graph<Target> Graph;
typedef Graph::vertex_descriptor Vertex;
typedef Graph::edge_descriptor Edge;
-typedef property_map<Graph::type, int Target::*>::type TargetIndexMap;
-typedef property_map<Graph::type, string Target::*>::type TargetNameMap;
+
+typedef property_map<Graph, string Target::*>::type TargetNameMap;
typedef map<string, Vertex> TargetMap;
@@ -48,7 +48,6 @@
it->second = v;
// configure the vertex properties
- g[v].index = num_vertices(g) - 1;
g[v].name = name;
}
else {
@@ -117,29 +116,33 @@
}
}
- // we need to create a vertex index map for the graph before
- // we can generate the build order
- TargetIndexMap indices = get(&Target::index, g);
// the build order is just a
BuildOrder order;
- topological_sort(g, front_inserter(order),
- // named parameters
- vertex_index_map(indices)
- );
+ topological_sort(g, front_inserter(order));
// write out the build order and compute time slots at the
// same time...
vector<int> time(num_vertices(g), 0);
- BuildOrder::iterator i = order.begin(), j = order.end();
- for( ; i != j; ++i) {
+ BuildOrder::iterator i = order.begin(), i_end = order.end();
+ for( ; i != i_end; ++i) {
int slot = -1;
- Graph::in_edge_iterator j, k;
- for(tie(j, k) = in_edges(*i, g); j != k; ++j) {
- slot = std::max(time[g[source(*j, g)].index], slot);
+ Graph::in_edge_iterator j, j_end;
+ for(tie(j, j_end) = in_edges(*i, g); j != j_end; ++j) {
+ Vertex v = source(*j, g);
+ int x = get(vertex_index, g, v);
+
+ // find the maximum time slot
+ slot = std::max(time[x], slot);
}
- time[g[*i].index] = slot + 1;
- cout << g[*i].name << " [" << time[g[*i].index] << "]\n";
+ // store the max depth
+ int x = get(vertex_index, g, *i);
+ time[x] = slot + 1;
+
+ // and print some stuff to the screen
+ cout << setw(25) << g[*i].name << " [" << time[x] << "]\n";
}
+
+ return 0;
}
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -20,15 +20,14 @@
struct Target
{
- int index;
string name;
};
typedef directed_graph<Target> Graph;
typedef Graph::vertex_descriptor Vertex;
typedef Graph::edge_descriptor Edge;
-typedef property_map<Graph::type, int Target::*>::type TargetIndexMap;
-typedef property_map<Graph::type, string Target::*>::type TargetNameMap;
+
+typedef property_map<Graph, string Target::*>::type TargetNameMap;
typedef map<string, Vertex> TargetMap;
@@ -63,12 +62,7 @@
if(inserted) {
// create a vertex for the name
v = add_vertex(g);
-
- // associate the vertex with the name
it->second = v;
-
- // configure the vertex properties
- g[v].index = num_vertices(g) - 1;
g[v].name = name;
}
else {
@@ -137,13 +131,9 @@
}
}
- // we need to create a vertex index map for the graph before
- // we can generate the build order
- TargetIndexMap indices = get(&Target::index, g);
-
bool cycle = false;
- depth_first_search(g,
- vertex_index_map(indices).
- visitor(detect_cycles(cycle)));
+ depth_first_search(g, visitor(detect_cycles(cycle)));
cout << "has cycle: " << cycle << "\n";
+
+ return 0;
}
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -14,5 +14,5 @@
build_order.cpp : directed_graph.hpp topological_sort.hpp
build_order.exe : build_order.cpp
-movies.cpp : kevin_bacon.cpp
-kevin_bacon.cpp : movies.cpp
\ No newline at end of file
+# movies.cpp : kevin_bacon.cpp
+# kevin_bacon.cpp : movies.cpp
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -17,44 +17,6 @@
using namespace std;
using namespace boost;
-// This visitor is responsible for recording (setting) the bacon numbers
-// of actors in the movie graph.
-template <typename DistanceMap>
-struct ActorDistanceRecorder : public bfs_visitor<>
-{
- ActorDistanceRecorder(DistanceMap d)
- : distances(d)
- {}
-
- // The tree_edge() method is invoked when a vertex v is discovered
- // while exploring an edge (u,v). With respect to a BFS, this means
- // that v is in the next higher level (or depth) than u. Therefore,
- // the Kevin Bacon number of v should be one more than that of u.
- template <typename Edge, typename Graph>
- void tree_edge(Edge e, const Graph& g) const
- {
- typedef typename Graph::vertex_descriptor Vertex;
-
- // get the source and target vertices of this tree edge.
- Vertex
- u = source(e, g),
- v = target(e, g);
-
- // set the bacon number to 1 + u's bacon number
- distances[v] = distances[u] + 1;
- }
-
- DistanceMap distances;
-};
-
-// This is just a convenience function so we can call a function rather than
-// explicitly instantiate the visitor type. It makes it more "action-oriented".
-template <typename DistanceMap>
-ActorDistanceRecorder<DistanceMap> record_actor_distances(DistanceMap d)
-{
- return ActorDistanceRecorder<DistanceMap>(d);
-}
-
int
main(int argc, char *argv[])
{
@@ -77,7 +39,14 @@
// run a breadth-first search on the graph and record
// the kevin bacon numbers for each actor
- breadth_first_search(g, kevin, visitor(record_actor_distances(dists)));
+ breadth_first_search(
+ g, kevin,
+ visitor(
+ make_bfs_visitor(
+ record_distances(dists, on_tree_edge())
+ )
+ )
+ );
// just run over the vertices and print the back numbers
Graph::vertex_iterator i, j;
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/movies.hpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -51,11 +51,11 @@
// These property maps index information in the Actor and Movie
// structures, respectively. They are used to access specific pieces
// of information inside the graph.
-typedef boost::property_map<Graph::graph_type, int Actor::*>::type ActorDistanceMap;
-typedef boost::property_map<Graph::graph_type, Vertex Actor::*>::type ActorParentMap;
-typedef boost::property_map<Graph::graph_type, std::string Actor::*>::type ActorNameMap;
+typedef boost::property_map<Graph, int Actor::*>::type ActorDistanceMap;
+typedef boost::property_map<Graph, Vertex Actor::*>::type ActorParentMap;
+typedef boost::property_map<Graph, std::string Actor::*>::type ActorNameMap;
-typedef boost::property_map<Graph::graph_type, std::string Movie::*>::type MovieNameMap;
+typedef boost::property_map<Graph, std::string Movie::*>::type MovieNameMap;
// we use an extra map to help dynamically populate the graph.
// this maps actor names to the vertices that they're inserted as
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -18,40 +18,6 @@
using namespace std;
using namespace boost;
-template <typename ParentMap>
-struct ActorParentRecorder : public bfs_visitor<>
-{
- ActorParentRecorder(ParentMap d)
- : parents(d)
- {}
-
- // record the parent
- template <typename Edge, typename Graph>
- void tree_edge(Edge e, const Graph& g) const
- {
- typedef typename Graph::vertex_descriptor Vertex;
-
- Vertex
- u = source(e, g),
- v = target(e, g);
-
- // the parent of v is u
- parents[v] = u;
- }
-
- ParentMap parents;
-};
-
-// This is just a convenience function so we can call a function rather than
-// explicitly instantiate the visitor type. It makes it more "action-oriented".
-template <typename ParentMap>
-ActorParentRecorder<ParentMap> record_actor_parents(ParentMap d)
-{
- return ActorParentRecorder<ParentMap>(d);
-}
-
-
-
int
main(int argc, char *argv[])
{
@@ -90,12 +56,18 @@
return -1;
}
- // The predeceessor map records, for the vertex at each index, the
- // predecessor (or parent) in the shortest-path tree. By iterating
- // from predecessor to predecessor, we can find the shortest path
+ // get the parents map so we can record them
+ // during a breadth first search
ActorParentMap parents = get(&Actor::parent, g);
- breadth_first_search(g, u, visitor(record_actor_parents(parents)));
+ breadth_first_search(
+ g, u,
+ visitor(
+ make_bfs_visitor(
+ record_predecessors(parents, on_tree_edge())
+ )
+ )
+ );
// print the movies in which the actors appear by iterating over
// the elements in the predecessor map
Added: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -0,0 +1,20 @@
+
+exe properties
+ : properties.cpp
+ : <include>../../../
+ ;
+
+exe mutable
+ : mutable.cpp
+ : <include>../../../
+ ;
+
+exe index
+ : index.cpp
+ : <include>../../../
+ ;
+
+exe range
+ : range.cpp
+ : <include>../../../
+ ;
Added: sandbox/SOC/2007/graphs/libs/graph/test/index.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/index.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -0,0 +1,62 @@
+
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/undirected_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+typedef undirected_graph<> Graph;
+typedef Graph::vertex_descriptor Vertex;
+typedef property_map<Graph, vertex_index_t>::type IndexMap;
+
+int test_main(int, char*[])
+{
+ Graph g;
+ Vertex v[5];
+
+ IndexMap x = get(vertex_index, g);
+
+ // build up the graph
+ for(int i = 0; i < 5; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // after the first build, we should have these conditions
+ BOOST_CHECK(max_vertex_index(g) == 5);
+ for(int i = 0; i < 5; ++i) {
+ BOOST_CHECK(get_vertex_index(v[i], g) == i);
+ }
+
+ // remove some vertices and re-add them...
+ for(int i = 0; i < 5; ++i) remove_vertex(v[i], g);
+ BOOST_CHECK(num_vertices(g) == 0);
+
+ for(int i = 0; i < 5; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // before renumbering, our vertices should be off by
+ // about 5...
+ BOOST_CHECK(max_vertex_index(g) == 10);
+ for(int i = 0; i < 5; ++i) {
+ BOOST_CHECK(get_vertex_index(v[i], g) == 5 + i);
+ }
+
+ // renumber them.
+ renumber_vertex_indices(g);
+
+ // and we should be back to the initial condition
+ BOOST_CHECK(max_vertex_index(g) == 5);
+ for(int i = 0; i < 5; ++i) {
+ BOOST_CHECK(get_vertex_index(v[i], g) == i);
+ }
+
+ return 0;
+}
Added: sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -0,0 +1,82 @@
+
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+
+#include <boost/test/minimal.hpp>
+#include <boost/graph/undirected_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+struct Foo
+{
+ int foo;
+};
+
+typedef undirected_graph<Foo> Graph;
+typedef Graph::vertex_descriptor Vertex;
+typedef Graph::edge_descriptor Edge;
+
+typedef adjacency_list<listS, listS, undirectedS> Test;
+
+int test_main(int, char*[])
+{
+ Graph g;
+ Vertex v[5];
+ Edge e[5];
+
+ // simple starting conditions...
+ BOOST_CHECK(num_vertices(g) == 0);
+ BOOST_CHECK(num_edges(g) == 0);
+
+ // build a couple verts and remove them
+ v[0] = add_vertex(g);
+ v[1] = add_vertex(g);
+ BOOST_CHECK(num_vertices(g) == 2);
+
+ remove_vertex(v[0], g);
+ BOOST_CHECK(num_vertices(g) == 1);
+
+ remove_vertex(v[1], g);
+ BOOST_CHECK(num_vertices(g) == 0);
+
+ // rebuild the graph, but add some edges this time
+ for(int i = 0; i < 5; ++i) v[i] = add_vertex(g);
+
+ e[0] = add_edge(v[0], v[1], g).first;
+ e[1] = add_edge(v[1], v[2], g).first;
+ e[2] = add_edge(v[2], v[3], g).first;
+ BOOST_CHECK(num_edges(g) == 3);
+ BOOST_CHECK(*edges(g).first == e[0]);
+
+ remove_edge(v[0], v[1], g); // removes e[0]
+ BOOST_CHECK(num_edges(g) == 2);
+ BOOST_CHECK(*edges(g).first == e[1]);
+
+ remove_edge(e[1], g); // removes e[1]
+ BOOST_CHECK(num_edges(g) == 1);
+ BOOST_CHECK(*edges(g).first == e[2]);
+
+ remove_edge(edges(g).first, g); // remove e[2]
+ BOOST_CHECK(num_edges(g) == 0);
+
+
+ // build a bunch of edges between two verts
+ for(int i = 0; i < 3; ++i) e[i] = add_edge(v[0], v[1], g).first;
+ BOOST_CHECK(num_edges(g) == 3);
+
+ remove_edge(v[0], v[1], g);
+ BOOST_CHECK(num_edges(g) == 0);
+
+ Test f;
+ v[0] = add_vertex(f);
+ v[1] = add_vertex(f);
+ add_edge(v[0], v[1], f);
+
+ return 0;
+}
Added: sandbox/SOC/2007/graphs/libs/graph/test/properties.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/properties.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -0,0 +1,46 @@
+
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <boost/graph/undirected_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+struct Foo
+{
+ int foo;
+};
+
+typedef undirected_graph<Foo> Graph;
+typedef Graph::vertex_descriptor Vertex;
+
+typedef property_map<Graph, vertex_index_t>::type IndexMap;
+typedef property_map<Graph, int Foo::*>::type FooMap;
+
+int main()
+{
+ Graph g;
+
+ Vertex u = add_vertex(g);
+ Vertex v = add_vertex(g);
+
+ IndexMap indices = get(vertex_index, g);
+ FooMap foos = get(&Foo::foo, g);
+
+ g[u].foo = 3;
+ g[v].foo = 5;
+
+ cout << indices[u] << " " << foos[u] << "\n";
+ cout << indices[v] << " " << foos[v] << "\n";
+
+ cout << "test: " << get(&Foo::foo, g, v) << "\n";
+ put(&Foo::foo, g, v, 12);
+ cout << "test: " << g[v].foo << "\n";
+
+ return 0;
+}
Added: sandbox/SOC/2007/graphs/libs/graph/test/range.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/range.cpp 2007-06-15 12:10:24 EDT (Fri, 15 Jun 2007)
@@ -0,0 +1,87 @@
+
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/breadth_first_search.hpp>
+
+using namespace std;
+using namespace boost;
+
+typedef undirected_graph<> Graph;
+typedef Graph::vertex_descriptor Vertex;
+
+static const int N = 5;
+
+void build_n_clique(Graph& g, int n)
+{
+ // build and tear down an N-clique
+ for(int i = 0; i < N; ++i) {
+ add_vertex(g);
+ }
+ Graph::vertex_iterator i, j, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ for(j = next(i); j != end; ++j) {
+ add_edge(*i, *j, g);
+ }
+ }
+}
+
+void clear(Graph& g)
+{
+ // apparently, the only way to safely clear the list of vertices
+ // is to use a trailing iterator type of trick. it's not pretty,
+ // but it works.
+ Graph::vertex_iterator i, j, end;
+ tie(i, end) = vertices(g);
+ for(j = i; i != end; i = j) {
+ ++j;
+ clear_vertex(*i, g);
+ remove_vertex(*i, g);
+ }
+}
+
+int test_main(int, char *argv[])
+{
+ Graph g;
+
+ build_n_clique(g, N);
+ clear(g);
+ build_n_clique(g, N);
+
+ cout << num_vertices(g) << "/" << num_edges(g) << "\n";
+ cout << max_vertex_index(g) << "\n";
+
+ // renumber_vertex_indices(g);
+ //
+ // WARNING: This will crash without the previous line of code.
+ // Why? Deep in the guts of the BFS that gets called below,
+ // the algorithm allocates a N-vector of colors that they plan
+ // to access via vertex indices. The only problem is that the
+ // vertex indices should now be in the range [N, 2*N), well
+ // beyond the bounds of the vectors used in the queue.
+ //
+ // Obviously uncommenting the previous line of code will work
+ // just fine, but a better approach might be to change the
+ // algorithm to create a vector of size [0, max_vertex_index).
+ // Despite the fact that there may gaps in the vector, correct
+ // usage of indices will mean that you never actually access
+ // non-vertex elements in your exterior property vectors.
+
+ breadth_first_search(
+ g, *vertices(g).first,
+ visitor(
+ make_bfs_visitor(null_visitor())
+ )
+ );
+
+
+ return 0;
+}
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