|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-06-25 13:33:41
Author: asutton
Date: 2007-06-25 13:33:40 EDT (Mon, 25 Jun 2007)
New Revision: 7141
URL: http://svn.boost.org/trac/boost/changeset/7141
Log:
Fixed a compiler error in [un]directed graphs.
Implemented semi-automated vertex management for new graphs.
Updated examples with new type stuff.
Removed:
sandbox/SOC/2007/graphs/boost/graph/graph_as_matrix.hpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp | 673 +++++++++++++++++++++-----------------
sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp | 693 ++++++++++++++++++++++-----------------
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp | 2
sandbox/SOC/2007/graphs/libs/graph/examples/movies/kevin_bacon.cpp | 14
sandbox/SOC/2007/graphs/libs/graph/examples/movies/six_degrees.cpp | 76 ++--
5 files changed, 798 insertions(+), 660 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-25 13:33:40 EDT (Mon, 25 Jun 2007)
@@ -7,6 +7,7 @@
#ifndef BOOST_GRAPH_DIRECTED_GRAPH_HPP
#define BOOST_GRAPH_DIRECTED_GRAPH_HPP
+#include <boost/utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
@@ -15,273 +16,295 @@
struct directed_graph_tag {};
template <
- typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property
- >
+ typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
+ typename GraphProperty = no_property
+ >
class directed_graph
{
- typedef boost::property<vertex_index_t, int, VertexProperty> vertex_property;
-
- public:
- typedef adjacency_list<listS,
- listS,
- bidirectionalS,
- vertex_property,
- EdgeProperty,
- 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;
-
- typedef typename property_traits<
- typename property_map<graph_type, vertex_index_t>::const_type
- >::value_type
- vertex_index_type;
- 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;
-
- 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 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 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)
- { return m_graph[v]; }
+ typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;
- const vertex_bundled& operator [](vertex_descriptor v) const
- { return m_graph[v]; }
+ public:
+ typedef adjacency_list<listS,
+ listS,
+ bidirectionalS,
+ vertex_property,
+ EdgeProperty,
+ GraphProperty,
+ listS> graph_type;
- edge_bundled& operator [](edge_descriptor e)
- { return m_graph[e]; }
+ 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;
- const edge_bundled& operator [](edge_descriptor e) const
- { return m_graph[e]; }
-#endif
+ public:
+ typedef directed_graph_tag graph_tag;
- // Graph concepts
- static inline vertex_descriptor null_vertex()
- { return graph_type::null_vertex(); }
+ // 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;
+
+ 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 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 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;
+ tie(i, i_end) = vertices(m_graph);
+ m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
+ }
+
+ inline void remove_vertex_and_renumber_indices(vertex_iterator i)
+ {
+ vertex_iterator j = next(i), j_end = vertices(m_graph).second;
+ vertex_index_type n = get(vertex_index, m_graph, *i);
+
+ // remove the offending vertex and renumber everything after
+ remove_vertex(*i);
+ m_max_vertex_index = renumber_vertex_indices(j, 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(); }
private:
- graph_type m_graph;
- vertices_size_type m_num_vertices;
- edges_size_type m_num_edges;
- vertex_index_type m_max_vertex_index;
+ inline vertices_size_type
+ renumber_vertex_indices(vertex_iterator i,
+ vertex_iterator i_end,
+ vertices_size_type n)
+ {
+ typename property_map<graph_type, vertex_index_t>::type
+ indices = get(vertex_index, m_graph);
+ for( ; i != i_end; ++i) {
+ indices[*i] = n++;
+ }
+ return n;
+ }
+
+ 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
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)
+ const directed_graph<VP,EP,GP> &g)
{
- return source(e, g.impl());
+ 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)
+ const directed_graph<VP,EP,GP> &g)
{
- return target(e, g.impl());
+ return target(e, g.impl());
}
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)
+ const directed_graph<VP,EP,GP> &g)
{
- return out_degree(v, g.impl());
+ return out_degree(v, 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
- >
+ 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)
+ const directed_graph<VP,EP,GP> &g)
{
- return out_edges(v, g.impl());
+ return out_edges(v, g.impl());
}
// BidirectionalGraph concepts
template <class VP, class EP, class GP>
inline typename directed_graph<VP,EP,GP>::degree_size_type
in_degree(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
+ const directed_graph<VP,EP,GP> &g)
{
- return in_degree(v, g.impl());
+ return in_degree(v, g.impl());
}
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
- >
+ 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)
+ const directed_graph<VP,EP,GP> &g)
{
- return in_edges(v, g.impl());
+ return in_edges(v, g.impl());
}
+
template <class VP, class EP, class GP>
inline typename directed_graph<VP,EP,GP>::degree_size_type
degree(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP> &g)
+ const directed_graph<VP,EP,GP> &g)
{
- return degree(v, g.impl());
+ return degree(v, g.impl());
}
// AdjacencyGraph concepts
@@ -291,27 +314,44 @@
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());
}
+ 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());
+ }
+
// 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();
+ return g.num_vertices();
}
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
- >
+ 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());
+ return vertices(g.impl());
}
// EdgeListGraph concepts
@@ -319,17 +359,17 @@
inline typename directed_graph<VP,EP,GP>::edges_size_type
num_edges(const directed_graph<VP,EP,GP>& g)
{
- return g.num_edges();
+ 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
- >
+ 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());
+ return edges(g.impl());
}
@@ -338,24 +378,24 @@
inline typename directed_graph<VP,EP,GP>::vertex_descriptor
add_vertex(directed_graph<VP,EP,GP> &g)
{
- return g.add_vertex();
+ return g.add_vertex();
}
template <class VP, class EP, class GP>
inline void
clear_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- directed_graph<VP,EP,GP> &g)
+ directed_graph<VP,EP,GP> &g)
{
- return g.clear_vertex(v);
+ return g.clear_vertex(v);
}
template <class VP, class EP, class GP>
inline void
remove_vertex(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- directed_graph<VP,EP,GP> &g)
+ directed_graph<VP,EP,GP> &g)
{
- return g.remove_vertex(v);
+ return g.remove_vertex(v);
}
@@ -363,107 +403,106 @@
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)
+ typename directed_graph<VP,EP,GP>::vertex_descriptor v,
+ directed_graph<VP,EP,GP> &g)
{
- return g.add_edge(u, v);
+ return g.add_edge(u, v);
}
template <class VP, class EP, class GP>
inline void
remove_edge(typename directed_graph<VP,EP,GP>::vertex_descriptor u,
- typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- directed_graph<VP,EP,GP> &g)
+ typename directed_graph<VP,EP,GP>::vertex_descriptor v,
+ directed_graph<VP,EP,GP> &g)
{
- return g.remove_edge(u, v);
+ return g.remove_edge(u, v);
}
template <class VP, class EP, class GP>
inline void
remove_edge(typename directed_graph<VP,EP,GP>::edge_descriptor e,
- directed_graph<VP,EP,GP> &g)
+ directed_graph<VP,EP,GP> &g)
{
- return g.remove_edge(e);
+ return g.remove_edge(e);
}
template <class VP, class EP, class GP>
inline void
remove_edge(typename directed_graph<VP,EP,GP>::edge_iterator i,
- directed_graph<VP,EP,GP> &g)
+ directed_graph<VP,EP,GP> &g)
{
- return g.remove_edge(i);
+ 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)
+ directed_graph<VP,EP,GP> &g)
{
- return remove_edge_if(pred, g.impl());
+ return remove_edge_if(pred, g.impl());
}
template <class VP, class EP, class GP, class Predicate>
inline void
remove_out_edge_if(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- Predicate pred,
- directed_graph<VP,EP,GP> &g)
+ Predicate pred,
+ directed_graph<VP,EP,GP> &g)
{
- return remove_out_edge_if(v, pred, g.impl());
+ 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)
+ Predicate pred,
+ directed_graph<VP,EP,GP> &g)
{
- return remove_in_edge_if(v, pred, g.impl());
+ 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;
- };
- };
+ 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;
+ typedef detail::directed_graph_vertex_property_selector type;
};
template <>
struct edge_property_selector<directed_graph_tag>
{
- typedef detail::directed_graph_edge_property_selector type;
+ typedef detail::directed_graph_edge_property_selector type;
};
// PropertyGraph concepts
@@ -471,30 +510,51 @@
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());
+ 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());
+ return get(p, 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
+ 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);
+ return get(p, g.impl(), k);
}
template <class VP, class EP, class GP, typename Property, typename Key, typename Value>
inline void
put(Property p, directed_graph<VP,EP,GP> &g, const Key& k, const Value& v)
{
- put(p, g.impl(), k, v);
+ put(p, g.impl(), k, v);
+ }
+
+ template <class VP, class EP, class GP, class Property>
+ typename graph_property<directed_graph<VP,EP,GP>, Property>::type&
+ get_property(directed_graph<VP,EP,GP>& g, Property p)
+ {
+ return get_property(g.impl(), p);
+ }
+
+ 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, class Property, class Value>
+ void
+ set_property(directed_graph<VP,EP,GP>& g, Property p, Value v)
+ {
+ return set_property(g.impl(), p, v);
}
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
@@ -502,64 +562,67 @@
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);
+ typedef typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::type
+ return_type;
+ return return_type(&g, p);
}
template <class VP, class EP, class GP, typename Type, typename Bundle>
inline typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::const_type
get(Type Bundle::* p, const directed_graph<VP,EP,GP>& g)
{
- typedef typename property_map<directed_graph<VP,EP,GP>, Type Bundle::*>::const_type
- return_type;
- return return_type(&g, p);
+ typedef typename property_map<directed_graph<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);
+ 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);
+ // 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
+ 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)
+ const directed_graph<VP,EP,GP>& g)
{
- return get(vertex_index, g, v);
+ 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
+ typename directed_graph<VP,EP,GP>::vertex_index_type
max_vertex_index(const directed_graph<VP,EP,GP>& g)
{
- return g.max_vertex_index();
+ return g.max_vertex_index();
}
template <class VP, class EP, class GP>
void
- renumber_vertex_indices(directed_graph<VP,EP,GP>& g)
+ renumber_vertex_indices(
+ typename directed_graph<VP,EP,GP>::vertex_iterator i,
+ directed_graph<VP,EP,GP>& g)
+ {
+ g.renumber_vertex_indices(i);
+ }
+
+ 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.renumber_vertex_indices();
+ g.remove_vertex_and_renumber_indices(i);
}
}
Deleted: sandbox/SOC/2007/graphs/boost/graph/graph_as_matrix.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/graph_as_matrix.hpp 2007-06-25 13:33:40 EDT (Mon, 25 Jun 2007)
+++ (empty file)
@@ -1,145 +0,0 @@
-// (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)
-
-#ifndef BOOST_GRPAPH_GRAPH_AS_MATRIX_HPP
-#define BOOST_GRPAPH_GRAPH_AS_MATRIX_HPP
-
-#include <utility>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-
-namespace boost
-{
- // NOTE:
- // The adjacency list must be a model of an incidence graph since it needs
- // out_edge_iterator and out_edges().
- //
- // NOTE:
- // This are _not_ constant time operations, but it is optimized (sort of) for
- // the type of graph. If directed, there isn't much choice in search algorithm.
- // Specifically, this will run in O(out_degree(u)). For bidirectional graphs,
- // we can optimize somewhat and search either the out edges of u or the in
- // edges of v for the requested edge. This will run in O(min{out_degree(u), in_degree(v)}).
- // A clever trick... Likewise, for undirected graphs, we can search either
- // the out edges of u or v so it runs in O(min{out_degree(u), out_degree(v)}).
-
- template <typename OEL, typename VL, typename VP,
- typename EP, typename GP, typename EL>
- std::pair<
- typename adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>::edge_descriptor,
- bool
- >
- edge(typename adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>::vertex_descriptor u,
- typename adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>::vertex_descriptor v,
- const adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>& g)
- {
- typedef adjacency_list<OEL,VL,directedS,VP,EP,GP,EL> Graph;
-
- bool found = false;
- typename Graph::edge_descriptor edge;
-
- // iterate over the out_edges of u, looking for v
- typename Graph::out_edge_iterator i, j;
- for(tie(i, j) = out_edges(u, g); i != j; ++i) {
- if(target(*i, g) == v) {
- edge = *i;
- found = true;
- break;
- }
- }
- return std::make_pair(edge, found);
- }
-
- template <typename OEL, typename VL, typename VP,
- typename EP, typename GP, typename EL>
- std::pair<
- typename adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>::edge_descriptor,
- bool
- >
- edge(typename adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>::vertex_descriptor u,
- typename adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>::vertex_descriptor v,
- const adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>& g)
- {
- typedef adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL> Graph;
-
- bool found = false;
- typename Graph::edge_descriptor edge;
-
- // iterate over either the out_edges or in_edges depending on the minimum
- // degreer (this should save some time if done repeatedly).
- if(out_degree(u, g) < in_degree(v, g)) {
- typename Graph::out_edge_iterator i, j;
- for(tie(i, j) = out_edges(u, g); i != j; ++i) {
- if(target(*i, g) == v) {
- edge = *i;
- found = true;
- break;
- }
- }
- }
- else {
- typename Graph::in_edge_iterator i, j;
- for(tie(i, j) = in_edges(v, g); i != j; ++i) {
- if(target(*i, g) == v) {
- edge = *i;
- found = true;
- break;
- }
- }
- }
- return std::make_pair(edge, found);
- }
-
- template <typename OEL, typename VL, typename VP,
- typename EP, typename GP, typename EL>
- std::pair<
- typename adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>::edge_descriptor,
- bool
- >
- edge(typename adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>::vertex_descriptor u,
- typename adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>::vertex_descriptor v,
- const adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>& g)
- {
- typedef adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL> Graph;
-
- bool found = false;
- typename Graph::edge_descriptor edge;
-
- typename Graph::vertex_descriptor p = out_degree(u, g) < out_degree(v, g) ? u : v;
-
- // iterate over the out_edges of u, looking for v
- typename Graph::out_edge_iterator i, j;
- for(tie(i, j) = out_edges(p, g); i != j; ++i) {
- if(target(*i, g) == v) {
- edge = *i;
- found = true;
- break;
- }
- }
- return std::make_pair(edge, found);
- }
-
- template <typename VP, typename EP, typename GP>
- std::pair<typename undirected_graph<VP,EP,GP>::edge_descriptor, bool>
- edge(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
- typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
- {
- return edge(u, v, g.impl());
- }
-
- template <typename VP, typename EP, typename 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());
- }
-}
-
-#endif
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-25 13:33:40 EDT (Mon, 25 Jun 2007)
@@ -7,6 +7,7 @@
#ifndef BOOST_GRAPH_UNDIRECTED_GRAPH_HPP
#define BOOST_GRAPH_UNDIRECTED_GRAPH_HPP
+#include <boost/utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
@@ -15,273 +16,306 @@
struct undirected_graph_tag {};
template <
- typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property
- >
+ typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
+ typename GraphProperty = no_property
+ >
class undirected_graph
{
- typedef boost::property<vertex_index_t, int, VertexProperty> vertex_property;
-
- public:
- typedef adjacency_list<listS,
- listS,
- undirectedS,
- vertex_property,
- EdgeProperty,
- 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;
-
- typedef typename property_traits<
- typename property_map<graph_type, vertex_index_t>::const_type
- >::value_type
- vertex_index_type;
- public:
- typedef undirected_graph_tag graph_tag;
-
- // types for properties and bundling
- typedef typename graph_type::graph_property_type graph_property_type;
- typedef typename graph_type::vertex_property_type vertex_property_type;
- typedef typename graph_type::edge_property_type edge_property_type;
- typedef typename graph_type::vertex_bundled vertex_bundled;
- typedef typename graph_type::edge_bundled edge_bundled;
-
- // more commonly used graph types
- typedef typename graph_type::stored_vertex stored_vertex;
- 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;
-
- 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 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 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)
- { return m_graph[v]; }
+ typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;
- const vertex_bundled& operator [](vertex_descriptor v) const
- { return m_graph[v]; }
+ public:
+ typedef adjacency_list<listS,
+ listS,
+ undirectedS,
+ vertex_property,
+ EdgeProperty,
+ GraphProperty,
+ listS> graph_type;
- edge_bundled& operator [](edge_descriptor e)
- { return m_graph[e]; }
+ 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;
- const edge_bundled& operator [](edge_descriptor e) const
- { return m_graph[e]; }
-#endif
+ public:
+ typedef undirected_graph_tag graph_tag;
- // Graph concepts
- static inline vertex_descriptor null_vertex()
- { return graph_type::null_vertex(); }
+ // 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;
+
+ 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 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 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;
+ tie(i, i_end) = vertices(m_graph);
+ m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
+ }
+
+ inline void remove_vertex_and_renumber_indices(vertex_iterator i)
+ {
+ vertex_iterator j = next(i), j_end = vertices(m_graph).second;
+ vertex_index_type n = get(vertex_index, m_graph, *i);
+
+ // remove the offending vertex and renumber everything after
+ remove_vertex(*i);
+ m_max_vertex_index = renumber_vertex_indices(j, 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(); }
private:
- graph_type m_graph;
- vertices_size_type m_num_vertices;
- edges_size_type m_num_edges;
- vertex_index_type m_max_vertex_index;
+ inline vertices_size_type
+ renumber_vertex_indices(vertex_iterator i,
+ vertex_iterator i_end,
+ vertices_size_type n)
+ {
+ typename property_map<graph_type, vertex_index_t>::type
+ indices = get(vertex_index, m_graph);
+ for( ; i != i_end; ++i) {
+ indices[*i] = n++;
+ }
+ return n;
+ }
+
+ 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
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
source(typename undirected_graph<VP,EP,GP>::edge_descriptor e,
- const undirected_graph<VP,EP,GP> &g)
+ const undirected_graph<VP,EP,GP> &g)
{
- return source(e, g.impl());
+ return source(e, g.impl());
}
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
target(typename undirected_graph<VP,EP,GP>::edge_descriptor e,
- const undirected_graph<VP,EP,GP> &g)
+ const undirected_graph<VP,EP,GP> &g)
{
- return target(e, g.impl());
+ return target(e, g.impl());
}
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::degree_size_type
out_degree(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
+ const undirected_graph<VP,EP,GP> &g)
{
- return out_degree(v, g.impl());
+ return out_degree(v, g.impl());
}
template <class VP, class EP, class GP>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::out_edge_iterator,
- typename undirected_graph<VP,EP,GP>::out_edge_iterator
- >
+ typename undirected_graph<VP,EP,GP>::out_edge_iterator,
+ typename undirected_graph<VP,EP,GP>::out_edge_iterator
+ >
out_edges(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
+ const undirected_graph<VP,EP,GP> &g)
{
- return out_edges(v, g.impl());
+ return out_edges(v, g.impl());
}
// BidirectionalGraph concepts
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::degree_size_type
in_degree(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
+ const undirected_graph<VP,EP,GP> &g)
{
- return in_degree(v, g.impl());
+ return in_degree(v, g.impl());
}
template <class VP, class EP, class GP>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::in_edge_iterator,
- typename undirected_graph<VP,EP,GP>::in_edge_iterator
- >
+ typename undirected_graph<VP,EP,GP>::in_edge_iterator,
+ typename undirected_graph<VP,EP,GP>::in_edge_iterator
+ >
in_edges(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
+ const undirected_graph<VP,EP,GP> &g)
+ {
+ return in_edges(v, g.impl());
+ }
+
+
+ template <class VP, class EP, class GP>
+ inline std::pair<
+ typename undirected_graph<VP,EP,GP>::out_edge_iterator,
+ typename undirected_graph<VP,EP,GP>::out_edge_iterator
+ >
+ incident_edges(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ const undirected_graph<VP,EP,GP> &g)
{
- return in_edges(v, g.impl());
+ return out_edges(v, g.impl());
}
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::degree_size_type
degree(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP> &g)
+ const undirected_graph<VP,EP,GP> &g)
{
- return degree(v, g.impl());
+ return degree(v, g.impl());
}
// AdjacencyGraph concepts
@@ -291,27 +325,44 @@
typename undirected_graph<VP,EP,GP>::adjacency_iterator
>
adjacent_vertices(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
+ const undirected_graph<VP,EP,GP>& g)
{
return adjacent_vertices(v, g.impl());
}
+ template <class VP, class EP, class GP>
+ typename undirected_graph<VP,EP,GP>::vertex_descriptor
+ vertex(typename undirected_graph<VP,EP,GP>::vertices_size_type n,
+ const undirected_graph<VP,EP,GP>& g)
+ {
+ return vertex(g.impl());
+ }
+
+ template <class VP, class EP, class GP>
+ std::pair<typename undirected_graph<VP,EP,GP>::edge_descriptor, bool>
+ edge(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
+ typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ const undirected_graph<VP,EP,GP>& g)
+ {
+ return edge(u, v, g.impl());
+ }
+
// VertexListGraph concepts
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::vertices_size_type
num_vertices(const undirected_graph<VP,EP,GP>& g)
{
- return g.num_vertices();
+ return g.num_vertices();
}
template <class VP, class EP, class GP>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::vertex_iterator,
- typename undirected_graph<VP,EP,GP>::vertex_iterator
- >
+ typename undirected_graph<VP,EP,GP>::vertex_iterator,
+ typename undirected_graph<VP,EP,GP>::vertex_iterator
+ >
vertices(const undirected_graph<VP,EP,GP>& g)
{
- return vertices(g.impl());
+ return vertices(g.impl());
}
// EdgeListGraph concepts
@@ -319,17 +370,17 @@
inline typename undirected_graph<VP,EP,GP>::edges_size_type
num_edges(const undirected_graph<VP,EP,GP>& g)
{
- return g.num_edges();
+ return g.num_edges();
}
template <class VP, class EP, class GP>
inline std::pair<
- typename undirected_graph<VP,EP,GP>::edge_iterator,
- typename undirected_graph<VP,EP,GP>::edge_iterator
- >
+ typename undirected_graph<VP,EP,GP>::edge_iterator,
+ typename undirected_graph<VP,EP,GP>::edge_iterator
+ >
edges(const undirected_graph<VP,EP,GP>& g)
{
- return edges(g.impl());
+ return edges(g.impl());
}
@@ -338,24 +389,24 @@
inline typename undirected_graph<VP,EP,GP>::vertex_descriptor
add_vertex(undirected_graph<VP,EP,GP> &g)
{
- return g.add_vertex();
+ return g.add_vertex();
}
template <class VP, class EP, class GP>
inline void
clear_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- undirected_graph<VP,EP,GP> &g)
+ undirected_graph<VP,EP,GP> &g)
{
- return g.clear_vertex(v);
+ return g.clear_vertex(v);
}
template <class VP, class EP, class GP>
inline void
remove_vertex(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- undirected_graph<VP,EP,GP> &g)
+ undirected_graph<VP,EP,GP> &g)
{
- return g.remove_vertex(v);
+ return g.remove_vertex(v);
}
@@ -363,107 +414,115 @@
template <class VP, class EP, class GP>
inline std::pair<typename undirected_graph<VP,EP,GP>::edge_descriptor, bool>
add_edge(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
- typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- undirected_graph<VP,EP,GP> &g)
+ typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ undirected_graph<VP,EP,GP> &g)
{
- return g.add_edge(u, v);
+ return g.add_edge(u, v);
}
template <class VP, class EP, class GP>
inline void
remove_edge(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
- typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- undirected_graph<VP,EP,GP> &g)
+ typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ undirected_graph<VP,EP,GP> &g)
{
- return g.remove_edge(u, v);
+ return g.remove_edge(u, v);
}
template <class VP, class EP, class GP>
inline void
remove_edge(typename undirected_graph<VP,EP,GP>::edge_descriptor e,
- undirected_graph<VP,EP,GP> &g)
+ undirected_graph<VP,EP,GP> &g)
{
- return g.remove_edge(e);
+ return g.remove_edge(e);
}
template <class VP, class EP, class GP>
inline void
remove_edge(typename undirected_graph<VP,EP,GP>::edge_iterator i,
- undirected_graph<VP,EP,GP> &g)
+ undirected_graph<VP,EP,GP> &g)
{
- return g.remove_edge(i);
+ return g.remove_edge(i);
}
template <class VP, class EP, class GP, class Predicate>
inline void
remove_edge_if(Predicate pred,
- undirected_graph<VP,EP,GP> &g)
+ undirected_graph<VP,EP,GP> &g)
{
- return remove_edge_if(pred, g.impl());
+ return remove_edge_if(pred, g.impl());
}
template <class VP, class EP, class GP, class Predicate>
inline void
+ remove_incident_edge_if(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ Predicate pred,
+ undirected_graph<VP,EP,GP> &g)
+ {
+ return remove_out_edge_if(v, pred, g.impl());
+ }
+
+ template <class VP, class EP, class GP, class Predicate>
+ inline void
remove_out_edge_if(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- Predicate pred,
- undirected_graph<VP,EP,GP> &g)
+ Predicate pred,
+ undirected_graph<VP,EP,GP> &g)
{
- return remove_out_edge_if(v, pred, g.impl());
+ return remove_out_edge_if(v, pred, g.impl());
}
template <class VP, class EP, class GP, class Predicate>
inline void
remove_in_edge_if(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- Predicate pred,
- undirected_graph<VP,EP,GP> &g)
+ Predicate pred,
+ undirected_graph<VP,EP,GP> &g)
{
- return remove_in_edge_if(v, pred, g.impl());
+ 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;
- };
- };
+ 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;
+ typedef detail::undirected_graph_vertex_property_selector type;
};
template <>
struct edge_property_selector<undirected_graph_tag>
{
- typedef detail::undirected_graph_edge_property_selector type;
+ typedef detail::undirected_graph_edge_property_selector type;
};
// PropertyGraph concepts
@@ -471,30 +530,51 @@
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());
+ return get(p, g.impl());
}
template <class VP, class EP, class GP, typename Property>
inline typename property_map<undirected_graph<VP,EP,GP>, Property>::const_type
get(Property p, const undirected_graph<VP,EP,GP>& g)
{
- return get(p, g.impl());
+ return get(p, g.impl());
}
template <class VP, class EP, class GP, typename Property, typename Key>
inline typename property_traits<
- typename property_map<typename undirected_graph<VP,EP,GP>::graph_type, Property>::const_type
- >::value_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)
{
- return 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, undirected_graph<VP,EP,GP> &g, const Key& k, const Value& v)
{
- put(p, g.impl(), k, v);
+ put(p, g.impl(), k, v);
+ }
+
+ template <class VP, class EP, class GP, class Property>
+ typename graph_property<undirected_graph<VP,EP,GP>, Property>::type&
+ get_property(undirected_graph<VP,EP,GP>& g, Property p)
+ {
+ return get_property(g.impl(), p);
+ }
+
+ template <class VP, class EP, class GP, class Property>
+ const typename graph_property<undirected_graph<VP,EP,GP>, Property>::type&
+ get_property(const undirected_graph<VP,EP,GP>& g, Property p)
+ {
+ return get_property(g.impl(), p);
+ }
+
+ template <class VP, class EP, class GP, class Property, class Value>
+ void
+ set_property(undirected_graph<VP,EP,GP>& g, Property p, Value v)
+ {
+ return set_property(g.impl(), p, v);
}
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
@@ -502,64 +582,67 @@
inline typename property_map<undirected_graph<VP,EP,GP>, Type Bundle::*>::type
get(Type Bundle::* p, undirected_graph<VP,EP,GP>& g)
{
- typedef typename property_map<undirected_graph<VP,EP,GP>, Type Bundle::*>::type
- return_type;
- return return_type(&g, p);
+ 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 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);
+ 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);
+ 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);
+ // 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
+ inline typename undirected_graph<VP,EP,GP>::vertex_index_type
get_vertex_index(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
+ const undirected_graph<VP,EP,GP>& g)
{
- return get(vertex_index, g, v);
+ 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
+ typename undirected_graph<VP,EP,GP>::vertex_index_type
max_vertex_index(const undirected_graph<VP,EP,GP>& g)
{
- return g.max_vertex_index();
+ return g.max_vertex_index();
}
template <class VP, class EP, class GP>
void
- renumber_vertex_indices(undirected_graph<VP,EP,GP>& g)
+ renumber_vertex_indices(
+ typename undirected_graph<VP,EP,GP>::vertex_iterator i,
+ undirected_graph<VP,EP,GP>& g)
+ {
+ g.renumber_vertex_indices(i);
+ }
+
+ template <class VP, class EP, class GP>
+ inline void
+ remove_vertex_and_renumber_indices(
+ typename undirected_graph<VP,EP,GP>::vertex_iterator i,
+ undirected_graph<VP,EP,GP>& g)
{
- g.renumber_vertex_indices();
+ g.remove_vertex_and_renumber_indices(i);
}
}
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-25 13:33:40 EDT (Mon, 25 Jun 2007)
@@ -27,8 +27,6 @@
typedef Graph::vertex_descriptor Vertex;
typedef Graph::edge_descriptor Edge;
-typedef property_map<Graph, string Target::*>::type TargetNameMap;
-
typedef map<string, Vertex> TargetMap;
struct CycleDetector : public dfs_visitor<>
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-25 13:33:40 EDT (Mon, 25 Jun 2007)
@@ -40,18 +40,16 @@
// run a breadth-first search on the graph and record
// the kevin bacon numbers for each actor
breadth_first_search(
- g, kevin,
- visitor(
- make_bfs_visitor(
- record_distances(dists, on_tree_edge())
- )
- )
- );
+ 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;
for(tie(i, j) = vertices(g); i != j; ++i) {
- cout << g[*i].distance << " : " << g[*i].name << "\n";
+ cout << g[*i].distance << " : " << g[*i].name << "\n";
}
return 0;
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-25 13:33:40 EDT (Mon, 25 Jun 2007)
@@ -26,15 +26,15 @@
// get the source and target nodes from the graph
if(argc < 2) {
- cerr << "usage: actor_paths actor [actor] < movies";
- return -1;
+ cerr << "usage: actor_paths actor [actor] < movies";
+ return -1;
}
- else if(argc == 2) {
- tgt = argv[1];
+ else if(argc == 2) {
+ tgt = argv[1];
}
else {
- src = argv[1];
- tgt = argv[2];
+ src = argv[1];
+ tgt = argv[2];
}
// instantiate the graph and the actor map
@@ -48,12 +48,12 @@
Vertex u = find_actor_vertex(g, actors, src);
Vertex v = find_actor_vertex(g, actors, tgt);
if(u == Graph::null_vertex()) {
- cerr << "could not find actor " << src << "\n";
- return -1;
+ cerr << "could not find actor " << src << "\n";
+ return -1;
}
if(v == Graph::null_vertex()) {
- cerr << "could not find actor " << tgt << "\n";
- return -1;
+ cerr << "could not find actor " << tgt << "\n";
+ return -1;
}
// get the parents map so we can record them
@@ -61,44 +61,40 @@
ActorParentMap parents = get(&Actor::parent, g);
breadth_first_search(
- g, u,
- visitor(
- make_bfs_visitor(
- record_predecessors(parents, on_tree_edge())
- )
- )
- );
+ 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
while(v != u) {
- Vertex p = parents[v];
+ Vertex p = parents[v];
- // what are our two names...
- string from = g[v].name;
- string to = g[p].name;
-
- // what edge does (v,p) exist on. unforunately, because this isn't
- // an adjacency matrix, we actually have to search the outgoing (or
- // incoming?) edges of v to find p, and get the edge associated with
- // that performance.
- Edge e;
- Graph::out_edge_iterator i, j;
- for(tie(i, j) = out_edges(v, g); i != j; ++i) {
- if(target(*i, g) == p) {
- e = *i;
- break;
- }
- }
+ // what are our two names...
+ string from = g[v].name;
+ string to = g[p].name;
+
+ // what edge does (v,p) exist on. unforunately, because this isn't
+ // an adjacency matrix, we actually have to search the outgoing (or
+ // incoming?) edges of v to find p, and get the edge associated with
+ // that performance.
+ Edge e;
+ bool found;
+ tie(e, found) = edge(v, p, g);
+ BOOST_ASSERT(found);
- // what's the movie name?
- string movie = g[e].name;
+ // what's the movie name?
+ string movie = g[e].name;
- // print out the path
- cout << from << " starred with " << to << " in '" << movie << "'\n";
+ // print out the path
+ cout << from << " starred with " << to << " in '" << movie << "'\n";
- // move to the next predecessor
- v = p;
+ // move to the next predecessor
+ v = p;
}
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