|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50206 - in trunk: boost/graph/detail libs/graph/test
From: asutton_at_[hidden]
Date: 2008-12-08 14:03:21
Author: asutton
Date: 2008-12-08 14:03:20 EST (Mon, 08 Dec 2008)
New Revision: 50206
URL: http://svn.boost.org/trac/boost/changeset/50206
Log:
Fixed #1622. A viable solution relies on the fact that incident edges in a
loop are stored adjacently in the out edge list of the vertex. A simple
modification of the global edge erasing loop for undirected graphs will
skip the next iterator if both the current and next contain the same iterator.
Added:
trunk/libs/graph/test/adj_list_loops.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/detail/adjacency_list.hpp | 392 ++++++++++++++++++++-------------------
trunk/libs/graph/test/Jamfile.v2 | 1
2 files changed, 201 insertions(+), 192 deletions(-)
Modified: trunk/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/detail/adjacency_list.hpp (original)
+++ trunk/boost/graph/detail/adjacency_list.hpp 2008-12-08 14:03:20 EST (Mon, 08 Dec 2008)
@@ -140,7 +140,7 @@
, EdgeDescriptor
, Difference
> super_t;
-
+
inline out_edge_iter() { }
inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
: super_t(i), m_src(src) { }
@@ -148,12 +148,12 @@
inline EdgeDescriptor
dereference() const
{
- return EdgeDescriptor(m_src, (*this->base()).get_target(),
+ return EdgeDescriptor(m_src, (*this->base()).get_target(),
&(*this->base()).get_property());
}
VertexDescriptor m_src;
};
-
+
template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
struct in_edge_iter
: iterator_adaptor<
@@ -173,9 +173,9 @@
, EdgeDescriptor
, Difference
> super_t;
-
+
inline in_edge_iter() { }
- inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
+ inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
: super_t(i), m_src(src) { }
inline EdgeDescriptor
@@ -211,10 +211,10 @@
> super_t;
undirected_edge_iter() {}
-
+
explicit undirected_edge_iter(EdgeIter i)
: super_t(i) {}
-
+
inline EdgeDescriptor
dereference() const {
return EdgeDescriptor(
@@ -268,11 +268,11 @@
inline stored_edge_property(Vertex target,
const Property& p = Property())
: stored_edge<Vertex>(target), m_property(new Property(p)) { }
- stored_edge_property(const self& x)
+ stored_edge_property(const self& x)
: Base(x), m_property(const_cast<self&>(x).m_property) { }
self& operator=(const self& x) {
Base::operator=(x);
- m_property = const_cast<self&>(x).m_property;
+ m_property = const_cast<self&>(x).m_property;
return *this;
}
inline Property& get_property() { return *m_property; }
@@ -298,7 +298,7 @@
inline stored_edge_iter(Vertex v, Iter i, void* = 0)
: stored_edge<Vertex>(v), m_iter(i) { }
inline Property& get_property() { return m_iter->get_property(); }
- inline const Property& get_property() const {
+ inline const Property& get_property() const {
return m_iter->get_property();
}
inline Iter get_iter() const { return m_iter; }
@@ -317,11 +317,11 @@
public:
typedef Property property_type;
inline stored_ra_edge_iter() { }
- inline stored_ra_edge_iter(Vertex v, Iter i = Iter(),
+ inline stored_ra_edge_iter(Vertex v, Iter i = Iter(),
EdgeVec* edge_vec = 0)
: stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
- inline const Property& get_property() const {
+ inline const Property& get_property() const {
return (*m_vec)[m_i].get_property();
}
inline Iter get_iter() const { return m_vec->begin() + m_i; }
@@ -331,7 +331,7 @@
};
} // namespace detail
-
+
template <class Tag, class Vertex, class Property>
const typename property_value<Property,Tag>::type&
get(Tag property_tag,
@@ -355,7 +355,7 @@
{
return get_property_value(e.get_property(), property_tag);
}
-
+
//=========================================================================
// Directed Edges Helper Class
@@ -378,7 +378,7 @@
template <class incidence_iterator, class EdgeList, class Predicate>
inline void
remove_directed_edge_if_dispatch(incidence_iterator first,
- incidence_iterator last,
+ incidence_iterator last,
EdgeList& el, Predicate pred,
boost::allow_parallel_edge_tag)
{
@@ -397,8 +397,8 @@
template <class incidence_iterator, class EdgeList, class Predicate>
inline void
remove_directed_edge_if_dispatch(incidence_iterator first,
- incidence_iterator last,
- EdgeList& el,
+ incidence_iterator last,
+ EdgeList& el,
Predicate pred,
boost::disallow_parallel_edge_tag)
{
@@ -410,12 +410,12 @@
}
}
- template <class PropT, class Graph, class incidence_iterator,
+ template <class PropT, class Graph, class incidence_iterator,
class EdgeList, class Predicate>
inline void
- undirected_remove_out_edge_if_dispatch(Graph& g,
+ undirected_remove_out_edge_if_dispatch(Graph& g,
incidence_iterator first,
- incidence_iterator last,
+ incidence_iterator last,
EdgeList& el, Predicate pred,
boost::allow_parallel_edge_tag)
{
@@ -444,8 +444,8 @@
else {
// Remove the edge from the target
detail::remove_directed_edge_dispatch
- (*i,
- g.out_edge_list(target(*i, g)),
+ (*i,
+ g.out_edge_list(target(*i, g)),
*(PropT*)(*i).get_property());
}
@@ -455,13 +455,13 @@
}
el.erase(first.base(), el.end());
}
- template <class PropT, class Graph, class incidence_iterator,
+ template <class PropT, class Graph, class incidence_iterator,
class EdgeList, class Predicate>
inline void
- undirected_remove_out_edge_if_dispatch(Graph& g,
+ undirected_remove_out_edge_if_dispatch(Graph& g,
incidence_iterator first,
- incidence_iterator last,
- EdgeList& el,
+ incidence_iterator last,
+ EdgeList& el,
Predicate pred,
boost::disallow_parallel_edge_tag)
{
@@ -475,8 +475,8 @@
if (source(*first, g) != target(*first, g)) {
// Remove the edge from the target
detail::remove_directed_edge_dispatch
- (*first,
- g.out_edge_list(target(*first, g)),
+ (*first,
+ g.out_edge_list(target(*first, g)),
*(PropT*)(*first).get_property());
}
@@ -510,7 +510,7 @@
// Placement of these overloaded remove_edge() functions
// inside the class avoids a VC++ bug.
-
+
// O(E/V)
inline void
remove_edge(typename Config::edge_descriptor e)
@@ -538,7 +538,7 @@
// O(1)
template <class Config>
- inline std::pair<typename Config::edge_iterator,
+ inline std::pair<typename Config::edge_iterator,
typename Config::edge_iterator>
edges(const directed_edges_helper<Config>& g_)
{
@@ -546,8 +546,8 @@
typedef typename Config::edge_iterator edge_iterator;
const graph_type& cg = static_cast<const graph_type&>(g_);
graph_type& g = const_cast<graph_type&>(cg);
- return std::make_pair( edge_iterator(g.vertex_set().begin(),
- g.vertex_set().begin(),
+ return std::make_pair( edge_iterator(g.vertex_set().begin(),
+ g.vertex_set().begin(),
g.vertex_set().end(), g),
edge_iterator(g.vertex_set().begin(),
g.vertex_set().end(),
@@ -565,7 +565,7 @@
template <class Config>
struct directed_graph_helper
- : public directed_edges_helper<Config> {
+ : public directed_edges_helper<Config> {
typedef typename Config::edge_descriptor edge_descriptor;
typedef adj_list_dir_traversal_tag traversal_category;
};
@@ -607,7 +607,7 @@
typename Config::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
remove_out_edge_if(*vi, pred, g);
- }
+ }
template <class EdgeOrIter, class Config>
inline void
@@ -619,7 +619,7 @@
// O(V + E) for allow_parallel_edges
// O(V * log(E/V)) for disallow_parallel_edges
template <class Config>
- inline void
+ inline void
clear_vertex(typename Config::vertex_descriptor u,
directed_graph_helper<Config>& g_)
{
@@ -635,7 +635,7 @@
}
template <class Config>
- inline void
+ inline void
clear_out_edges(typename Config::vertex_descriptor u,
directed_graph_helper<Config>& g_)
{
@@ -664,27 +664,27 @@
// O(log(E/V)) for disallow_parallel_edge_tag
template <class Config>
inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
- add_edge(typename Config::vertex_descriptor u,
+ add_edge(typename Config::vertex_descriptor u,
typename Config::vertex_descriptor v,
- const typename Config::edge_property_type& p,
+ const typename Config::edge_property_type& p,
directed_graph_helper<Config>& g_)
{
typedef typename Config::edge_descriptor edge_descriptor;
typedef typename Config::graph_type graph_type;
typedef typename Config::StoredEdge StoredEdge;
graph_type& g = static_cast<graph_type&>(g_);
- typename Config::OutEdgeList::iterator i;
+ typename Config::OutEdgeList::iterator i;
bool inserted;
- boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
+ boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
StoredEdge(v, p));
- return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
+ return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
inserted);
}
// Did not use default argument here because that
// causes Visual C++ to get confused.
template <class Config>
inline std::pair<typename Config::edge_descriptor, bool>
- add_edge(typename Config::vertex_descriptor u,
+ add_edge(typename Config::vertex_descriptor u,
typename Config::vertex_descriptor v,
directed_graph_helper<Config>& g_)
{
@@ -697,7 +697,7 @@
template <class Config>
struct undirected_graph_helper;
- struct undir_adj_list_traversal_tag :
+ struct undir_adj_list_traversal_tag :
public virtual vertex_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag,
@@ -713,8 +713,8 @@
// O(E/V)
template <class edge_descriptor, class Config>
static void
- apply(edge_descriptor e,
- undirected_graph_helper<Config>& g_,
+ apply(edge_descriptor e,
+ undirected_graph_helper<Config>& g_,
StoredProperty& p)
{
typedef typename Config::global_edgelist_selector EdgeListS;
@@ -722,7 +722,7 @@
typedef typename Config::graph_type graph_type;
graph_type& g = static_cast<graph_type&>(g_);
-
+
typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
typename Config::OutEdgeList::iterator out_i = out_el.begin();
for (; out_i != out_el.end(); ++out_i)
@@ -777,7 +777,7 @@
// O(E/V)
template <class Graph, class EdgeList, class Vertex>
inline void
- remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
+ remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
boost::allow_parallel_edge_tag cat)
{
typedef typename Graph::global_edgelist_selector EdgeListS;
@@ -785,15 +785,23 @@
typedef typename EdgeList::value_type StoredEdge;
typename EdgeList::iterator i = el.begin(), end = el.end();
- for (; i != end; ++i)
- if ((*i).get_target() == v)
+ for (; i != end; ++i) {
+ if((*i).get_target() == v) {
+ // NOTE: Wihtout this skip, this loop will double-delete properties
+ // of loop edges. This solution is based on the observation that
+ // the incidence edges of a vertex with a loop are adjacent in the
+ // out edge list. This *may* actually hold for multisets also.
+ bool skip = (next(i) != end && i->get_iter() == next(i)->get_iter());
g.m_edges.erase((*i).get_iter());
+ if(skip) ++i;
+ }
+ }
detail::erase_from_incidence_list(el, v, cat);
}
// O(log(E/V))
template <class Graph, class EdgeList, class Vertex>
inline void
- remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
+ remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
boost::disallow_parallel_edge_tag)
{
typedef typename Graph::global_edgelist_selector EdgeListS;
@@ -857,15 +865,15 @@
// Had to make these non-members to avoid accidental instantiation
// on SGI MIPSpro C++
template <class C>
- inline typename C::InEdgeList&
- in_edge_list(undirected_graph_helper<C>&,
+ inline typename C::InEdgeList&
+ in_edge_list(undirected_graph_helper<C>&,
typename C::vertex_descriptor v)
{
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
return sv->m_out_edges;
}
template <class C>
- inline const typename C::InEdgeList&
+ inline const typename C::InEdgeList&
in_edge_list(const undirected_graph_helper<C>&,
typename C::vertex_descriptor v) {
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
@@ -886,8 +894,8 @@
// O(E/V) or O(log(E/V))
template <class Config>
void
- remove_edge(typename Config::vertex_descriptor u,
- typename Config::vertex_descriptor v,
+ remove_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
undirected_graph_helper<Config>& g_)
{
typedef typename Config::global_edgelist_selector EdgeListS;
@@ -899,7 +907,7 @@
detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
}
-
+
template <class Config, class Predicate>
void
remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
@@ -907,7 +915,7 @@
{
typedef typename Config::global_edgelist_selector EdgeListS;
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
-
+
typedef typename Config::graph_type graph_type;
typedef typename Config::OutEdgeList::value_type::property_type PropT;
graph_type& g = static_cast<graph_type&>(g_);
@@ -949,7 +957,7 @@
// O(1)
template <class Config>
- inline std::pair<typename Config::edge_iterator,
+ inline std::pair<typename Config::edge_iterator,
typename Config::edge_iterator>
edges(const undirected_graph_helper<Config>& g_)
{
@@ -963,7 +971,7 @@
// O(1)
template <class Config>
inline typename Config::edges_size_type
- num_edges(const undirected_graph_helper<Config>& g_)
+ num_edges(const undirected_graph_helper<Config>& g_)
{
typedef typename Config::graph_type graph_type;
const graph_type& g = static_cast<const graph_type&>(g_);
@@ -971,7 +979,7 @@
}
// O(E/V * E/V)
template <class Config>
- inline void
+ inline void
clear_vertex(typename Config::vertex_descriptor u,
undirected_graph_helper<Config>& g_)
{
@@ -982,7 +990,7 @@
typedef typename Config::edge_parallel_category Cat;
graph_type& g = static_cast<graph_type&>(g_);
typename Config::OutEdgeList& el = g.out_edge_list(u);
- typename Config::OutEdgeList::iterator
+ typename Config::OutEdgeList::iterator
ei = el.begin(), ei_end = el.end();
for (; ei != ei_end; ++ei) {
detail::erase_from_incidence_list
@@ -995,8 +1003,8 @@
// O(log(E/V)) for disallow_parallel_edge_tag
template <class Config>
inline std::pair<typename Config::edge_descriptor, bool>
- add_edge(typename Config::vertex_descriptor u,
- typename Config::vertex_descriptor v,
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
const typename Config::edge_property_type& p,
undirected_graph_helper<Config>& g_)
{
@@ -1007,11 +1015,11 @@
bool inserted;
typename Config::EdgeContainer::value_type e(u, v, p);
- typename Config::EdgeContainer::iterator p_iter
+ typename Config::EdgeContainer::iterator p_iter
= graph_detail::push(g.m_edges, e).first;
typename Config::OutEdgeList::iterator i;
- boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
+ boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
StoredEdge(v, p_iter, &g.m_edges));
if (inserted) {
boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
@@ -1025,8 +1033,8 @@
}
template <class Config>
inline std::pair<typename Config::edge_descriptor, bool>
- add_edge(typename Config::vertex_descriptor u,
- typename Config::vertex_descriptor v,
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
undirected_graph_helper<Config>& g_)
{
typename Config::edge_property_type p;
@@ -1036,7 +1044,7 @@
// O(1)
template <class Config>
inline typename Config::degree_size_type
- degree(typename Config::vertex_descriptor u,
+ degree(typename Config::vertex_descriptor u,
const undirected_graph_helper<Config>& g_)
{
typedef typename Config::graph_type Graph;
@@ -1045,9 +1053,9 @@
}
template <class Config>
- inline std::pair<typename Config::in_edge_iterator,
+ inline std::pair<typename Config::in_edge_iterator,
typename Config::in_edge_iterator>
- in_edges(typename Config::vertex_descriptor u,
+ in_edges(typename Config::vertex_descriptor u,
const undirected_graph_helper<Config>& g_)
{
typedef typename Config::graph_type Graph;
@@ -1068,7 +1076,7 @@
//=========================================================================
// Bidirectional Graph Helper Class
- struct bidir_adj_list_traversal_tag :
+ struct bidir_adj_list_traversal_tag :
public virtual vertex_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag,
@@ -1084,15 +1092,15 @@
// Had to make these non-members to avoid accidental instantiation
// on SGI MIPSpro C++
template <class C>
- inline typename C::InEdgeList&
- in_edge_list(bidirectional_graph_helper<C>&,
+ inline typename C::InEdgeList&
+ in_edge_list(bidirectional_graph_helper<C>&,
typename C::vertex_descriptor v)
{
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
return sv->m_in_edges;
}
template <class C>
- inline const typename C::InEdgeList&
+ inline const typename C::InEdgeList&
in_edge_list(const bidirectional_graph_helper<C>&,
typename C::vertex_descriptor v) {
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
@@ -1118,9 +1126,9 @@
}
template <class Config>
- inline std::pair<typename Config::in_edge_iterator,
+ inline std::pair<typename Config::in_edge_iterator,
typename Config::in_edge_iterator>
- in_edges(typename Config::vertex_descriptor u,
+ in_edges(typename Config::vertex_descriptor u,
const bidirectional_graph_helper<Config>& g_)
{
typedef typename Config::graph_type graph_type;
@@ -1134,7 +1142,7 @@
// O(1)
template <class Config>
- inline std::pair<typename Config::edge_iterator,
+ inline std::pair<typename Config::edge_iterator,
typename Config::edge_iterator>
edges(const bidirectional_graph_helper<Config>& g_)
{
@@ -1156,7 +1164,7 @@
{
typedef typename Config::graph_type graph_type;
typedef typename Config::out_edge_iterator out_edge_iterator;
-
+
std::pair<out_edge_iterator, out_edge_iterator>
get_parallel_edge_sublist(typename Config::edge_descriptor e,
const graph_type& g,
@@ -1197,7 +1205,7 @@
typedef typename Config::edgelist_selector OutEdgeListS;
- std::pair<out_edge_iterator, out_edge_iterator> rng =
+ std::pair<out_edge_iterator, out_edge_iterator> rng =
get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
rng.first = std::find(rng.first, rng.second, e);
assert(rng.first != rng.second);
@@ -1227,8 +1235,8 @@
// O(log(E/V)) for disallow_parallel_edge_tag
template <class Config>
inline void
- remove_edge(typename Config::vertex_descriptor u,
- typename Config::vertex_descriptor v,
+ remove_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
bidirectional_graph_helper_with_property<Config>& g_)
{
typedef typename Config::global_edgelist_selector EdgeListS;
@@ -1264,7 +1272,7 @@
typedef typename Config::graph_type graph_type;
typedef typename Config::OutEdgeList::value_type::property_type PropT;
graph_type& g = static_cast<graph_type&>(g_);
-
+
typedef typename Config::EdgeIter EdgeIter;
typedef std::vector<EdgeIter> Garbage;
Garbage garbage;
@@ -1338,7 +1346,7 @@
// O(1)
template <class Config>
inline typename Config::edges_size_type
- num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
+ num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
{
typedef typename Config::graph_type graph_type;
const graph_type& g = static_cast<const graph_type&>(g_);
@@ -1358,20 +1366,20 @@
typedef typename Config::edge_parallel_category Cat;
graph_type& g = static_cast<graph_type&>(g_);
typename Config::OutEdgeList& el = g.out_edge_list(u);
- typename Config::OutEdgeList::iterator
+ typename Config::OutEdgeList::iterator
ei = el.begin(), ei_end = el.end();
for (; ei != ei_end; ++ei) {
detail::erase_from_incidence_list
(in_edge_list(g, (*ei).get_target()), u, Cat());
g.m_edges.erase((*ei).get_iter());
- }
+ }
typename Config::InEdgeList& in_el = in_edge_list(g, u);
- typename Config::InEdgeList::iterator
+ typename Config::InEdgeList::iterator
in_ei = in_el.begin(), in_ei_end = in_el.end();
for (; in_ei != in_ei_end; ++in_ei) {
detail::erase_from_incidence_list
(g.out_edge_list((*in_ei).get_target()), u, Cat());
- g.m_edges.erase((*in_ei).get_iter());
+ g.m_edges.erase((*in_ei).get_iter());
}
g.out_edge_list(u).clear();
in_edge_list(g, u).clear();
@@ -1389,13 +1397,13 @@
typedef typename Config::edge_parallel_category Cat;
graph_type& g = static_cast<graph_type&>(g_);
typename Config::OutEdgeList& el = g.out_edge_list(u);
- typename Config::OutEdgeList::iterator
+ typename Config::OutEdgeList::iterator
ei = el.begin(), ei_end = el.end();
for (; ei != ei_end; ++ei) {
detail::erase_from_incidence_list
(in_edge_list(g, (*ei).get_target()), u, Cat());
g.m_edges.erase((*ei).get_iter());
- }
+ }
g.out_edge_list(u).clear();
}
@@ -1411,12 +1419,12 @@
typedef typename Config::edge_parallel_category Cat;
graph_type& g = static_cast<graph_type&>(g_);
typename Config::InEdgeList& in_el = in_edge_list(g, u);
- typename Config::InEdgeList::iterator
+ typename Config::InEdgeList::iterator
in_ei = in_el.begin(), in_ei_end = in_el.end();
for (; in_ei != in_ei_end; ++in_ei) {
detail::erase_from_incidence_list
(g.out_edge_list((*in_ei).get_target()), u, Cat());
- g.m_edges.erase((*in_ei).get_iter());
+ g.m_edges.erase((*in_ei).get_iter());
}
in_edge_list(g, u).clear();
}
@@ -1426,7 +1434,7 @@
template <class Config>
inline std::pair<typename Config::edge_descriptor, bool>
add_edge(typename Config::vertex_descriptor u,
- typename Config::vertex_descriptor v,
+ typename Config::vertex_descriptor v,
const typename Config::edge_property_type& p,
bidirectional_graph_helper_with_property<Config>& g_)
{
@@ -1436,19 +1444,19 @@
typedef typename Config::StoredEdge StoredEdge;
bool inserted;
typename Config::EdgeContainer::value_type e(u, v, p);
- typename Config::EdgeContainer::iterator p_iter
+ typename Config::EdgeContainer::iterator p_iter
= graph_detail::push(g.m_edges, e).first;
typename Config::OutEdgeList::iterator i;
- boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
+ boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
StoredEdge(v, p_iter, &g.m_edges));
if (inserted) {
boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
- return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
+ return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
true);
} else {
g.m_edges.erase(p_iter);
- return std::make_pair(edge_descriptor(u, v,
- &i->get_iter()->get_property()),
+ return std::make_pair(edge_descriptor(u, v,
+ &i->get_iter()->get_property()),
false);
}
}
@@ -1465,7 +1473,7 @@
// O(1)
template <class Config>
inline typename Config::degree_size_type
- degree(typename Config::vertex_descriptor u,
+ degree(typename Config::vertex_descriptor u,
const bidirectional_graph_helper_with_property<Config>& g_)
{
typedef typename Config::graph_type graph_type;
@@ -1505,15 +1513,15 @@
// Borland gets confused about constness.
// O(E/V)
- inline std::pair<edge_descriptor,bool>
- edge_dispatch(const AdjList& g,
- vertex_descriptor u, vertex_descriptor v,
+ inline std::pair<edge_descriptor,bool>
+ edge_dispatch(const AdjList& g,
+ vertex_descriptor u, vertex_descriptor v,
boost::allow_parallel_edge_tag) const
{
bool found;
const typename Config::OutEdgeList& el = g.out_edge_list(u);
- typename Config::OutEdgeList::const_iterator
- i = std::find_if(el.begin(), el.end(),
+ typename Config::OutEdgeList::const_iterator
+ i = std::find_if(el.begin(), el.end(),
detail::target_is<vertex_descriptor>(v));
found = (i != g.out_edge_list(u).end());
if (found)
@@ -1523,9 +1531,9 @@
return std::make_pair(edge_descriptor(u, v, 0), false);
}
// O(log(E/V))
- inline std::pair<edge_descriptor,bool>
- edge_dispatch(const AdjList& g,
- vertex_descriptor u, vertex_descriptor v,
+ inline std::pair<edge_descriptor,bool>
+ edge_dispatch(const AdjList& g,
+ vertex_descriptor u, vertex_descriptor v,
boost::disallow_parallel_edge_tag) const
{
bool found;
@@ -1533,7 +1541,7 @@
but the VC++ std::set::find() const returns const_iterator.
And since iterator should be convertible to const_iterator, the
following should work everywhere. -Jeremy */
- typename Config::OutEdgeList::const_iterator
+ typename Config::OutEdgeList::const_iterator
i = g.out_edge_list(u).find(StoredEdge(v)),
end = g.out_edge_list(u).end();
found = (i != end);
@@ -1546,9 +1554,9 @@
};
template <class Config, class Base>
- inline std::pair<typename Config::adjacency_iterator,
+ inline std::pair<typename Config::adjacency_iterator,
typename Config::adjacency_iterator>
- adjacent_vertices(typename Config::vertex_descriptor u,
+ adjacent_vertices(typename Config::vertex_descriptor u,
const adj_list_helper<Config, Base>& g_)
{
typedef typename Config::graph_type AdjList;
@@ -1561,9 +1569,9 @@
adjacency_iterator(last, &g));
}
template <class Config, class Base>
- inline std::pair<typename Config::inv_adjacency_iterator,
+ inline std::pair<typename Config::inv_adjacency_iterator,
typename Config::inv_adjacency_iterator>
- inv_adjacent_vertices(typename Config::vertex_descriptor u,
+ inv_adjacent_vertices(typename Config::vertex_descriptor u,
const adj_list_helper<Config, Base>& g_)
{
typedef typename Config::graph_type AdjList;
@@ -1576,9 +1584,9 @@
inv_adjacency_iterator(last, &g));
}
template <class Config, class Base>
- inline std::pair<typename Config::out_edge_iterator,
+ inline std::pair<typename Config::out_edge_iterator,
typename Config::out_edge_iterator>
- out_edges(typename Config::vertex_descriptor u,
+ out_edges(typename Config::vertex_descriptor u,
const adj_list_helper<Config, Base>& g_)
{
typedef typename Config::graph_type AdjList;
@@ -1590,7 +1598,7 @@
out_edge_iterator(g.out_edge_list(u).end(), u));
}
template <class Config, class Base>
- inline std::pair<typename Config::vertex_iterator,
+ inline std::pair<typename Config::vertex_iterator,
typename Config::vertex_iterator>
vertices(const adj_list_helper<Config, Base>& g_)
{
@@ -1609,7 +1617,7 @@
}
template <class Config, class Base>
inline typename Config::degree_size_type
- out_degree(typename Config::vertex_descriptor u,
+ out_degree(typename Config::vertex_descriptor u,
const adj_list_helper<Config, Base>& g_)
{
typedef typename Config::graph_type AdjList;
@@ -1618,8 +1626,8 @@
}
template <class Config, class Base>
inline std::pair<typename Config::edge_descriptor, bool>
- edge(typename Config::vertex_descriptor u,
- typename Config::vertex_descriptor v,
+ edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
const adj_list_helper<Config, Base>& g_)
{
typedef typename Config::graph_type Graph;
@@ -1642,8 +1650,8 @@
typename Config::OutEdgeList& el = g.out_edge_list(u);
typename Config::OutEdgeList::iterator first, last;
typename Config::EdgeContainer fake_edge_container;
- tie(first, last) =
- std::equal_range(el.begin(), el.end(),
+ tie(first, last) =
+ std::equal_range(el.begin(), el.end(),
StoredEdge(v, fake_edge_container.end(),
&fake_edge_container));
return std::make_pair(out_edge_iterator(first, u),
@@ -1652,7 +1660,7 @@
template <class Config>
inline typename Config::degree_size_type
- in_degree(typename Config::vertex_descriptor u,
+ in_degree(typename Config::vertex_descriptor u,
const directed_edges_helper<Config>& g_)
{
typedef typename Config::graph_type Graph;
@@ -1666,7 +1674,7 @@
inline
typename boost::property_map<typename Config::graph_type,
Property>::type
- get_dispatch(adj_list_helper<Config,Base>&, Property,
+ get_dispatch(adj_list_helper<Config,Base>&, Property,
boost::edge_property_tag) {
typedef typename Config::graph_type Graph;
typedef typename boost::property_map<Graph, Property>::type PA;
@@ -1674,9 +1682,9 @@
}
template <class Config, class Base, class Property>
inline
- typename boost::property_map<typename Config::graph_type,
+ typename boost::property_map<typename Config::graph_type,
Property>::const_type
- get_dispatch(const adj_list_helper<Config,Base>&, Property,
+ get_dispatch(const adj_list_helper<Config,Base>&, Property,
boost::edge_property_tag) {
typedef typename Config::graph_type Graph;
typedef typename boost::property_map<Graph, Property>::const_type PA;
@@ -1685,9 +1693,9 @@
template <class Config, class Base, class Property>
inline
- typename boost::property_map<typename Config::graph_type,
+ typename boost::property_map<typename Config::graph_type,
Property>::type
- get_dispatch(adj_list_helper<Config,Base>& g, Property,
+ get_dispatch(adj_list_helper<Config,Base>& g, Property,
boost::vertex_property_tag) {
typedef typename Config::graph_type Graph;
typedef typename boost::property_map<Graph, Property>::type PA;
@@ -1697,7 +1705,7 @@
inline
typename boost::property_map<typename Config::graph_type,
Property>::const_type
- get_dispatch(const adj_list_helper<Config, Base>& g, Property,
+ get_dispatch(const adj_list_helper<Config, Base>& g, Property,
boost::vertex_property_tag) {
typedef typename Config::graph_type Graph;
typedef typename boost::property_map<Graph, Property>::const_type PA;
@@ -1717,7 +1725,7 @@
}
template <class Config, class Base, class Property>
inline
- typename boost::property_map<typename Config::graph_type,
+ typename boost::property_map<typename Config::graph_type,
Property>::const_type
get(Property p, const adj_list_helper<Config, Base>& g) {
typedef typename property_kind<Property>::type Kind;
@@ -1727,7 +1735,7 @@
template <class Config, class Base, class Property, class Key>
inline
typename boost::property_traits<
- typename boost::property_map<typename Config::graph_type,
+ typename boost::property_map<typename Config::graph_type,
Property>::type
>::reference
get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
@@ -1737,7 +1745,7 @@
template <class Config, class Base, class Property, class Key>
inline
typename boost::property_traits<
- typename boost::property_map<typename Config::graph_type,
+ typename boost::property_map<typename Config::graph_type,
Property>::const_type
>::reference
get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
@@ -1746,7 +1754,7 @@
template <class Config, class Base, class Property, class Key,class Value>
inline void
- put(Property p, adj_list_helper<Config, Base>& g,
+ put(Property p, adj_list_helper<Config, Base>& g,
const Key& key, const Value& value)
{
typedef typename Config::graph_type Graph;
@@ -1786,7 +1794,7 @@
{
return 0;
}
-
+
inline adj_list_impl() { }
inline adj_list_impl(const adj_list_impl& x) {
@@ -1855,7 +1863,7 @@
inline StoredVertexList& vertex_set() { return m_vertices; }
inline const StoredVertexList& vertex_set() const { return m_vertices; }
- inline void copy_impl(const adj_list_impl& x_)
+ inline void copy_impl(const adj_list_impl& x_)
{
const Derived& x = static_cast<const Derived&>(x_);
@@ -1876,9 +1884,9 @@
edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
edge_descriptor e;
- bool inserted;
+ bool inserted;
vertex_descriptor s = source(*ei,x), t = target(*ei,x);
- tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
+ tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
vertex_map[(stored_vertex*)t], *this);
*((edge_property_type*)e.m_eproperty)
= *((edge_property_type*)(*ei).m_eproperty);
@@ -1913,7 +1921,7 @@
{
typedef typename Config::vertex_descriptor vertex_descriptor;
Derived& g = static_cast<Derived&>(g_);
- if (optional<vertex_descriptor> v
+ if (optional<vertex_descriptor> v
= g.vertex_by_property(get_property_value(p, vertex_bundle)))
return *v;
@@ -1941,7 +1949,7 @@
// O(V)
template <class Derived, class Config, class Base>
inline typename Config::vertex_descriptor
- vertex(typename Config::vertices_size_type n,
+ vertex(typename Config::vertices_size_type n,
const adj_list_impl<Derived, Config, Base>& g_)
{
const Derived& g = static_cast<const Derived&>(g_);
@@ -1956,8 +1964,8 @@
namespace detail {
template <class Graph, class vertex_descriptor>
- inline void
- remove_vertex_dispatch(Graph& g, vertex_descriptor u,
+ inline void
+ remove_vertex_dispatch(Graph& g, vertex_descriptor u,
boost::directed_tag)
{
typedef typename Graph::edge_parallel_category edge_parallel_category;
@@ -1970,8 +1978,8 @@
}
template <class Graph, class vertex_descriptor>
- inline void
- remove_vertex_dispatch(Graph& g, vertex_descriptor u,
+ inline void
+ remove_vertex_dispatch(Graph& g, vertex_descriptor u,
boost::undirected_tag)
{
typedef typename Graph::global_edgelist_selector EdgeListS;
@@ -1981,7 +1989,7 @@
g.m_vertices.erase(g.m_vertices.begin() + u);
vertex_descriptor V = num_vertices(g);
for (vertex_descriptor v = 0; v < V; ++v)
- reindex_edge_list(g.out_edge_list(v), u,
+ reindex_edge_list(g.out_edge_list(v), u,
edge_parallel_category());
typedef typename Graph::EdgeContainer Container;
typedef typename Container::iterator Iter;
@@ -1994,8 +2002,8 @@
}
}
template <class Graph, class vertex_descriptor>
- inline void
- remove_vertex_dispatch(Graph& g, vertex_descriptor u,
+ inline void
+ remove_vertex_dispatch(Graph& g, vertex_descriptor u,
boost::bidirectional_tag)
{
typedef typename Graph::global_edgelist_selector EdgeListS;
@@ -2007,10 +2015,10 @@
vertex_descriptor v;
if (u != V) {
for (v = 0; v < V; ++v)
- reindex_edge_list(g.out_edge_list(v), u,
+ reindex_edge_list(g.out_edge_list(v), u,
edge_parallel_category());
for (v = 0; v < V; ++v)
- reindex_edge_list(in_edge_list(g, v), u,
+ reindex_edge_list(in_edge_list(g, v), u,
edge_parallel_category());
typedef typename Graph::EdgeContainer Container;
@@ -2027,7 +2035,7 @@
template <class EdgeList, class vertex_descriptor>
inline void
- reindex_edge_list(EdgeList& el, vertex_descriptor u,
+ reindex_edge_list(EdgeList& el, vertex_descriptor u,
boost::allow_parallel_edge_tag)
{
typename EdgeList::iterator ei = el.begin(), e_end = el.end();
@@ -2037,7 +2045,7 @@
}
template <class EdgeList, class vertex_descriptor>
inline void
- reindex_edge_list(EdgeList& el, vertex_descriptor u,
+ reindex_edge_list(EdgeList& el, vertex_descriptor u,
boost::disallow_parallel_edge_tag)
{
typename EdgeList::iterator ei = el.begin(), e_end = el.end();
@@ -2054,14 +2062,14 @@
} // namespace detail
struct vec_adj_list_tag { };
-
+
template <class Graph, class Config, class Base>
class vec_adj_list_impl
: public adj_list_helper<Config, Base>
{
typedef typename Config::OutEdgeList OutEdgeList;
typedef typename Config::InEdgeList InEdgeList;
- typedef typename Config::StoredVertexList StoredVertexList;
+ typedef typename Config::StoredVertexList StoredVertexList;
public:
typedef typename Config::vertex_descriptor vertex_descriptor;
typedef typename Config::edge_descriptor edge_descriptor;
@@ -2081,7 +2089,7 @@
{
return (std::numeric_limits<vertex_descriptor>::max)();
}
-
+
inline vec_adj_list_impl() { }
inline vec_adj_list_impl(const vec_adj_list_impl& x) {
@@ -2106,7 +2114,7 @@
: m_vertices(num_vertices)
{
while (first != last) {
- add_edge((*first).first, (*first).second,
+ add_edge((*first).first, (*first).second,
static_cast<Graph&>(*this));
++first;
}
@@ -2118,7 +2126,7 @@
: m_vertices(num_vertices)
{
while (first != last) {
- add_edge((*first).first, (*first).second, *ep_iter,
+ add_edge((*first).first, (*first).second, *ep_iter,
static_cast<Graph&>(*this));
++first;
++ep_iter;
@@ -2135,7 +2143,7 @@
inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
return m_vertices[v].m_out_edges;
}
- inline void copy_impl(const vec_adj_list_impl& x_)
+ inline void copy_impl(const vec_adj_list_impl& x_)
{
const Graph& x = static_cast<const Graph&>(x_);
// Copy the stored vertex objects by adding each vertex
@@ -2149,7 +2157,7 @@
edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
edge_descriptor e;
- bool inserted;
+ bool inserted;
tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
*((edge_property_type*)e.m_eproperty)
= *((edge_property_type*)(*ei).m_eproperty);
@@ -2161,14 +2169,14 @@
// Had to make these non-members to avoid accidental instantiation
// on SGI MIPSpro C++
template <class G, class C, class B>
- inline typename C::InEdgeList&
- in_edge_list(vec_adj_list_impl<G,C,B>& g,
+ inline typename C::InEdgeList&
+ in_edge_list(vec_adj_list_impl<G,C,B>& g,
typename C::vertex_descriptor v) {
return g.m_vertices[v].m_in_edges;
}
template <class G, class C, class B>
- inline const typename C::InEdgeList&
- in_edge_list(const vec_adj_list_impl<G,C,B>& g,
+ inline const typename C::InEdgeList&
+ in_edge_list(const vec_adj_list_impl<G,C,B>& g,
typename C::vertex_descriptor v) {
return g.m_vertices[v].m_in_edges;
}
@@ -2189,7 +2197,7 @@
vec_adj_list_impl<Graph, Config, Base>& g_) {
typedef typename Config::vertex_descriptor vertex_descriptor;
Graph& g = static_cast<Graph&>(g_);
- if (optional<vertex_descriptor> v
+ if (optional<vertex_descriptor> v
= g.vertex_by_property(get_property_value(p, vertex_bundle)))
return *v;
typedef typename Config::stored_vertex stored_vertex;
@@ -2203,7 +2211,7 @@
// either u or v is greater than the number of vertices.
template <class Graph, class Config, class Base>
inline std::pair<typename Config::edge_descriptor, bool>
- add_edge(typename Config::vertex_descriptor u,
+ add_edge(typename Config::vertex_descriptor u,
typename Config::vertex_descriptor v,
const typename Config::edge_property_type& p,
vec_adj_list_impl<Graph, Config, Base>& g_)
@@ -2217,7 +2225,7 @@
}
template <class Graph, class Config, class Base>
inline std::pair<typename Config::edge_descriptor, bool>
- add_edge(typename Config::vertex_descriptor u,
+ add_edge(typename Config::vertex_descriptor u,
typename Config::vertex_descriptor v,
vec_adj_list_impl<Graph, Config, Base>& g_)
{
@@ -2238,8 +2246,8 @@
}
// O(1)
template <class Graph, class Config, class Base>
- inline typename Config::vertex_descriptor
- vertex(typename Config::vertices_size_type n,
+ inline typename Config::vertex_descriptor
+ vertex(typename Config::vertices_size_type n,
const vec_adj_list_impl<Graph, Config, Base>&)
{
return n;
@@ -2252,13 +2260,13 @@
// Adjacency List Generator
template <class Graph, class VertexListS, class OutEdgeListS,
- class DirectedS, class VertexProperty, class EdgeProperty,
+ class DirectedS, class VertexProperty, class EdgeProperty,
class GraphProperty, class EdgeListS>
struct adj_list_gen
{
- typedef typename detail::is_random_access<VertexListS>::type
+ typedef typename detail::is_random_access<VertexListS>::type
is_rand_access;
- typedef typename has_property<EdgeProperty>::type has_edge_property;
+ typedef typename has_property<EdgeProperty>::type has_edge_property;
typedef typename DirectedS::is_directed_t DirectedT;
typedef typename DirectedS::is_bidir_t BidirectionalT;
@@ -2273,7 +2281,7 @@
typedef GraphProperty graph_property_type;
typedef std::size_t vertices_size_type;
- typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
+ typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
Traits;
typedef typename Traits::directed_category directed_category;
@@ -2281,13 +2289,13 @@
typedef typename Traits::vertex_descriptor vertex_descriptor;
typedef typename Traits::edge_descriptor edge_descriptor;
- typedef void* vertex_ptr;
+ typedef void* vertex_ptr;
// need to reorganize this to avoid instantiating stuff
// that doesn't get used -JGS
// VertexList and vertex_iterator
- typedef typename container_gen<VertexListS,
+ typedef typename container_gen<VertexListS,
vertex_ptr>::type SeqVertexList;
typedef boost::integer_range<std::size_t> RandVertexList;
typedef typename mpl::if_<is_rand_access,
@@ -2297,10 +2305,10 @@
// EdgeContainer and StoredEdge
- typedef typename container_gen<EdgeListS,
+ typedef typename container_gen<EdgeListS,
list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
- typedef typename mpl::and_<DirectedT,
+ typedef typename mpl::and_<DirectedT,
typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
typedef typename mpl::if_<on_edge_storage,
@@ -2321,7 +2329,7 @@
// Adjacency Types
- typedef typename container_gen<OutEdgeListS, StoredEdge>::type
+ typedef typename container_gen<OutEdgeListS, StoredEdge>::type
OutEdgeList;
typedef typename OutEdgeList::size_type degree_size_type;
typedef typename OutEdgeList::iterator OutEdgeIter;
@@ -2358,10 +2366,10 @@
typedef undirected_edge_iter<
EdgeIter
, edge_descriptor
- , EdgeIterDiff
+ , EdgeIterDiff
> UndirectedEdgeIter; // also used for bidirectional
- typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
+ typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
graph_type> DirectedEdgeIter;
typedef typename mpl::if_<on_edge_storage,
@@ -2637,16 +2645,16 @@
typedef typename Bind::const_type const_type;
};
} // namespace detail
-
+
//=========================================================================
// Edge Property Map
template <class Directed, class Value, class Ref, class Vertex,
class Property, class Tag>
struct adj_list_edge_property_map
- : public put_get_helper<
+ : public put_get_helper<
Ref,
- adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
+ adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
Tag>
>
{
@@ -2667,7 +2675,7 @@
class Vertex>
struct adj_list_edge_all_properties_map
: public put_get_helper<PropRef,
- adj_list_edge_all_properties_map<Directed, Property, PropRef,
+ adj_list_edge_all_properties_map<Directed, Property, PropRef,
PropPtr, Vertex>
>
{
@@ -2692,12 +2700,12 @@
typedef typename property_value<Property,Tag>::type value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
-
+
typedef adj_list_edge_property_map
- <typename Graph::directed_category, value_type, reference,
+ <typename Graph::directed_category, value_type, reference,
typename Graph::vertex_descriptor,Property,Tag> type;
typedef adj_list_edge_property_map
- <typename Graph::directed_category, value_type, const_reference,
+ <typename Graph::directed_category, value_type, const_reference,
typename Graph::vertex_descriptor,const Property, Tag> const_type;
};
};
@@ -2708,7 +2716,7 @@
<typename Graph::directed_category, Property, Property&, Property*,
typename Graph::vertex_descriptor> type;
typedef adj_list_edge_all_properties_map
- <typename Graph::directed_category, Property, const Property&,
+ <typename Graph::directed_category, Property, const Property&,
const Property*, typename Graph::vertex_descriptor> const_type;
};
};
@@ -2738,11 +2746,11 @@
};
} // namespace detail
- template <>
+ template <>
struct edge_property_selector<adj_list_tag> {
typedef detail::adj_list_edge_property_selector type;
};
- template <>
+ template <>
struct edge_property_selector<vec_adj_list_tag> {
typedef detail::adj_list_edge_property_selector type;
};
@@ -2757,7 +2765,7 @@
typedef typename Choice::const_type const_type;
};
};
- template <>
+ template <>
struct vertex_property_selector<adj_list_tag> {
typedef adj_list_vertex_property_selector type;
};
@@ -2770,7 +2778,7 @@
typedef typename Choice::const_type const_type;
};
};
- template <>
+ template <>
struct vertex_property_selector<vec_adj_list_tag> {
typedef vec_adj_list_vertex_property_selector type;
};
@@ -2792,7 +2800,7 @@
#endif
template <typename V>
- struct hash< boost::detail::stored_edge<V> >
+ struct hash< boost::detail::stored_edge<V> >
{
std::size_t
operator()(const boost::detail::stored_edge<V>& e) const
@@ -2802,7 +2810,7 @@
};
template <typename V, typename P>
- struct hash< boost::detail::stored_edge_property <V,P> >
+ struct hash< boost::detail::stored_edge_property <V,P> >
{
std::size_t
operator()(const boost::detail::stored_edge_property<V,P>& e) const
@@ -2812,7 +2820,7 @@
};
template <typename V, typename I, typename P>
- struct hash< boost::detail::stored_edge_iter<V,I, P> >
+ struct hash< boost::detail::stored_edge_iter<V,I, P> >
{
std::size_t
operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
@@ -2838,17 +2846,17 @@
/*
Implementation Notes:
-
+
Many of the public interface functions in this file would have been
more conveniently implemented as inline friend functions.
However there are a few compiler bugs that make that approach
non-portable.
-
+
1. g++ inline friend in namespace bug
2. g++ using clause doesn't work with inline friends
3. VC++ doesn't have Koenig lookup
- For these reasons, the functions were all written as non-inline free
+ For these reasons, the functions were all written as non-inline free
functions, and static cast was used to convert from the helper
class to the adjacency_list derived class.
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2008-12-08 14:03:20 EST (Mon, 08 Dec 2008)
@@ -29,6 +29,7 @@
# unit-test adj_list_test : adj_list_test.cpp ;
[ run adj_list_edge_list_set.cpp ]
+ [ run adj_list_loops.cpp ]
[ compile adj_matrix_cc.cpp ]
[ run bfs.cpp ../../test/build//boost_test_exec_monitor ]
[ compile bfs_cc.cpp ]
Added: trunk/libs/graph/test/adj_list_loops.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/adj_list_loops.cpp 2008-12-08 14:03:20 EST (Mon, 08 Dec 2008)
@@ -0,0 +1,119 @@
+
+#if __GNUC__ == 4 && __GNUC_MINOR__ >= 3
+# define BOOST_NO_HASH
+#endif
+
+#include "typestr.hpp"
+
+#include <iostream>
+
+#include <boost/assert.hpp>
+#include <boost/graph/adjacency_list.hpp>
+
+using namespace boost;
+
+// TODO: Integrate this into a larger adj_list test suite.
+
+template <typename Graph>
+void test_graph_nonloop()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ // Build a graph with 1 edge and turn it into a loop.
+ Graph g(5);
+ Vertex u = *vertices(g).first;
+ Vertex v = *next(vertices(g).first, 2);
+ add_edge(u, v, g);
+ BOOST_ASSERT(num_vertices(g) == 5);
+ BOOST_ASSERT(num_edges(g) == 1);
+ remove_edge(u, v, g);
+ BOOST_ASSERT(num_edges(g) == 0);
+
+}
+
+
+template <typename Graph>
+void test_multigraph_nonloop()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ // Build a graph with 1 edge and turn it into a loop.
+ Graph g(5);
+ Vertex u = *vertices(g).first;
+ Vertex v = *next(vertices(g).first, 2);
+ add_edge(u, v, g);
+ add_edge(u, v, g);
+ BOOST_ASSERT(num_vertices(g) == 5);
+ BOOST_ASSERT(num_edges(g) == 2);
+ remove_edge(u, v, g);
+ BOOST_ASSERT(num_edges(g) == 0);
+
+}
+
+template <typename Graph>
+void test_graph_loop()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ Graph g(5);
+ Vertex v = *next(vertices(g).first, 2);
+ add_edge(v, v, g);
+ BOOST_ASSERT(num_vertices(g) == 5);
+ BOOST_ASSERT(num_edges(g) == 1);
+ remove_edge(v, v, g);
+ BOOST_ASSERT(num_edges(g) == 0);
+}
+
+template <typename Graph>
+void test_multigraph_loop()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ Graph g(5);
+ Vertex v = *next(vertices(g).first, 2);
+ add_edge(v, v, g);
+ add_edge(v, v, g);
+ BOOST_ASSERT(num_vertices(g) == 5);
+ BOOST_ASSERT(num_edges(g) == 2);
+ remove_edge(v, v, g);
+ BOOST_ASSERT(num_edges(g) == 0);
+}
+
+template <typename Kind>
+void test()
+{
+ typedef no_property na;
+ typedef adjacency_list<vecS, vecS, Kind, na, na, na, listS> VVL;
+ typedef adjacency_list<listS, vecS, Kind, na, na, na, listS> LVL;
+ typedef adjacency_list<setS, vecS, Kind, na, na, na, listS> SVL;
+ typedef adjacency_list<multisetS, vecS, Kind, na, na, na, listS> MVL;
+
+ test_graph_nonloop<VVL>();
+ test_graph_nonloop<LVL>();
+ test_graph_nonloop<SVL>();
+ test_graph_nonloop<MVL>();
+ test_multigraph_nonloop<VVL>();
+ test_multigraph_nonloop<LVL>();
+ test_multigraph_nonloop<MVL>();
+ test_graph_loop<VVL>();
+ test_graph_loop<LVL>();
+ test_graph_loop<SVL>();
+ test_graph_loop<MVL>();
+ test_multigraph_loop<VVL>();
+ test_multigraph_loop<LVL>();
+ test_multigraph_loop<MVL>();
+}
+
+
+int main()
+{
+ test<undirectedS>();
+ test<directedS>();
+ test<bidirectionalS>();
+
+ 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