|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50191 - in trunk: boost/graph libs/graph/test
From: asutton_at_[hidden]
Date: 2008-12-08 10:22:32
Author: asutton
Date: 2008-12-08 10:22:32 EST (Mon, 08 Dec 2008)
New Revision: 50191
URL: http://svn.boost.org/trac/boost/changeset/50191
Log:
Fixing #2550. Added a check for this condition in the test files.
Text files modified:
trunk/boost/graph/adjacency_matrix.hpp | 223 ++++++++++++++++++++-------------------
trunk/libs/graph/test/adjacency_matrix_test.cpp | 61 +++++++---
2 files changed, 155 insertions(+), 129 deletions(-)
Modified: trunk/boost/graph/adjacency_matrix.hpp
==============================================================================
--- trunk/boost/graph/adjacency_matrix.hpp (original)
+++ trunk/boost/graph/adjacency_matrix.hpp 2008-12-08 10:22:32 EST (Mon, 08 Dec 2008)
@@ -31,7 +31,7 @@
#include <boost/type_traits/ice.hpp>
namespace boost {
-
+
namespace detail {
template <class Directed, class Vertex>
@@ -40,7 +40,7 @@
typedef edge_desc_impl<Directed,Vertex> Base;
public:
matrix_edge_desc_impl() { }
- matrix_edge_desc_impl(bool exists, Vertex s, Vertex d,
+ matrix_edge_desc_impl(bool exists, Vertex s, Vertex d,
const void* ep = 0)
: Base(s, d, ep), m_exists(exists) { }
bool exists() const { return m_exists; }
@@ -53,13 +53,15 @@
bool operator()(const Edge& e) const { return e.exists(); }
};
+ // Note to self... The int for get_edge_exists and set_edge exist helps
+ // make these calls unambiguous.
template <typename EdgeProperty>
bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {
return stored_edge.first;
}
template <typename EdgeProperty>
void set_edge_exists(
- std::pair<bool, EdgeProperty>& stored_edge,
+ std::pair<bool, EdgeProperty>& stored_edge,
bool flag,
int
) {
@@ -91,7 +93,7 @@
template <typename StoredEdgeProperty, typename EdgeProperty>
inline void
- set_property(std::pair<bool, StoredEdgeProperty>& stored_edge,
+ set_property(std::pair<bool, StoredEdgeProperty>& stored_edge,
const EdgeProperty& ep, int) {
stored_edge.second = ep;
}
@@ -107,7 +109,7 @@
template <typename EdgeProxy, typename EdgeProperty>
inline void
set_property(EdgeProxy, const EdgeProperty&, ...) {}
-
+
//=======================================================================
// Directed Out Edge Iterator
@@ -133,9 +135,9 @@
, EdgeDescriptor
, std::ptrdiff_t
> super_t;
-
+
dir_adj_matrix_out_edge_iter() { }
-
+
dir_adj_matrix_out_edge_iter(
const MatrixIter& i
, const VertexDescriptor& src
@@ -148,11 +150,11 @@
++this->base_reference();
++m_targ;
}
-
+
inline EdgeDescriptor
- dereference() const
+ dereference() const
{
- return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
+ return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
&get_property(*this->base()));
}
VertexDescriptor m_src, m_targ;
@@ -184,9 +186,9 @@
, EdgeDescriptor
, std::ptrdiff_t
> super_t;
-
+
dir_adj_matrix_in_edge_iter() { }
-
+
dir_adj_matrix_in_edge_iter(
const MatrixIter& i
, const MatrixIter& last
@@ -204,11 +206,11 @@
this->base_reference() = m_last;
}
}
-
+
inline EdgeDescriptor
- dereference() const
+ dereference() const
{
- return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
+ return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
&get_property(*this->base()));
}
MatrixIter m_last;
@@ -223,7 +225,7 @@
typename VertexDescriptor, typename MatrixIter
, typename VerticesSizeType, typename EdgeDescriptor
>
- struct undir_adj_matrix_out_edge_iter
+ struct undir_adj_matrix_out_edge_iter
: iterator_adaptor<
undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
, MatrixIter
@@ -241,9 +243,9 @@
, EdgeDescriptor
, std::ptrdiff_t
> super_t;
-
+
undir_adj_matrix_out_edge_iter() { }
-
+
undir_adj_matrix_out_edge_iter(
const MatrixIter& i
, const VertexDescriptor& src
@@ -269,16 +271,16 @@
}
++m_targ;
}
-
+
inline EdgeDescriptor
- dereference() const
+ dereference() const
{
return EdgeDescriptor(
get_edge_exists(*this->base(), 0), m_src, m_targ
, &get_property(*this->base())
);
}
-
+
VertexDescriptor m_src, m_inc, m_targ;
VerticesSizeType m_n;
};
@@ -290,7 +292,7 @@
typename VertexDescriptor, typename MatrixIter
, typename VerticesSizeType, typename EdgeDescriptor
>
- struct undir_adj_matrix_in_edge_iter
+ struct undir_adj_matrix_in_edge_iter
: iterator_adaptor<
undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
, MatrixIter
@@ -308,9 +310,9 @@
, EdgeDescriptor
, std::ptrdiff_t
> super_t;
-
+
undir_adj_matrix_in_edge_iter() { }
-
+
undir_adj_matrix_in_edge_iter(
const MatrixIter& i
, const VertexDescriptor& src
@@ -336,16 +338,16 @@
}
++m_targ;
}
-
+
inline EdgeDescriptor
- dereference() const
+ dereference() const
{
return EdgeDescriptor(
get_edge_exists(*this->base(), 0), m_targ, m_src
, &get_property(*this->base())
);
}
-
+
VertexDescriptor m_src, m_inc, m_targ;
VerticesSizeType m_n;
};
@@ -353,7 +355,7 @@
//=======================================================================
// Edge Iterator
- template <typename Directed, typename MatrixIter,
+ template <typename Directed, typename MatrixIter,
typename VerticesSizeType, typename EdgeDescriptor>
struct adj_matrix_edge_iter
: iterator_adaptor<
@@ -373,17 +375,17 @@
, EdgeDescriptor
, std::ptrdiff_t
> super_t;
-
+
adj_matrix_edge_iter() { }
-
- adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n)
+
+ adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n)
: super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }
void increment()
{
increment_dispatch(this->base_reference(), Directed());
}
-
+
void increment_dispatch(MatrixIter& i, directedS)
{
++i;
@@ -397,7 +399,7 @@
++m_targ;
}
}
-
+
void increment_dispatch(MatrixIter& i, undirectedS)
{
++i;
@@ -413,14 +415,14 @@
}
inline EdgeDescriptor
- dereference() const
+ dereference() const
{
return EdgeDescriptor(
get_edge_exists(
*this->base(), 0), m_src, m_targ, &get_property(*this->base())
);
}
-
+
MatrixIter m_start;
VerticesSizeType m_src, m_targ, m_n;
};
@@ -444,9 +446,9 @@
typedef typename mpl::if_<is_directed,
bidirectional_tag, undirected_tag>::type
directed_category;
-
+
typedef disallow_parallel_edge_tag edge_parallel_category;
-
+
typedef std::size_t vertex_descriptor;
typedef detail::matrix_edge_desc_impl<directed_category,
@@ -461,7 +463,7 @@
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag,
public virtual edge_list_graph_tag { };
-
+
//=========================================================================
// Adjacency Matrix Class
template <typename Directed = directedS,
@@ -472,7 +474,7 @@
class adjacency_matrix {
typedef adjacency_matrix self;
typedef adjacency_matrix_traits<Directed> Traits;
-
+
public:
#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
// The bidirectionalS tag is not allowed with the adjacency_matrix
@@ -487,14 +489,14 @@
vertex_property_type;
typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type
edge_property_type;
-
+
private:
typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged
maybe_vertex_bundled;
typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged
maybe_edge_bundled;
-
+
public:
// The types that are actually bundled
typedef typename mpl::if_c<(is_same<maybe_vertex_bundled, no_property>::value),
@@ -534,7 +536,7 @@
{
return (std::numeric_limits<vertex_descriptor>::max)();
}
-
+
//private: if friends worked, these would be private
typedef detail::dir_adj_matrix_out_edge_iter<
@@ -560,11 +562,11 @@
typedef typename mpl::if_<
typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter
>::type unfiltered_in_edge_iter;
-
+
typedef detail::adj_matrix_edge_iter<
Directed, MatrixIter, size_type, edge_descriptor
> unfiltered_edge_iter;
-
+
public:
// IncidenceGraph concept required types
@@ -596,8 +598,8 @@
typedef adjacency_matrix_class_tag graph_tag;
// Constructor required by MutableGraph
- adjacency_matrix(vertices_size_type n_vertices)
- : m_matrix(Directed::is_directed ?
+ adjacency_matrix(vertices_size_type n_vertices)
+ : m_matrix(Directed::is_directed ?
(n_vertices * n_vertices)
: (n_vertices * (n_vertices + 1) / 2)),
m_vertex_set(0, n_vertices),
@@ -618,7 +620,7 @@
const edge_bundled& operator[](edge_descriptor e) const
{ return get(edge_bundle, *this)[e]; }
#endif
-
+
//private: if friends worked, these would be private
typename Matrix::const_reference
@@ -647,9 +649,9 @@
std::vector<vertex_property_type> m_vertex_properties;
size_type m_num_edges;
};
-
+
//=========================================================================
- // Functions required by the AdjacencyMatrix concept
+ // Functions required by the AdjacencyMatrix concept
template <typename D, typename VP, typename EP, typename GP, typename A>
std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
@@ -665,7 +667,7 @@
}
//=========================================================================
- // Functions required by the IncidenceGraph concept
+ // Functions required by the IncidenceGraph concept
// O(1)
template <typename VP, typename EP, typename GP, typename A>
@@ -685,7 +687,7 @@
, last(l, u, g.m_vertex_set.size());
detail::does_edge_exist pred;
typedef typename Graph::out_edge_iterator out_edge_iterator;
- return std::make_pair(out_edge_iterator(pred, first, last),
+ return std::make_pair(out_edge_iterator(pred, first, last),
out_edge_iterator(pred, last, last));
}
@@ -707,15 +709,15 @@
typename Graph::unfiltered_out_edge_iter
first(f, u, g.m_vertex_set.size())
, last(l, u, g.m_vertex_set.size());
-
+
detail::does_edge_exist pred;
typedef typename Graph::out_edge_iterator out_edge_iterator;
- return std::make_pair(out_edge_iterator(pred, first, last),
+ return std::make_pair(out_edge_iterator(pred, first, last),
out_edge_iterator(pred, last, last));
}
-
+
// O(N)
- template <typename D, typename VP, typename EP, typename GP, typename A>
+ template <typename D, typename VP, typename EP, typename GP, typename A>
typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
const adjacency_matrix<D,VP,EP,GP,A>& g)
@@ -729,7 +731,7 @@
// O(1)
template <typename D, typename VP, typename EP, typename GP, typename A,
- typename Dir, typename Vertex>
+ typename Dir, typename Vertex>
typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
const adjacency_matrix<D,VP,EP,GP,A>&)
@@ -739,7 +741,7 @@
// O(1)
template <typename D, typename VP, typename EP, typename GP, typename A,
- typename Dir, typename Vertex>
+ typename Dir, typename Vertex>
typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
const adjacency_matrix<D,VP,EP,GP,A>&)
@@ -748,7 +750,7 @@
}
//=========================================================================
- // Functions required by the BidirectionalGraph concept
+ // Functions required by the BidirectionalGraph concept
// O(1)
template <typename VP, typename EP, typename GP, typename A>
@@ -767,7 +769,7 @@
, last(l, l, u, g.m_vertex_set.size());
detail::does_edge_exist pred;
typedef typename Graph::in_edge_iterator in_edge_iterator;
- return std::make_pair(in_edge_iterator(pred, first, last),
+ return std::make_pair(in_edge_iterator(pred, first, last),
in_edge_iterator(pred, last, last));
}
@@ -789,15 +791,15 @@
typename Graph::unfiltered_in_edge_iter
first(f, u, g.m_vertex_set.size())
, last(l, u, g.m_vertex_set.size());
-
+
detail::does_edge_exist pred;
typedef typename Graph::in_edge_iterator in_edge_iterator;
- return std::make_pair(in_edge_iterator(pred, first, last),
+ return std::make_pair(in_edge_iterator(pred, first, last),
in_edge_iterator(pred, last, last));
}
-
+
// O(N)
- template <typename D, typename VP, typename EP, typename GP, typename A>
+ template <typename D, typename VP, typename EP, typename GP, typename A>
typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
const adjacency_matrix<D,VP,EP,GP,A>& g)
@@ -810,7 +812,7 @@
}
//=========================================================================
- // Functions required by the AdjacencyGraph concept
+ // Functions required by the AdjacencyGraph concept
template <typename D, typename VP, typename EP, typename GP, typename A>
std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,
@@ -830,7 +832,7 @@
}
//=========================================================================
- // Functions required by the VertexListGraph concept
+ // Functions required by the VertexListGraph concept
template <typename D, typename VP, typename EP, typename GP, typename A>
std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,
@@ -846,10 +848,10 @@
num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {
return g.m_vertex_set.size();
}
-
+
//=========================================================================
- // Functions required by the EdgeListGraph concept
-
+ // Functions required by the EdgeListGraph concept
+
template <typename D, typename VP, typename EP, typename GP, typename A>
std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,
typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>
@@ -857,11 +859,11 @@
{
typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
Graph& g = const_cast<Graph&>(g_);
-
+
typename Graph::unfiltered_edge_iter
- first(g.m_matrix.begin(), g.m_matrix.begin(),
+ first(g.m_matrix.begin(), g.m_matrix.begin(),
g.m_vertex_set.size()),
- last(g.m_matrix.end(), g.m_matrix.begin(),
+ last(g.m_matrix.end(), g.m_matrix.begin(),
g.m_vertex_set.size());
detail::does_edge_exist pred;
typedef typename Graph::edge_iterator edge_iterator;
@@ -876,9 +878,9 @@
{
return g.m_num_edges;
}
-
+
//=========================================================================
- // Functions required by the MutableGraph concept
+ // Functions required by the MutableGraph concept
// O(1)
template <typename D, typename VP, typename EP, typename GP, typename A>
@@ -888,14 +890,14 @@
const EP& ep,
adjacency_matrix<D,VP,EP,GP,A>& g)
{
- typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
+ typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
edge_descriptor;
if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
++(g.m_num_edges);
detail::set_property(g.get_edge(u,v), ep, 0);
detail::set_edge_exists(g.get_edge(u,v), true, 0);
return std::make_pair
- (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
+ (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
true);
} else
return std::make_pair
@@ -913,15 +915,18 @@
return add_edge(u, v, ep, g);
}
- // O(1)
+ // O(1)
template <typename D, typename VP, typename EP, typename GP, typename A>
void
remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
adjacency_matrix<D,VP,EP,GP,A>& g)
{
- --(g.m_num_edges);
- detail::set_edge_exists(g.get_edge(u,v), false, 0);
+ // Don'remove the edge unless it already exists.
+ if(detail::get_edge_exists(g.get_edge(u,v), 0)) {
+ --(g.m_num_edges);
+ detail::set_edge_exists(g.get_edge(u,v), false, 0);
+ }
}
// O(1)
@@ -933,7 +938,7 @@
remove_edge(source(e, g), target(e, g), g);
}
-
+
template <typename D, typename VP, typename EP, typename GP, typename A>
inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
@@ -966,7 +971,7 @@
(typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
adjacency_matrix<directedS,VP,EP,GP,A>& g)
{
- typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator
+ typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator
vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
remove_edge(u, *vi, g);
@@ -989,10 +994,10 @@
//=========================================================================
// Vertex Property Map
-
- template <typename GraphPtr, typename Vertex, typename T, typename R,
- typename Tag>
- class adj_matrix_vertex_property_map
+
+ template <typename GraphPtr, typename Vertex, typename T, typename R,
+ typename Tag>
+ class adj_matrix_vertex_property_map
: public put_get_helper<R,
adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >
{
@@ -1031,10 +1036,10 @@
struct bind_ {
typedef typename property_value<Property,Tag>::type Value;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
-
+
typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,
Tag> type;
- typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value,
+ typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value,
const Value&, Tag> const_type;
};
};
@@ -1079,14 +1084,14 @@
struct vertex_property_selector<adjacency_matrix_class_tag> {
typedef detail::adj_matrix_vertex_property_selector type;
};
-
+
//=========================================================================
// Edge Property Map
- template <typename Directed, typename Property, typename Vertex,
- typename T, typename R, typename Tag>
- class adj_matrix_edge_property_map
+ template <typename Directed, typename Property, typename Vertex,
+ typename T, typename R, typename Tag>
+ class adj_matrix_edge_property_map
: public put_get_helper<R,
adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >
{
@@ -1121,56 +1126,56 @@
namespace detail {
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A>
- typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::type
get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,
vertex_property_tag)
{
typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
- typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::type PA;
return PA(&g);
}
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A>
- typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::type
get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property,
edge_property_tag)
{
- typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::type PA;
return PA();
}
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A>
- typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::const_type
get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property,
vertex_property_tag)
{
typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
- typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::const_type PA;
return PA(&g);
}
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A>
- typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::const_type
get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property,
edge_property_tag)
{
- typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
+ typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
Property>::const_type PA;
return PA();
}
} // namespace detail
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A>
inline
typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type
@@ -1180,7 +1185,7 @@
return detail::get_dispatch(g, p, Kind());
}
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A>
inline
typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
@@ -1190,7 +1195,7 @@
return detail::get_dispatch(g, p, Kind());
}
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A, typename Key>
inline
typename property_traits<
@@ -1202,7 +1207,7 @@
return get(get(p, g), key);
}
- template <typename Property, typename D, typename VP, typename EP,
+ template <typename Property, typename D, typename VP, typename EP,
typename GP, typename A, typename Key, typename Value>
inline void
put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g,
@@ -1213,11 +1218,11 @@
Map pmap = get(p, g);
put(pmap, key, value);
}
-
+
//=========================================================================
// Other Functions
- template <typename D, typename VP, typename EP, typename GP, typename A>
+ template <typename D, typename VP, typename EP, typename GP, typename A>
typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,
const adjacency_matrix<D,VP,EP,GP,A>& g)
@@ -1252,7 +1257,7 @@
result_type;
return result_type(&g, p);
}
-
+
template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
typename Allocator, typename T, typename Bundle, typename Key>
inline T
Modified: trunk/libs/graph/test/adjacency_matrix_test.cpp
==============================================================================
--- trunk/libs/graph/test/adjacency_matrix_test.cpp (original)
+++ trunk/libs/graph/test/adjacency_matrix_test.cpp 2008-12-08 10:22:32 EST (Mon, 08 Dec 2008)
@@ -53,9 +53,7 @@
Graph1 g1(24);
Graph2 g2(24);
- boost::add_edge(boost::vertex(0, g1), boost::vertex(7, g1), g1);
- boost::add_edge(boost::vertex(0, g2), boost::vertex(7, g2), g2);
- boost::add_edge(boost::vertex(1, g1), boost::vertex(2, g1), g1);
+boost::add_edge(boost::vertex(1, g1), boost::vertex(2, g1), g1);
boost::add_edge(boost::vertex(1, g2), boost::vertex(2, g2), g2);
boost::add_edge(boost::vertex(2, g1), boost::vertex(10, g1), g1);
boost::add_edge(boost::vertex(2, g2), boost::vertex(10, g2), g2);
@@ -171,7 +169,7 @@
{
BOOST_CHECK(boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2));
- for (boost::tie(ei1, eend1) = boost::out_edges(*vi1, g1),
+ for (boost::tie(ei1, eend1) = boost::out_edges(*vi1, g1),
boost::tie(ei2, eend2) = boost::out_edges(*vi2, g2);
ei1 != eend1;
++ei1, ++ei2)
@@ -188,7 +186,7 @@
{
BOOST_CHECK(boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2));
- for (boost::tie(iei1, ieend1) = boost::in_edges(*vi1, g1),
+ for (boost::tie(iei1, ieend1) = boost::in_edges(*vi1, g1),
boost::tie(iei2, ieend2) = boost::in_edges(*vi2, g2);
iei1 != ieend1;
++iei1, ++iei2)
@@ -198,23 +196,46 @@
}
}
+template <typename Graph>
+void test_remove_edges()
+{
+ using namespace boost;
+
+ // Build a 2-vertex graph
+ Graph g(2);
+ add_edge(vertex(0, g), vertex(1, g), g);
+ BOOST_CHECK(num_vertices(g) == 2);
+ BOOST_CHECK(num_edges(g) == 1);
+ remove_edge(vertex(0, g), vertex(1, g), g);
+ BOOST_CHECK(num_edges(g) == 0);
+
+ // Make sure we don't decrement the edge count if the edge doesn't actually
+ // exist.
+ remove_edge(vertex(0, g), vertex(1, g), g);
+ BOOST_CHECK(num_edges(g) == 0);
+}
+
+
int test_main(int, char*[])
{
- // Use setS to keep out edges in order, so they match the adjacency_matrix.
- typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>
- UGraph1;
- typedef boost::adjacency_matrix<boost::undirectedS>
- UGraph2;
- run_test<UGraph1, UGraph2>();
-
- // Use setS to keep out edges in order, so they match the adjacency_matrix.
- typedef boost::adjacency_list<boost::setS, boost::vecS,
- boost::bidirectionalS>
- BGraph1;
- typedef boost::adjacency_matrix<boost::directedS>
- BGraph2;
- run_test<BGraph1, BGraph2>();
+ // Use setS to keep out edges in order, so they match the adjacency_matrix.
+ typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>
+ UGraph1;
+ typedef boost::adjacency_matrix<boost::undirectedS>
+ UGraph2;
+ run_test<UGraph1, UGraph2>();
+
+ // Use setS to keep out edges in order, so they match the adjacency_matrix.
+ typedef boost::adjacency_list<boost::setS, boost::vecS,
+ boost::bidirectionalS>
+ BGraph1;
+ typedef boost::adjacency_matrix<boost::directedS>
+ BGraph2;
+ run_test<BGraph1, BGraph2>();
+
+ test_remove_edges<UGraph2>();
+ test_remove_edges<BGraph2>();
- return 0;
+ 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