|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50330 - in branches/release: boost/graph boost/graph/detail libs/graph libs/graph/doc libs/graph/src libs/graph/test
From: asutton_at_[hidden]
Date: 2008-12-20 14:08:01
Author: asutton
Date: 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
New Revision: 50330
URL: http://svn.boost.org/trac/boost/changeset/50330
Log:
Selectively merging changes from 47269:HEAD. Changes herein fix or address
the following tickets: #1622 (r50206), #2550 (r50191), #416 (r50137),
#2460 (r49563), #2392 (r49254), #2209 (r49000), #1700 (r48611). Also adds
metric_tsp_approx algorithm.
Added:
branches/release/boost/graph/metric_tsp_approx.hpp
- copied unchanged from r49563, /trunk/boost/graph/metric_tsp_approx.hpp
branches/release/boost/graph/named_graph.hpp
- copied unchanged from r49179, /trunk/boost/graph/named_graph.hpp
branches/release/libs/graph/CMakeLists.txt
- copied unchanged from r50329, /trunk/libs/graph/CMakeLists.txt
branches/release/libs/graph/doc/TSPTourVisitor.html
- copied unchanged from r50329, /trunk/libs/graph/doc/TSPTourVisitor.html
branches/release/libs/graph/doc/metric_tsp_approx.html
- copied unchanged from r50329, /trunk/libs/graph/doc/metric_tsp_approx.html
branches/release/libs/graph/doc/tsp_tour_len_visitor.html
- copied unchanged from r50329, /trunk/libs/graph/doc/tsp_tour_len_visitor.html
branches/release/libs/graph/doc/tsp_tour_visitor.html
- copied unchanged from r50329, /trunk/libs/graph/doc/tsp_tour_visitor.html
branches/release/libs/graph/module.cmake
- copied unchanged from r50329, /trunk/libs/graph/module.cmake
branches/release/libs/graph/src/CMakeLists.txt
- copied unchanged from r50329, /trunk/libs/graph/src/CMakeLists.txt
branches/release/libs/graph/test/CMakeLists.txt
- copied unchanged from r50329, /trunk/libs/graph/test/CMakeLists.txt
branches/release/libs/graph/test/adj_list_invalidation.cpp
- copied unchanged from r50329, /trunk/libs/graph/test/adj_list_invalidation.cpp
branches/release/libs/graph/test/adj_list_loops.cpp
- copied unchanged from r50329, /trunk/libs/graph/test/adj_list_loops.cpp
branches/release/libs/graph/test/dimacs.cpp
- copied unchanged from r50329, /trunk/libs/graph/test/dimacs.cpp
branches/release/libs/graph/test/is_straight_line_draw_test.cpp
- copied unchanged from r50329, /trunk/libs/graph/test/is_straight_line_draw_test.cpp
branches/release/libs/graph/test/metric_tsp_approx.cpp
- copied unchanged from r50329, /trunk/libs/graph/test/metric_tsp_approx.cpp
branches/release/libs/graph/test/metric_tsp_approx.txt
- copied unchanged from r50329, /trunk/libs/graph/test/metric_tsp_approx.txt
branches/release/libs/graph/test/named_vertices_test.cpp
- copied unchanged from r50329, /trunk/libs/graph/test/named_vertices_test.cpp
Properties modified:
branches/release/libs/graph/doc/edmonds_karp_max_flow.html (props changed)
Text files modified:
branches/release/boost/graph/adjacency_list.hpp | 19 +
branches/release/boost/graph/adjacency_matrix.hpp | 223 +++++++++++----------
branches/release/boost/graph/chrobak_payne_drawing.hpp | 4
branches/release/boost/graph/detail/adjacency_list.hpp | 403 +++++++++++++++++++++------------------
branches/release/boost/graph/exception.hpp | 57 +++--
branches/release/boost/graph/fruchterman_reingold.hpp | 20
branches/release/boost/graph/graphml.hpp | 98 ++++----
branches/release/boost/graph/is_straight_line_drawing.hpp | 28 ++
branches/release/boost/graph/read_dimacs.hpp | 111 +++++-----
branches/release/boost/graph/reverse_graph.hpp | 39 +-
branches/release/libs/graph/doc/adjacency_list.html | 83 +++++---
branches/release/libs/graph/doc/known_problems.html | 26 +
branches/release/libs/graph/doc/table_of_contents.html | 108 +++++----
branches/release/libs/graph/test/Jamfile.v2 | 68 ++----
branches/release/libs/graph/test/adjacency_matrix_test.cpp | 61 ++++-
branches/release/libs/graph/test/graphml_test.cpp | 2
branches/release/libs/graph/test/graphml_test.xml | 2
17 files changed, 739 insertions(+), 613 deletions(-)
Modified: branches/release/boost/graph/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/adjacency_list.hpp (original)
+++ branches/release/boost/graph/adjacency_list.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -17,6 +17,9 @@
#include <list>
#include <set>
+// TODO: Deprecating this requires some cooperation from Boost.Config. It's not
+// a good idea to just refuse the inclusion because it could break otherwise
+// functioning code.
#if !defined BOOST_NO_HASH
# ifdef BOOST_HASH_SET_HEADER
# include BOOST_HASH_SET_HEADER
@@ -44,6 +47,7 @@
#include <boost/type_traits/is_same.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/graph/named_graph.hpp>
namespace boost {
@@ -333,7 +337,14 @@
#else
VertexProperty, EdgeProperty,
#endif
- GraphProperty, EdgeListS>::type
+ GraphProperty, EdgeListS>::type,
+ // Support for named vertices
+ public graph::maybe_named_graph<
+ adjacency_list<OutEdgeListS,VertexListS,DirectedS,
+ VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
+ typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS,
+ EdgeListS>::vertex_descriptor,
+ VertexProperty>
{
#if !defined(BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
typedef typename detail::retag_property_list<vertex_bundle_t,
@@ -434,6 +445,12 @@
*this = tmp;
}
+ void clear()
+ {
+ this->clearing_graph();
+ Base::clear();
+ }
+
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
// Directly access a vertex or edge bundle
vertex_bundled& operator[](vertex_descriptor v)
Modified: branches/release/boost/graph/adjacency_matrix.hpp
==============================================================================
--- branches/release/boost/graph/adjacency_matrix.hpp (original)
+++ branches/release/boost/graph/adjacency_matrix.hpp 2008-12-20 14:07:58 EST (Sat, 20 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: branches/release/boost/graph/chrobak_payne_drawing.hpp
==============================================================================
--- branches/release/boost/graph/chrobak_payne_drawing.hpp (original)
+++ branches/release/boost/graph/chrobak_payne_drawing.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -193,8 +193,8 @@
delta_p_q += delta_x[temp];
}
- delta_x[v] = (y[rightmost] - y[leftmost] + delta_p_q)/2;
- y[v] = (y[rightmost] + y[leftmost] + delta_p_q)/2;
+ delta_x[v] = ((y[rightmost] + delta_p_q) - y[leftmost])/2;
+ y[v] = y[leftmost] + delta_x[v];
delta_x[rightmost] = delta_p_q - delta_x[v];
bool leftmost_and_rightmost_adjacent = right[leftmost] == rightmost;
Modified: branches/release/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/detail/adjacency_list.hpp (original)
+++ branches/release/boost/graph/detail/adjacency_list.hpp 2008-12-20 14:07:58 EST (Sat, 20 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);
@@ -1902,6 +1910,7 @@
bool inserted;
boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
v->m_position = pos;
+ g.added_vertex(v);
return v;
}
// O(1)
@@ -1910,13 +1919,19 @@
add_vertex(const typename Config::vertex_property_type& p,
adj_list_impl<Derived, Config, Base>& g_)
{
+ typedef typename Config::vertex_descriptor vertex_descriptor;
Derived& g = static_cast<Derived&>(g_);
+ if (optional<vertex_descriptor> v
+ = g.vertex_by_property(get_property_value(p, vertex_bundle)))
+ return *v;
+
typedef typename Config::stored_vertex stored_vertex;
stored_vertex* v = new stored_vertex(p);
typename Config::StoredVertexList::iterator pos;
bool inserted;
boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
v->m_position = pos;
+ g.added_vertex(v);
return v;
}
// O(1)
@@ -1926,6 +1941,7 @@
{
typedef typename Config::stored_vertex stored_vertex;
Derived& g = static_cast<Derived&>(g_);
+ g.removing_vertex(u);
stored_vertex* su = (stored_vertex*)u;
g.m_vertices.erase(su->m_position);
delete su;
@@ -1933,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_);
@@ -1948,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;
@@ -1962,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;
@@ -1973,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;
@@ -1986,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;
@@ -1999,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;
@@ -2019,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();
@@ -2029,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();
@@ -2046,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;
@@ -2073,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) {
@@ -2098,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;
}
@@ -2110,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;
@@ -2127,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
@@ -2141,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);
@@ -2153,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;
}
@@ -2171,6 +2187,7 @@
add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
Graph& g = static_cast<Graph&>(g_);
g.m_vertices.resize(g.m_vertices.size() + 1);
+ g.added_vertex(g.m_vertices.size() - 1);
return g.m_vertices.size() - 1;
}
@@ -2178,9 +2195,14 @@
inline typename Config::vertex_descriptor
add_vertex(const typename Config::vertex_property_type& p,
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
+ = g.vertex_by_property(get_property_value(p, vertex_bundle)))
+ return *v;
typedef typename Config::stored_vertex stored_vertex;
g.m_vertices.push_back(stored_vertex(p));
+ g.added_vertex(g.m_vertices.size() - 1);
return g.m_vertices.size() - 1;
}
@@ -2189,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_)
@@ -2203,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_)
{
@@ -2219,12 +2241,13 @@
{
typedef typename Config::directed_category Cat;
Graph& g = static_cast<Graph&>(g_);
+ g.removing_vertex(v);
detail::remove_vertex_dispatch(g, v, Cat());
}
// 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;
@@ -2237,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;
@@ -2258,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;
@@ -2266,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,
@@ -2282,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,
@@ -2306,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;
@@ -2343,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,
@@ -2622,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>
>
{
@@ -2652,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>
>
{
@@ -2677,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;
};
};
@@ -2693,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;
};
};
@@ -2723,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;
};
@@ -2742,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;
};
@@ -2755,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;
};
@@ -2777,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
@@ -2787,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
@@ -2797,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
@@ -2823,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: branches/release/boost/graph/exception.hpp
==============================================================================
--- branches/release/boost/graph/exception.hpp (original)
+++ branches/release/boost/graph/exception.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -15,29 +15,40 @@
namespace boost {
- struct bad_graph : public std::invalid_argument {
- bad_graph(const std::string& what_arg)
- : std::invalid_argument(what_arg) { }
- };
-
- struct not_a_dag : public bad_graph {
- not_a_dag()
- : bad_graph("The graph must be a DAG.") { }
- };
-
- struct negative_edge : public bad_graph {
- negative_edge()
- : bad_graph("The graph may not contain an edge with negative weight."){ }
- };
-
- struct negative_cycle : public bad_graph {
- negative_cycle()
- : bad_graph("The graph may not contain negative cycles.") { }
- };
- struct not_connected : public bad_graph {
- not_connected()
- : bad_graph("The graph must be connected.") { }
- };
+ struct bad_graph : public std::invalid_argument {
+ bad_graph(const std::string& what_arg)
+ : std::invalid_argument(what_arg) { }
+ };
+
+ struct not_a_dag : public bad_graph {
+ not_a_dag()
+ : bad_graph("The graph must be a DAG.")
+ { }
+ };
+
+ struct negative_edge : public bad_graph {
+ negative_edge()
+ : bad_graph("The graph may not contain an edge with negative weight.")
+ { }
+ };
+
+ struct negative_cycle : public bad_graph {
+ negative_cycle()
+ : bad_graph("The graph may not contain negative cycles.")
+ { }
+ };
+
+ struct not_connected : public bad_graph {
+ not_connected()
+ : bad_graph("The graph must be connected.")
+ { }
+ };
+
+ struct not_complete : public bad_graph {
+ not_complete()
+ : bad_graph("The graph must be complete.")
+ { }
+ };
} // namespace boost
Modified: branches/release/boost/graph/fruchterman_reingold.hpp
==============================================================================
--- branches/release/boost/graph/fruchterman_reingold.hpp (original)
+++ branches/release/boost/graph/fruchterman_reingold.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -137,11 +137,11 @@
std::size_t adj_end_column = column == columns - 1? column : column + 1;
for (std::size_t other_row = adj_start_row; other_row <= adj_end_row;
++other_row)
- for (std::size_t other_column = adj_start_column;
+ for (std::size_t other_column = adj_start_column;
other_column <= adj_end_column; ++other_column)
if (other_row != row || other_column != column) {
// Repulse vertices in this bucket
- bucket_t& other_bucket
+ bucket_t& other_bucket
= buckets[other_row * columns + other_column];
for (v = other_bucket.begin(); v != other_bucket.end(); ++v)
apply_force(*u, *v);
@@ -301,20 +301,20 @@
BOOST_USING_STD_MAX();
Dim disp_size = sqrt(displacement[*v].x * displacement[*v].x
+ displacement[*v].y * displacement[*v].y);
- position[*v].x += displacement[*v].x / disp_size
+ position[*v].x += displacement[*v].x / disp_size
* min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
- position[*v].y += displacement[*v].y / disp_size
+ position[*v].y += displacement[*v].y / disp_size
* min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
- position[*v].x = min BOOST_PREVENT_MACRO_SUBSTITUTION
- (width / 2,
- max BOOST_PREVENT_MACRO_SUBSTITUTION(-width / 2,
+ position[*v].x = min BOOST_PREVENT_MACRO_SUBSTITUTION
+ (width / 2,
+ max BOOST_PREVENT_MACRO_SUBSTITUTION(-width / 2,
position[*v].x));
position[*v].y = min BOOST_PREVENT_MACRO_SUBSTITUTION
- (height / 2,
- max BOOST_PREVENT_MACRO_SUBSTITUTION(-height / 2,
+ (height / 2,
+ max BOOST_PREVENT_MACRO_SUBSTITUTION(-height / 2,
position[*v].y));
}
- } while (temp = cool());
+ } while ((temp = cool()));
}
namespace detail {
Modified: branches/release/boost/graph/graphml.hpp
==============================================================================
--- branches/release/boost/graph/graphml.hpp (original)
+++ branches/release/boost/graph/graphml.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -25,15 +25,15 @@
#include <exception>
#include <sstream>
-namespace boost
+namespace boost
{
/////////////////////////////////////////////////////////////////////////////
// Graph reader exceptions
/////////////////////////////////////////////////////////////////////////////
-struct parse_error: public graph_exception
+struct parse_error: public graph_exception
{
- parse_error(const std::string& error) {statement = "parse error: " + error;}
+ parse_error(const std::string& error) {statement = "parse error: " + error;}
virtual ~parse_error() throw() {}
virtual const char* what() const throw() {return statement.c_str();}
std::string statement;
@@ -48,14 +48,14 @@
virtual boost::any do_add_vertex() = 0;
virtual std::pair<boost::any,bool> do_add_edge(boost::any source, boost::any target) = 0;
-
- virtual void
+
+ virtual void
set_graph_property(const std::string& name, const std::string& value, const std::string& value_type) = 0;
- virtual void
+ virtual void
set_vertex_property(const std::string& name, boost::any vertex, const std::string& value, const std::string& value_type) = 0;
-
- virtual void
+
+ virtual void
set_edge_property(const std::string& name, boost::any edge, const std::string& value, const std::string& value_type) = 0;
};
@@ -87,27 +87,27 @@
return std::make_pair(any(retval.first), retval.second);
}
- virtual void
+ virtual void
set_graph_property(const std::string& name, const std::string& value, const std::string& value_type)
{
bool type_found = false;
try
{
mpl::for_each<value_types>(put_property<MutableGraph,value_types>
- (name, m_dp, m_g, value, value_type, m_type_names, type_found));
+ (name, m_dp, m_g, value, value_type, m_type_names, type_found));
}
catch (bad_lexical_cast)
{
- throw parse_error("invalid value \"" + value + "\" for key " +
+ throw parse_error("invalid value \"" + value + "\" for key " +
name + " of type " + value_type);
}
if (!type_found)
- throw parse_error("unrecognized type \"" + value_type +
+ throw parse_error("unrecognized type \"" + value_type +
"\" for key " + name);
-
+
}
-
- virtual void
+
+ virtual void
set_vertex_property(const std::string& name, any vertex, const std::string& value, const std::string& value_type)
{
bool type_found = false;
@@ -115,20 +115,20 @@
{
mpl::for_each<value_types>(put_property<vertex_descriptor,value_types>
(name, m_dp, any_cast<vertex_descriptor>(vertex),
- value, value_type, m_type_names, type_found));
+ value, value_type, m_type_names, type_found));
}
catch (bad_lexical_cast)
{
- throw parse_error("invalid value \"" + value + "\" for key " +
+ throw parse_error("invalid value \"" + value + "\" for key " +
name + " of type " + value_type);
}
if (!type_found)
- throw parse_error("unrecognized type \"" + value_type +
+ throw parse_error("unrecognized type \"" + value_type +
"\" for key " + name);
-
+
}
-
- virtual void
+
+ virtual void
set_edge_property(const std::string& name, any edge, const std::string& value, const std::string& value_type)
{
bool type_found = false;
@@ -136,15 +136,15 @@
{
mpl::for_each<value_types>(put_property<edge_descriptor,value_types>
(name, m_dp, any_cast<edge_descriptor>(edge),
- value, value_type, m_type_names, type_found));
+ value, value_type, m_type_names, type_found));
}
catch (bad_lexical_cast)
{
- throw parse_error("invalid value \"" + value + "\" for key " +
+ throw parse_error("invalid value \"" + value + "\" for key " +
name + " of type " + value_type);
}
if (!type_found)
- throw parse_error("unrecognized type \"" + value_type +
+ throw parse_error("unrecognized type \"" + value_type +
"\" for key " + name);
}
@@ -152,11 +152,11 @@
class put_property
{
public:
- put_property(const std::string& name, dynamic_properties& dp, const Key& key,
- const std::string& value, const std::string& value_type,
- char** type_names, bool& type_found)
- : m_name(name), m_dp(dp), m_key(key), m_value(value),
- m_value_type(value_type), m_type_names(type_names),
+ put_property(const std::string& name, dynamic_properties& dp, const Key& key,
+ const std::string& value, const std::string& value_type,
+ const char** type_names, bool& type_found)
+ : m_name(name), m_dp(dp), m_key(key), m_value(value),
+ m_value_type(value_type), m_type_names(type_names),
m_type_found(type_found) {}
template <class Value>
void operator()(Value)
@@ -173,19 +173,19 @@
const Key& m_key;
const std::string& m_value;
const std::string& m_value_type;
- char** m_type_names;
+ const char** m_type_names;
bool& m_type_found;
- };
-
+ };
+
protected:
MutableGraph& m_g;
dynamic_properties& m_dp;
typedef mpl::vector<bool, int, long, float, double, std::string> value_types;
- static char* m_type_names[];
+ static const char* m_type_names[];
};
template<typename MutableGraph>
-char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean", "int", "long", "float", "double", "string"};
+const char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean", "int", "long", "float", "double", "string"};
void BOOST_GRAPH_DECL
read_graphml(std::istream& in, mutate_graph& g);
@@ -193,7 +193,7 @@
template<typename MutableGraph>
void
read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp)
-{
+{
mutate_graph_impl<MutableGraph> mg(g,dp);
read_graphml(in, mg);
}
@@ -202,7 +202,7 @@
class get_type_name
{
public:
- get_type_name(const std::type_info& type, char** type_names, std::string& type_name)
+ get_type_name(const std::type_info& type, const char** type_names, std::string& type_name)
: m_type(type), m_type_names(type_names), m_type_name(type_name) {}
template <typename Type>
void operator()(Type)
@@ -212,7 +212,7 @@
}
private:
const std::type_info &m_type;
- char** m_type_names;
+ const char** m_type_names;
std::string &m_type_name;
};
@@ -226,22 +226,22 @@
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- BOOST_STATIC_CONSTANT(bool,
- graph_is_directed =
+ BOOST_STATIC_CONSTANT(bool,
+ graph_is_directed =
(is_convertible<directed_category*, directed_tag*>::value));
out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"
<< "<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd\">\n";
typedef mpl::vector<bool, short, unsigned short, int, unsigned int, long, unsigned long, long long, unsigned long long, float, double, long double, std::string> value_types;
- char* type_names[] = {"boolean", "int", "int", "int", "int", "long", "long", "long", "long", "float", "double", "double", "string"};
+ const char* type_names[] = {"boolean", "int", "int", "int", "int", "long", "long", "long", "long", "float", "double", "double", "string"};
std::map<std::string, std::string> graph_key_ids;
std::map<std::string, std::string> vertex_key_ids;
std::map<std::string, std::string> edge_key_ids;
int key_count = 0;
// Output keys
- for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
+ for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
{
std::string key_id = "key" + lexical_cast<std::string>(key_count++);
if (i->second->key() == typeid(Graph))
@@ -254,14 +254,14 @@
continue;
std::string type_name = "string";
mpl::for_each<value_types>(get_type_name<value_types>(i->second->value(), type_names, type_name));
- out << " <key id=\"" << key_id << "\" for=\""
+ out << " <key id=\"" << key_id << "\" for=\""
<< (i->second->key() == typeid(Graph) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\""
<< " attr.name=\"" << i->first << "\""
<< " attr.type=\"" << type_name << "\""
<< " />\n";
}
- out << " <graph id=\"G\" edgedefault=\""
+ out << " <graph id=\"G\" edgedefault=\""
<< (graph_is_directed ? "directed" : "undirected") << "\""
<< " parse.nodeids=\"" << (ordered_vertices ? "canonical" : "free") << "\""
<< " parse.edgeids=\"canonical\" parse.order=\"nodesfirst\">\n";
@@ -269,13 +269,13 @@
// Output graph data
for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
{
- if (i->second->key() == typeid(Graph))
+ if (i->second->key() == typeid(Graph))
{
out << " <data key=\"" << graph_key_ids[i->first] << "\">"
<< i->second->get_string(g) << "</data>\n";
}
}
-
+
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
vertex_iterator v, v_end;
for (tie(v, v_end) = vertices(g); v != v_end; ++v)
@@ -284,7 +284,7 @@
// Output data
for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
{
- if (i->second->key() == typeid(vertex_descriptor))
+ if (i->second->key() == typeid(vertex_descriptor))
{
out << " <data key=\"" << vertex_key_ids[i->first] << "\">"
<< i->second->get_string(*v) << "</data>\n";
@@ -296,7 +296,7 @@
typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
edge_iterator e, e_end;
typename graph_traits<Graph>::edges_size_type edge_count = 0;
- for (tie(e, e_end) = edges(g); e != e_end; ++e)
+ for (tie(e, e_end) = edges(g); e != e_end; ++e)
{
out << " <edge id=\"e" << edge_count++ << "\" source=\"n"
<< get(vertex_index, source(*e, g)) << "\" target=\"n"
@@ -305,7 +305,7 @@
// Output data
for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
{
- if (i->second->key() == typeid(edge_descriptor))
+ if (i->second->key() == typeid(edge_descriptor))
{
out << " <data key=\"" << edge_key_ids[i->first] << "\">"
<< i->second->get_string(*e) << "</data>\n";
@@ -321,7 +321,7 @@
template <typename Graph>
void
-write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp,
+write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp,
bool ordered_vertices=false)
{
write_graphml(out, g, get(vertex_index, g), dp, ordered_vertices);
Modified: branches/release/boost/graph/is_straight_line_drawing.hpp
==============================================================================
--- branches/release/boost/graph/is_straight_line_drawing.hpp (original)
+++ branches/release/boost/graph/is_straight_line_drawing.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -164,7 +164,7 @@
edge_t e(get<0>(*itr));
vertex_t source_v(source(e,g));
vertex_t target_v(target(e,g));
- if (drawing[source_v].x > drawing[target_v].x)
+ if (drawing[source_v].y > drawing[target_v].y)
std::swap(source_v, target_v);
active_map_key_t key(get(drawing, source_v).y,
@@ -187,12 +187,32 @@
before = prior(a_itr);
after = next(a_itr);
- if (after != active_edges.end() || before != active_edges.end())
+ if (before != active_edges.end())
{
- edge_t f = after != active_edges.end() ?
- after->second : before->second;
+ edge_t f = before->second;
+ vertex_t e_source(source(e,g));
+ vertex_t e_target(target(e,g));
+ vertex_t f_source(source(f,g));
+ vertex_t f_target(target(f,g));
+ if (intersects(drawing[e_source].x,
+ drawing[e_source].y,
+ drawing[e_target].x,
+ drawing[e_target].y,
+ drawing[f_source].x,
+ drawing[f_source].y,
+ drawing[f_target].x,
+ drawing[f_target].y
+ )
+ )
+ return false;
+ }
+
+ if (after != active_edges.end())
+ {
+
+ edge_t f = after->second;
vertex_t e_source(source(e,g));
vertex_t e_target(target(e,g));
vertex_t f_source(source(f,g));
Modified: branches/release/boost/graph/read_dimacs.hpp
==============================================================================
--- branches/release/boost/graph/read_dimacs.hpp (original)
+++ branches/release/boost/graph/read_dimacs.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -9,24 +9,27 @@
/*
Reads maximal flow problem in extended DIMACS format.
- This works, but could use some polishing.
+ This works, but could use some polishing.
*/
/* ----------------------------------------------------------------- */
#include <vector>
-#include <istream>
-#include <stdio.h>
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+
+#include <boost/graph/graph_traits.hpp>
namespace boost {
template <class Graph, class CapacityMap, class ReverseEdgeMap>
int read_dimacs_max_flow(Graph& g,
- CapacityMap capacity,
+ CapacityMap capacity,
ReverseEdgeMap reverse_edge,
typename graph_traits<Graph>::vertex_descriptor& src,
typename graph_traits<Graph>::vertex_descriptor& sink,
- std::istream& in=std::cin)
+ std::istream& in = std::cin)
{
// const int MAXLINE = 100; /* max line length in the input file */
const int ARC_FIELDS = 3; /* no of fields in arc line */
@@ -37,7 +40,7 @@
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
-
+
std::vector<vertex_descriptor> verts;
long m, n, /* number of edges and nodes */
@@ -48,11 +51,11 @@
no_nslines=0, /* no of node-source-lines */
no_nklines=0, /* no of node-source-lines */
no_alines=0; /* no of arc-lines */
-
+
std::string in_line; /* for reading input line */
char pr_type[3]; /* for reading type of the problem */
char nd; /* source (s) or sink (t) */
-
+
int k, /* temporary */
err_no; /* no of detected error */
@@ -78,9 +81,9 @@
const int EN19 = 18;
const int EN20 = 19;
const int EN22 = 20;
-
- static char *err_message[] =
- {
+
+ static char *err_message[] =
+ {
/* 0*/ "more than one problem line.",
/* 1*/ "wrong number of parameters in the problem line.",
/* 2*/ "it is not a Max Flow problem line.",
@@ -121,14 +124,14 @@
case '\n': /* skip empty lines */
case '\0': /* skip empty lines at the end of file */
break;
-
+
case 'p': /* problem description */
if ( no_plines > 0 )
/* more than one problem line */
{ err_no = EN1 ; goto error; }
-
+
no_plines = 1;
-
+
if (
/* reading problem line: type of problem, no of nodes, no of arcs */
sscanf ( in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m )
@@ -136,11 +139,11 @@
)
/*wrong number of parameters in the problem line*/
{ err_no = EN2; goto error; }
-
+
if ( strcmp ( pr_type, PROBLEM_TYPE ) )
/*wrong problem type*/
{ err_no = EN3; goto error; }
-
+
if ( n <= 0 || m <= 0 )
/*wrong value of no of arcs or nodes*/
{ err_no = EN4; goto error; }
@@ -150,83 +153,83 @@
verts.push_back(add_vertex(g));
}
break;
-
+
case 'n': /* source(s) description */
if ( no_plines == 0 )
/* there was not problem line above */
{ err_no = EN8; goto error; }
-
+
/* reading source or sink */
k = sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd );
--i; // index from 0
if ( k < NODE_FIELDS )
/* node line is incorrect */
{ err_no = EN11; goto error; }
-
+
if ( i < 0 || i > n )
/* wrong value of node */
{ err_no = EN12; goto error; }
-
+
switch (nd) {
case 's': /* source line */
-
+
if ( no_nslines != 0)
- /* more than one source line */
+ /* more than one source line */
{ err_no = EN9; goto error; }
-
+
no_nslines = 1;
src = verts[i];
break;
-
+
case 't': /* sink line */
-
+
if ( no_nklines != 0)
/* more than one sink line */
{ err_no = EN9; goto error; }
-
+
no_nklines = 1;
sink = verts[i];
break;
-
+
default:
/* wrong type of node-line */
- err_no = EN12; goto error;
+ err_no = EN12; goto error;
}
break;
-
+
case 'a': /* arc description */
- if ( no_nslines == 0 || no_nklines == 0 )
+ if ( no_nslines == 0 || no_nklines == 0 )
/* there was not source and sink description above */
{ err_no = EN14; goto error; }
-
+
if ( no_alines >= m )
/*too many arcs on input*/
{ err_no = EN16; goto error; }
-
+
if (
/* reading an arc description */
sscanf ( in_line.c_str(),"%*c %ld %ld %ld",
&tail, &head, &cap )
!= ARC_FIELDS
- )
+ )
/* arc description is not correct */
{ err_no = EN15; goto error; }
--tail; // index from 0, not 1
--head;
if ( tail < 0 || tail > n ||
- head < 0 || head > n
+ head < 0 || head > n
)
/* wrong value of nodes */
{ err_no = EN17; goto error; }
- {
- edge_descriptor e1, e2;
+ {
+ edge_descriptor e1, e2;
bool in1, in2;
tie(e1, in1) = add_edge(verts[tail], verts[head], g);
tie(e2, in2) = add_edge(verts[head], verts[tail], g);
if (!in1 || !in2) {
- std::cerr << "unable to add edge (" << head << "," << tail << ")"
+ std::cerr << "unable to add edge (" << head << "," << tail << ")"
<< std::endl;
return -1;
}
@@ -237,38 +240,38 @@
}
++no_alines;
break;
-
+
default:
/* unknown type of line */
err_no = EN18; goto error;
-
+
} /* end of switch */
} /* end of input loop */
-
- /* ----- all is red or error while reading ----- */
-
+
+ /* ----- all is red or error while reading ----- */
+
if ( feof (stdin) == 0 ) /* reading error */
- { err_no=EN21; goto error; }
-
+ { err_no=EN21; goto error; }
+
if ( no_lines == 0 ) /* empty input */
- { err_no = EN22; goto error; }
-
+ { err_no = EN22; goto error; }
+
if ( no_alines < m ) /* not enough arcs */
- { err_no = EN19; goto error; }
-
- if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0 )
+ { err_no = EN19; goto error; }
+
+ if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0 )
/* no arc goes out of the source */
{ err_no = EN20; goto error; }
-
+
/* Thanks God! all is done */
return (0);
-
+
/* ---------------------------------- */
error: /* error found reading input */
-
- printf ( "\nline %ld of input - %s\n",
+
+ printf ( "\nline %ld of input - %s\n",
no_lines, err_message[err_no] );
-
+
exit (1);
return (0); /* to avoid warning */
}
Modified: branches/release/boost/graph/reverse_graph.hpp
==============================================================================
--- branches/release/boost/graph/reverse_graph.hpp (original)
+++ branches/release/boost/graph/reverse_graph.hpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -76,9 +76,9 @@
typedef typename Traits::edges_size_type edges_size_type;
// More typedefs used by detail::edge_property_map, vertex_property_map
- typedef typename BidirectionalGraph::edge_property_type
+ typedef typename boost::edge_property_type<BidirectionalGraph>::type
edge_property_type;
- typedef typename BidirectionalGraph::vertex_property_type
+ typedef typename boost::vertex_property_type<BidirectionalGraph>::type
vertex_property_type;
typedef reverse_graph_tag graph_tag;
@@ -146,16 +146,16 @@
}
template <class BidirectionalGraph, class GRef>
-inline std::pair<typename BidirectionalGraph::in_edge_iterator,
- typename BidirectionalGraph::in_edge_iterator>
-out_edges(const typename BidirectionalGraph::vertex_descriptor u,
+inline std::pair<typename graph_traits<BidirectionalGraph>::in_edge_iterator,
+ typename graph_traits<BidirectionalGraph>::in_edge_iterator>
+out_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
return in_edges(u, g.m_g);
}
template <class BidirectionalGraph, class GRef>
-inline typename BidirectionalGraph::vertices_size_type
+inline typename graph_traits<BidirectionalGraph>::vertices_size_type
num_vertices(const reverse_graph<BidirectionalGraph,GRef>& g)
{
return num_vertices(g.m_g);
@@ -169,26 +169,27 @@
}
template <class BidirectionalGraph, class GRef>
-inline typename BidirectionalGraph::degree_size_type
-out_degree(const typename BidirectionalGraph::vertex_descriptor u,
+inline typename graph_traits<BidirectionalGraph>::degree_size_type
+out_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
return in_degree(u, g.m_g);
}
template <class BidirectionalGraph, class GRef>
-inline std::pair<typename BidirectionalGraph::edge_descriptor, bool>
-edge(const typename BidirectionalGraph::vertex_descriptor u,
- const typename BidirectionalGraph::vertex_descriptor v,
+inline std::pair<typename graph_traits<BidirectionalGraph>::edge_descriptor,
+ bool>
+edge(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
+ const typename graph_traits<BidirectionalGraph>::vertex_descriptor v,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
return edge(v, u, g.m_g);
}
template <class BidirectionalGraph, class GRef>
-inline std::pair<typename BidirectionalGraph::out_edge_iterator,
- typename BidirectionalGraph::out_edge_iterator>
-in_edges(const typename BidirectionalGraph::vertex_descriptor u,
+inline std::pair<typename graph_traits<BidirectionalGraph>::out_edge_iterator,
+ typename graph_traits<BidirectionalGraph>::out_edge_iterator>
+in_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
return out_edges(u, g.m_g);
@@ -197,20 +198,20 @@
template <class BidirectionalGraph, class GRef>
inline std::pair<typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator,
typename reverse_graph<BidirectionalGraph,GRef>::adjacency_iterator>
-adjacent_vertices(const typename BidirectionalGraph::vertex_descriptor u,
+adjacent_vertices(typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
typedef reverse_graph<BidirectionalGraph,GRef> Graph;
- typename Graph::out_edge_iterator first, last;
+ typename graph_traits<Graph>::out_edge_iterator first, last;
tie(first, last) = out_edges(u, g);
- typedef typename Graph::adjacency_iterator adjacency_iterator;
+ typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
return std::make_pair(adjacency_iterator(first, const_cast<Graph*>(&g)),
adjacency_iterator(last, const_cast<Graph*>(&g)));
}
template <class BidirectionalGraph, class GRef>
-inline typename BidirectionalGraph::degree_size_type
-in_degree(const typename BidirectionalGraph::vertex_descriptor u,
+inline typename graph_traits<BidirectionalGraph>::degree_size_type
+in_degree(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
return out_degree(u, g.m_g);
Modified: branches/release/libs/graph/doc/adjacency_list.html
==============================================================================
--- branches/release/libs/graph/doc/adjacency_list.html (original)
+++ branches/release/libs/graph/doc/adjacency_list.html 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -8,10 +8,10 @@
-->
<Head>
<Title>Boost Graph Library: Adjacency List</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
<BR Clear>
@@ -146,7 +146,7 @@
<H3>Model of</H3>
<P>
-VertexAndEdgeListGraph,
+VertexAndEdgeListGraph,
<a href="./MutablePropertyGraph.html">MutablePropertyGraph</a>,
<a href="../../utility/CopyConstructible.html">CopyConstructible</a>,
<a href="../../utility/Assignable.html">Assignable</a>,
@@ -178,7 +178,7 @@
HREF="../../property_map/property_map.html">Property Map
Concepts</A> or may be bundled properties,
which have a more succinct syntax. The types of all property values
-must be Copy Constructible, Assignable, and Default Constructible.
+must be Copy Constructible, Assignable, and Default Constructible.
The property maps obtained from the
<TT>adjacency_list</TT> class are models of the <a
href="../../property_map/LvaluePropertyMap.html">Lvalue Property
@@ -322,30 +322,51 @@
<CAPTION ALIGN="BOTTOM"><STRONG>Table:</STRONG>
Summary of Descriptor and Iterator Invalidation.
</CAPTION>
-<tr> <th>Function</th> <th>Vertex Desc</th> <th>Edge Desc</th>
-<th>Vertex Iter</th> <th>Edge Iter</th> <th>Adj Iter</th> </tr>
-
<tr>
-<td><tt>add_edge()</tt></td> <td align=center><tt>OK</tt></td><td
-align=center><tt>OK</tt></td><td align=center><tt>OK</tt></td><td
-align=center><tt>EL=vecS &&<br> Directed=directedS</tt></td><td align=center><tt>EL=vecS</tt></td>
+ <th>Function</th>
+ <th>Vertex Desc</th>
+ <th>Edge Desc</th>
+ <th>Vertex Iter</th>
+ <th>Edge Iter</th>
+ <th>Adj Iter</th>
</tr>
<tr>
-<td><tt>remove_edge()<br>remove_edge_if()<br>remove_out_edge_if()<br>remove_in_edge_if()<br>clear_vertex()</tt></td><td align=center><tt>OK</tt></td><td align=center><tt>OK</tt></td><td align=center><tt>OK</tt></td>
-<td align=center><tt>EL=vecS &&<br> Directed=directedS</tt></td><td align=center><tt>EL=vecS</tt></td>
+<td>
+ <tt>add_edge()</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>EL=vecS && <br>Directed=directedS</tt></td>
+ <td align=center><tt>EL=vecS</tt></td>
</tr>
<tr>
-<td><tt>add_vertex()</tt></td><td align=center><tt>OK</tt></td><td
-align=center><tt>OK</tt></td><td align=center><tt>OK</tt></td><td
-align=center><tt>OK</tt></td><td align=center><tt>OK</tt></td>
+ <td><tt>remove_edge()<br>remove_edge_if()<br>remove_out_edge_if()<br>
+ remove_in_edge_if()<br>clear_vertex()</tt>
+ </td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>EL=vecS && <br>Directed=directedS</tt></td>
+ <td align=center><tt>EL=vecS</tt></td>
</tr>
<tr>
-<td><tt>remove_vertex()</tt></td><td align=center><tt>VL=vecS</tt></td><td align=center><tt>VL=vecS</tt></td><td align=center><tt>VL=vecS</tt></td><td align=center><tt>VL=vecS</tt></td><td align=center><tt>VL=vecS</tt></td>
+ <td><tt>add_vertex()</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>OK</tt></td>
+ <td align=center><tt>VL=vecS && <br/> Directed=directedS</tt></td>
+ <td align=center><tt>VL=vecS && <br/> Directed=directedS</tt></td>
+</tr>
+<tr>
+ <td><tt>remove_vertex()</tt></td>
+ <td align=center><tt>VL=vecS</tt></td>
+ <td align=center><tt>VL=vecS</tt></td>
+ <td align=center><tt>VL=vecS</tt></td>
+ <td align=center><tt>VL=vecS</tt></td>
+ <td align=center><tt>VL=vecS</tt></td>
</tr>
-
</table>
-
<H2>Associated Types</H2>
<hr>
@@ -539,7 +560,7 @@
<hr>
<pre>
-adjacency_list(vertices_size_type n,
+adjacency_list(vertices_size_type n,
const GraphProperty& p = GraphProperty())
</pre>
Creates a graph object with <TT>n</TT> vertices and zero edges.
@@ -550,8 +571,8 @@
<pre>
template <class EdgeIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
- vertices_size_type n,
- edges_size_type m = 0,
+ vertices_size_type n,
+ edges_size_type m = 0,
const GraphProperty& p = GraphProperty())
</pre>
Creates a graph object with <TT>n</TT> vertices and with the edges
@@ -600,7 +621,7 @@
Swap the vertices, edges, and properties of this graph with the
vertices, edges, and properties of graph <tt>x</tt>.
<hr>
-
+
<P>
<H2>Non-Member Functions</H2>
@@ -781,7 +802,7 @@
<p>
The placement of the new edge in the out-edge list is in general
unspecified, though ordering of the out-edge list can be accomplished
-through the choice of <tt>OutEdgeList</tt>.
+through the choice of <tt>OutEdgeList</tt>.
If the <tt>VertexList</tt> selector is
<tt>vecS</tt>, and if either vertex descriptor <tt>u</tt> or
@@ -821,7 +842,7 @@
void remove_edge(vertex_descriptor u, vertex_descriptor v,
adjacency_list& g)
</pre>
-Removes the edge <i>(u,v)</i> from the graph.
+Removes the edge <i>(u,v)</i> from the graph.
<p>
This operation causes any outstanding edge descriptors or iterators
that point to edge <i>(u,v)</i> to become invalid. In addition, if
@@ -867,7 +888,7 @@
</pre>
Removes all out-edges of vertex <i>u</i> from the graph that satisfy
the <tt>predicate</tt>. That is, if the predicate returns true when
-applied to an edge descriptor, then the edge is removed.
+applied to an edge descriptor, then the edge is removed.
<p>
The affect on descriptor and iterator stability is the same as that of
invoking <tt>remove_edge()</tt> on each of the removed edges.
@@ -899,7 +920,7 @@
</pre>
Removes all edges from the graph that satisfy
the <tt>predicate</tt>. That is, if the predicate returns true when
-applied to an edge descriptor, then the edge is removed.
+applied to an edge descriptor, then the edge is removed.
<p>
The affect on descriptor and iterator stability is the same as that of
invoking <tt>remove_edge()</tt> on each of the removed edges.
@@ -912,7 +933,7 @@
add_vertex(adjacency_list& g)
</pre>
Adds a vertex to the graph and returns the vertex descriptor for the
-new vertex.
+new vertex.
</a>
<hr>
@@ -975,7 +996,7 @@
Remove vertex <i>u</i> from the vertex set of the graph. It is assumed
that there are no edges to or from vertex <i>u</i> when it is removed.
One way to make sure of this is to invoke <TT>clear_vertex()</TT>
-beforehand.
+beforehand.
<p>
If the <TT>VertexList</TT> template parameter of the
<TT>adjacency_list</TT> was <TT>vecS</TT>, then all vertex
@@ -1110,7 +1131,7 @@
</TD></TR></TABLE>
</BODY>
-</HTML>
+</HTML>
<!-- LocalWords: gif ALT OutEdgeList EdgeList VertexList html VertexProperties EdgeProperties
-->
<!-- LocalWords: GraphPropertyTag cpp enum ai cout endl VertexAndEdgeListGraph
Modified: branches/release/libs/graph/doc/known_problems.html
==============================================================================
--- branches/release/libs/graph/doc/known_problems.html (original)
+++ branches/release/libs/graph/doc/known_problems.html 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -8,14 +8,17 @@
-->
<Head>
<Title>Known Problems</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
<BR Clear>
- <h1>Known Problems</h1>
+ <h1>Known Problems and Workarounds</h1>
+
+This is a list of known problems compiling the BGL for different compilers and
+versions.
<ol>
<li>The <code>subgraph</code> adaptor has several known problems:
@@ -23,7 +26,7 @@
<li>Each instance of subgraph has its own copy of internal
vertex and edge properties. Only at the root subgraph are the
properties valid. </li>
-
+
<li>Edge and vertex removal functions are unimplemented.</li>
<li>The graph is required to have vertex descriptors of integral
@@ -38,9 +41,16 @@
<li>Using a GraphProperty with adjacency_list may cause a VC++ internal compiler error.</li>
<li>Using get(property, graph, edge) may cause a VC++ internal compiler error.</li>
- <li>"using boost::tie;" may cause VC++ internal compiler error.
+ <li>"using boost::tie;" may cause VC++ internal compiler error.
</ol>
+<h2>Workarounds</h2>
+<p>
+<b>Compiler Warnings on <code>hash_set</code> and <code>hash_map</code></b>. Versions of
+GCC >= 4.3 deprecate these headers and data structures and will emit warnings when
+compiling the BGL. To suppress these warnings <em>and the hash-based storage selectors</em>
+define the <code>BOOST_NO_HASH</code> prior to including any Boost.Graph headers.
+</p>
<br>
<HR>
@@ -57,4 +67,4 @@
</TD></TR></TABLE>
</BODY>
-</HTML>
+</HTML>
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -8,10 +8,10 @@
-->
<Head>
<Title>Table of Contents: Boost Graph Library</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
<BR Clear>
@@ -70,25 +70,28 @@
<LI>DFS Visitor
<LI>Dijkstra Visitor
<LI>Bellman Ford Visitor
- <LI>A* Visitor</LI>
+ <LI>A* Visitor</LI>
<LI>Event Visitor
- <LI>Planar Face Visitor
+ <LI>Planar Face Visitor
+ <li>TSP Tour Visitor</li>
</OL>
<li>EventVisitorList Adaptors
<OL>
- <LI>Event Visitor List
- <LI>bfs_visitor
- <LI>dfs_visitor
- <LI>dijkstra_visitor
- <LI>bellman_visitor
- <li>astar_visitor</li>
+ <LI>Event Visitor List
+ <LI>bfs_visitor
+ <LI>dfs_visitor
+ <LI>dijkstra_visitor
+ <LI>bellman_visitor
+ <li>astar_visitor</li>
</OL>
<li>Event Visitors
<OL>
- <LI>predecessor_recorder
- <LI>distance_recorder
- <LI>time_stamper
- <LI>property_writer
+ <LI>predecessor_recorder
+ <LI>distance_recorder
+ <LI>time_stamper
+ <LI>property_writer
+ <li>tsp_tour_visitor</li>
+ <li>tsp_tour_len_visitor</li>
</OL>
<LI>Graph classes
<OL>
@@ -151,28 +154,28 @@
<LI><A
href="./prim_minimum_spanning_tree.html"><tt>prim_minimum_spanning_tree</tt></A>
</OL>
- <LI>Connected Components Algorithms
- <OL>
- <LI>connected_components
- <LI>strong_components
-
- <LI>biconnected_components
- <LI>articulation_points
- <LI>Incremental Connected Components
- <OL>
- <LI>initialize_incremental_components
- <LI>incremental_components
- <LI><A
- href="./incremental_components.html#sec:same-component"><tt>same_component</tt></A>
- <LI>component_index
- </OL>
- </OL></LI>
+ <LI>Connected Components Algorithms
+ <OL>
+ <LI>connected_components
+ <LI>strong_components
+
+ <LI>biconnected_components
+ <LI>articulation_points
+ <LI>Incremental Connected Components
+ <OL>
+ <LI>initialize_incremental_components
+ <LI>incremental_components
+ <LI><A
+ href="./incremental_components.html#sec:same-component"><tt>same_component</tt></A>
+ <LI>component_index
+ </OL>
+ </OL></LI>
<LI>Maximum Flow and Matching Algorithms
<OL>
<LI>edmunds_karp_max_flow
<LI>push_relabel_max_flow
<li>kolmogorov_max_flow</li>
- <LI>edmonds_maximum_cardinality_matching
+ <LI>edmonds_maximum_cardinality_matching
</OL>
<li>Sparse Matrix Ordering Algorithms
@@ -183,34 +186,39 @@
<LI>minimum_degree_ordering
</ol>
</li>
- <LI>topological_sort
- <li>transitive_closure
- <LI>copy_graph
- <LI>transpose_graph
- <LI>isomorphism
-
- <LI><A
- href="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></A>
- <li>sloan_ordering</li>
+ <LI>topological_sort
+ <li>transitive_closure
+ <LI>copy_graph
+ <LI>transpose_graph
+ <LI>isomorphism
+
+ <li>Path and Tour Algorithms
+ <ol>
+ <li>metric_tsp_approx</li>
+ </ol>
+ </li>
+
+ <LI>sequential_vertex_coloring
+ <li>sloan_ordering</li>
<li>sloan_start_end_vertices</li>
<LI>ith_wavefront, max_wavefront, aver_wavefront, and rms_wavefront</LI>
<LI>brandes_betweenness_centrality</LI>
<li>Layout algorithms
<ol>
- <li>random_graph_layout</li>
+ <li>random_graph_layout</li>
<li>circle_layout</li>
<li>kamada_kawai_spring_layout</li>
- <li>fruchterman_reingold_force_directed_layout</li>
+ <li>fruchterman_reingold_force_directed_layout</li>
<li>gursoy_atun_layout</li>
- </ol>
- </li>
+ </ol>
+ </li>
<li>Clustering algorithms
- <ol>
+ <ol>
<li>betweenness_centrality_clustering</li>
- </ol>
+ </ol>
</li>
- <li>astar_search</li>
+ <li>astar_search</li>
<li>lengauer_tarjan_dominator_tree</li>
<li>minimum_cycle_ratio and maximum_cycle_ratio</li>
<li>Planar Graph Algorithms
@@ -292,4 +300,4 @@
</TD></TR></TABLE>
</BODY>
-</HTML>
+</HTML>
Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 (original)
+++ branches/release/libs/graph/test/Jamfile.v2 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -4,7 +4,7 @@
# (See accompanying file LICENSE_1_0.txt or copy at
# http://www.boost.org/LICENSE_1_0.txt)
-# Define SGB (stanford graph base top level directory) and
+# Define SGB (stanford graph base top level directory) and
# LEDA (also top level directory) at the command line of jam using -s
import modules ;
@@ -17,69 +17,48 @@
if [ modules.peek : EXPAT_INCLUDE ] && [ modules.peek : EXPAT_LIBPATH ]
{
- optional_tests += [ run graphml_test.cpp ../build//boost_graph ] ;
+ optional_tests += [ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ] ;
}
-test-suite graph_test :
+test-suite graph_test :
[ run transitive_closure_test.cpp ]
-
[ compile adj_list_cc.cpp ]
# adj_list_test needs some work -JGS
# 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 ]
-
[ run bellman-test.cpp ]
-
- [ run betweenness_centrality_test.cpp ]
-
+ [ run betweenness_centrality_test.cpp ]
[ run bidir_remove_edge.cpp ]
-
[ run csr_graph_test.cpp : : : : : <variant>release ]
-
[ run dag_longest_paths.cpp ]
-
[ run dfs.cpp ../../test/build//boost_test_exec_monitor ]
-
[ compile dfs_cc.cpp ]
-
[ compile dijkstra_cc.cpp ]
-
[ run dijkstra_heap_performance.cpp : 10000 ]
-
[ run dominator_tree_test.cpp ]
-
[ run relaxed_heap_test.cpp : 5000 15000 ]
-
[ compile edge_list_cc.cpp ]
-
[ compile filtered_graph_cc.cpp ]
-
[ run graph.cpp ]
-
[ compile graph_concepts.cpp ]
-
- [ run graphviz_test.cpp
- /boost/test//boost_test_exec_monitor/<link>static
+ [ run graphviz_test.cpp
+ /boost/test//boost_test_exec_monitor/<link>static
../build//boost_graph ]
-
[ run gursoy_atun_layout_test.cpp ]
-
[ run layout_test.cpp : : : <test-info>always_show_run_output <toolset>intel:<debug-symbols>off ]
- [ run serialize.cpp
+ [ run serialize.cpp
../../serialization/build//boost_serialization
: : : ]
- [ compile reverse_graph_cc.cpp ]
+ [ compile reverse_graph_cc.cpp ]
[ run sequential_vertex_coloring.cpp ]
@@ -87,13 +66,13 @@
[ run isomorphism.cpp ../../test/build//boost_test_exec_monitor ]
- [ run adjacency_matrix_test.cpp ]
+ [ run adjacency_matrix_test.cpp ]
[ compile vector_graph_cc.cpp ]
[ compile copy.cpp ]
-
- [ compile property_iter.cpp ]
+
+ [ compile property_iter.cpp ]
[ run bundled_properties.cpp ]
@@ -123,16 +102,23 @@
[ run make_maximal_planar_test.cpp ]
- [ run all_planar_input_files_test.cpp
- ../../filesystem/build
+ [ run named_vertices_test.cpp ]
+
+ [ run all_planar_input_files_test.cpp
+ ../../filesystem/build
../../system/build
: $(PLANAR_INPUT_FILES) ]
- [ run parallel_edges_loops_test.cpp
- ../../filesystem/build
+ [ run parallel_edges_loops_test.cpp
+ ../../filesystem/build
../../system/build
: $(PLANAR_INPUT_FILES) ]
+ # [ run r_c_shortest_paths_test.cpp ]
+ [ run is_straight_line_draw_test.cpp ]
+ [ run metric_tsp_approx.cpp : metric_tsp_approx.txt ]
+ [ compile dimacs.cpp ]
+
$(optional_tests)
;
@@ -142,18 +128,18 @@
local SDB_DEPENDCIES =
<include>$(SGB) <library-file>$(SGB)/libgb.a ;
- compile stanford_graph_cc.cpp
+ compile stanford_graph_cc.cpp
$(SDB_DEPENDCIES) ;
}
# Run LEDA tests only when -sLEDA= is set.
if [ modules.peek : LEDA ] != ""
{
- local LEDA_DEPENDENCIES =
- <include>$(LEDA)/incl
+ local LEDA_DEPENDENCIES =
+ <include>$(LEDA)/incl
<library-file>$(LEDA)/libG.a
;
- compile leda_graph_cc.cpp
+ compile leda_graph_cc.cpp
$(LEDA_DEPENDENCIES) ;
}
Modified: branches/release/libs/graph/test/adjacency_matrix_test.cpp
==============================================================================
--- branches/release/libs/graph/test/adjacency_matrix_test.cpp (original)
+++ branches/release/libs/graph/test/adjacency_matrix_test.cpp 2008-12-20 14:07:58 EST (Sat, 20 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;
}
Modified: branches/release/libs/graph/test/graphml_test.cpp
==============================================================================
--- branches/release/libs/graph/test/graphml_test.cpp (original)
+++ branches/release/libs/graph/test/graphml_test.cpp 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -43,7 +43,7 @@
dp.property("foo",get(vertex_color_t(),g));
dp.property("weight",get(edge_weight_t(),g));
- ifstream ifile("graphml_test.xml");
+ ifstream ifile(argv[1]);
read_graphml(ifile, g, dp);
ifile.close();
Modified: branches/release/libs/graph/test/graphml_test.xml
==============================================================================
--- branches/release/libs/graph/test/graphml_test.xml (original)
+++ branches/release/libs/graph/test/graphml_test.xml 2008-12-20 14:07:58 EST (Sat, 20 Dec 2008)
@@ -19,7 +19,7 @@
<node id="n6">
<data key="d1">0</data>
</node>
- <edge id="e0" source="n0" target="n1" directed="false" />
+ <edge id="e0" source="n0" target="n1" />
<edge id="e1" source="n1" target="not a canonical node">
<data key="d2">0.8</data>
</edge>
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