|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-09 10:45:47
Author: asutton
Date: 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
New Revision: 47268
URL: http://svn.boost.org/trac/boost/changeset/47268
Log:
Finished reimplementing the undirected graph class using the descriptor lib.
This entailed rewriting some of the property store so that it actually
accepts incidence descriptors (iterators) into the various vertices. There's
a common problem of finding an incidence descriptor for a corresponding
vertex descriptor that could be solved a little more cleanly.
Removing some old files that are no longer used.
Stubbing out implementations for compressed (static) graphs. Not sure how
this will work just yet.
Started work on directed graphs.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_edges.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_vertices.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp (contents, props changed)
Removed:
sandbox/SOC/2008/graphs/trunk/boost/graphs/mapped_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_index.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp | 4 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp | 14 ++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp | 15 ++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp | 15 ++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp | 29 +++++++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp | 26 +++++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 13 +++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 101 ++++++++++++++++++++++-----------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp | 37 +++++---------
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp | 4
14 files changed, 147 insertions(+), 125 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -13,6 +13,7 @@
template <typename Iterator>
class adjacency_iterator
{
+public:
typedef Iterator iterator;
typedef typename Iterator::vertex_descriptor vertex_descriptor;
@@ -40,11 +41,14 @@
inline adjacency_iterator& operator--()
{ --_iter; return *this; }
+ /** @name Equality Comparable */
+ //@{
inline bool operator==(adjacency_iterator const& x) const
{ return _iter == x._iter; }
inline bool operator!=(adjacency_iterator const& x) const
{ return _iter != x._iter; }
+ //@}
reference operator*() const
{
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_edges.hpp
==============================================================================
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_vertices.hpp
==============================================================================
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -0,0 +1,14 @@
+
+#ifndef DIRECTED_TYPES_HPP
+#define DIRECTED_TYPES_HPP
+
+/**
+ * This class is a metafunction that generates all of the types needed to
+ * implement a directed graph.
+ */
+template <typename VertexProps, typename EdgeProps, typename VertexStore, typename EdgeStore>
+class directed_types
+{
+};
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -37,10 +37,10 @@
// The property store metafunction generates the underlying global store
// type for edge properties in undirected graphs.
- template <typename EdgeProps, typename VertexDesc>
+ template <typename EdgeProps>
struct property_store
{
- typedef std::pair<EdgeProps, std::pair<VertexDesc, VertexDesc>> edge;
+ typedef std::pair<EdgeProps, std::pair<incidence_descriptor, incidence_descriptor>> edge;
typedef SecondAlloc<edge> allocator;
typedef property_list<edge, allocator> type;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -44,10 +44,10 @@
// The property store metafunnction generates the global store type for
// undirected graphs. The property list only needs to be a list, not a set.
- template <typename EdgeProps, typename VertexDesc>
+ template <typename EdgeProps>
struct property_store
{
- typedef std::pair<EdgeProps, std::pair<VertexDesc, VertexDesc>> edge;
+ typedef std::pair<EdgeProps, std::pair<incidence_descriptor, incidence_descriptor>> edge;
typedef SecondAlloc<edge> allocator;
typedef property_list<edge, allocator> type;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -51,10 +51,10 @@
// The property store metafunction generates the type of vector used to
// store global properties for undirected graphs.
- template <typename EdgeProps, typename VertexDesc>
+ template <typename EdgeProps>
struct property_store
{
- typedef std::pair<EdgeProps, std::pair<VertexDesc, VertexDesc>> edge;
+ typedef std::pair<EdgeProps, std::pair<incidence_descriptor, incidence_descriptor>> edge;
typedef SecondAlloc<edge> allocator;
typedef property_vector<edge, allocator> type;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -94,19 +94,17 @@
{ return _edges.end(); }
//@}
- /** @name Property Access
- * These functions provide a descriptor-based interface to the property
- * descriptors contained within the edge record. Binding binds the property
- * to an edge stub, and the properties function returns the bound property
- * descriptor.
- */
- //@{
+ /** Bind this incident edge to the given property descriptor. */
inline void bind(incidence_descriptor d, property_descriptor p)
{ make_iterator(_edges, d)->second = p; }
+ /** Return the connected vertex referenced by this edge. */
+ inline vertex_descriptor vertex(incidence_descriptor d) const
+ { return make_iterator(_edges, d)->first; }
+
+ /** Return the property referenced by this edge. */
inline property_descriptor properties(incidence_descriptor d) const
{ return make_iterator(_edges, d)->second; }
- //@}
private:
mutable store_type _edges;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -95,20 +95,17 @@
{ return _edges.end(); }
//@}
- /** @name Property Access
- * These functions provide a descriptor-based interface to the property
- * descriptors contained within the edge record. Binding binds the property
- * to an edge stub, and the properties function returns the bound property
- * descriptor.
- */
- //@{
+ /** Bind this incident edge to the given property. */
inline void bind(incidence_descriptor d, property_descriptor p)
{ make_iterator(_edges, d)->second = p; }
+ /** Return the vertex connected by this edge. */
+ inline vertex_descriptor vertex(incidence_descriptor d) const
+ { return make_iterator(_edges, d)->first; }
+
+ /** Return the properties connected by this edge. */
inline property_descriptor properties(incidence_descriptor d) const
{ return make_iterator(_edges, d)->second; }
- //@}
-
private:
mutable store_type _edges;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -75,20 +75,17 @@
{ return _edges.end(); }
//@}
- /** @name Property Access
- * These functions provide a descriptor-based interface to the property
- * descriptors contained within the edge record. Binding binds the property
- * to an edge stub, and the properties function returns the bound property
- * descriptor.
- */
- //@{
+ /** Bind this edge to the given property. */
inline void bind(incidence_descriptor d, property_descriptor p)
{ make_iterator(_edges, d)->second = p; }
+ /** Return the vertex connected by this edge. */
+ inline vertex_descriptor vertex(incidence_descriptor d) const
+ { return make_iterator(_edges, d)->first; }
+
+ /** Return the properties of this edge. */
inline property_descriptor properties(incidence_descriptor d) const
{ return make_iterator(_edges, d)->second; }
- //@}
-
private:
mutable store_type _edges;
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/mapped_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/mapped_iterator.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
+++ (empty file)
@@ -1,54 +0,0 @@
-
-#ifndef MAPPED_ITERATOR_HPP
-#define MAPPED_ITERATOR_HPP
-
-/**
- * A map iterator adapter that returns references to the mapped edge.
- */
-template <typename Iter>
-struct mapped_iterator
-{
- typedef typename Iter::iterator_category iterator_category;
- typedef typename Iter::difference_type difference_type;
-
- // Deconstruct and reconstruct the value type. Yikes.
- typedef typename Iter::value_type::second_type value_type;
- typedef value_type& reference;
- typedef value_type* pointer;
-
- inline mapped_iterator()
- : iter()
- { }
-
- inline mapped_iterator(Iter x)
- : iter(x)
- { }
-
- inline mapped_iterator& operator++()
- { ++iter; return *this; }
-
- inline mapped_iterator& operator--()
- { --iter; return *this; }
-
- inline bool operator==(mapped_iterator const& x) const
- { return iter == x.iter; }
-
- inline bool operator!=(mapped_iterator const& x) const
- { return !operator==(x); }
-
- inline reference operator*()
- { return iter->second; }
-
- inline const reference operator*() const
- { return iter->second; }
-
- inline pointer operator->()
- { return &iter->second; }
-
- inline const pointer operator->() const
- { return &iter->second; }
-
- Iter iter;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
+++ (empty file)
@@ -1,61 +0,0 @@
-
-#ifndef PLACEHOLDER_HPP
-#define PLACEHOLDER_HPP
-
-#include <algorithm>
-
-#include <boost/static_assert.hpp>
-
-/**
- * The placeholder type is used to allocate a small buffer of memory that can
- * be reinterpreted as a type of the same size. This is used solely as a means
- * of deferring the immediate need for the type of an object if you can guess
- * its size.
- *
- * If you're going to write something hacky, you may as well try to make it a
- * little bit pretty.
- */
-template <int N>
-struct placeholder
-{
- inline placeholder()
- : mem()
- { std::fill(mem, mem + N, 0); }
-
- inline placeholder(placeholder const& x)
- : mem()
- { copy(x.mem, x.mem + N, mem); }
-
- template <typename T>
- inline placeholder(const T& x)
- : mem()
- { put(x); }
-
- /** Put the value of x into the placeholder. */
- template <typename T>
- inline void put(T const& x)
- {
- BOOST_STATIC_ASSERT(sizeof(T) == N);
- char const* p = reinterpret_cast<char const*>(&x);
- copy(p, p + N, mem);
- }
-
- /** Get the value of the placeholder and return it as an object of type T. */
- template <typename T>
- inline T& get() const
- {
- BOOST_STATIC_ASSERT(sizeof(T) == N);
- return *reinterpret_cast<T*>(mem);
- }
-
- mutable char mem[N];
-};
-
-/** A metafunction to make declaring placeholders a little easier. */
-template <typename T>
-struct hold
-{
- typedef placeholder<sizeof(T)> type;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_index.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_index.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
+++ (empty file)
@@ -1,15 +0,0 @@
-
-#ifndef PROPERTY_INDEX_HPP
-#define PROPERTY_INDEX_HPP
-
-// If no edge properties are given, then we can just manufacture
-// indices for edges without actually connecting them to anything.
-// I think. Is there anything that would make this /not/ work?
-
-class property_index
-{
-public:
-};
-
-#endif
-
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -17,6 +17,9 @@
* Because this store is built over a list, but only allows the insertion and
* removal of one element at a time, we do this to optimize calls to the size()
* function (which is used for the number of edges).
+ *
+ * Note that the edge pair is actually a set of descriptors into the incidence
+ * lists of the vertices that reference this edge property.
*/
template <typename Edge, typename Alloc>
class property_list
@@ -71,17 +74,6 @@
--_size;
}
- /** Return the properties referenced by the given descriptor. */
- inline edge_properties& properties(property_descriptor d)
- { return make_iterator(_props, d)->first; }
-
- /**
- * Bind vertex descriptors into the incidence lists into the global
- * property. This is the last step of edge creation for undirected graphs.
- */
- void bind(property_descriptor d, edge_pair const& p)
- { make_iterator(_props, d)->second = p; }
-
/** Return the number of properties. */
inline size_type size() const
{ return _size; }
@@ -99,6 +91,21 @@
{ return _props.end(); }
//@}
+ /**
+ * Bind vertex descriptors into the incidence lists into the global
+ * property. This is the last step of edge creation for undirected graphs.
+ */
+ void bind(property_descriptor d, edge_pair const& p)
+ { make_iterator(_props, d)->second = p; }
+
+ /** Return the incidence descriptors bound to the property. */
+ edge_pair const& ends(property_descriptor d) const
+ { return make_iterator(_props, d)->second; }
+
+ /** Return the properties referenced by the given descriptor. */
+ inline edge_properties& properties(property_descriptor d)
+ { return make_iterator(_props, d)->first; }
+
private:
mutable store_type _props;
size_type _size;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -58,17 +58,6 @@
return make_descriptor(_props, i);
}
- /**
- * Bind vertex descriptors into the incidence lists into the global
- * property. This is the last step of edge creation for undirected graphs.
- */
- void bind(property_descriptor d, edge_pair const& p)
- { make_iterator(_props, d)->second = p; }
-
- /** Return the properties referenced by the given descriptor. */
- inline edge_properties& properties(property_descriptor d)
- { return make_iterator(_props, d)->first; }
-
/** Return the number of properties in the store. */
inline size_type size() const
{ return _props.size(); }
@@ -86,6 +75,21 @@
{ return _props.end(); }
//@}
+ /**
+ * Bind vertex descriptors into the incidence lists into the global
+ * property. This is the last step of edge creation for undirected graphs.
+ */
+ void bind(property_descriptor d, edge_pair const& p)
+ { make_iterator(_props, d)->second = p; }
+
+ /** Return the properties referenced by the given descriptor. */
+ inline edge_properties& properties(property_descriptor d)
+ { return make_iterator(_props, d)->first; }
+
+ /** Return the ends referened by the given descriptor. */
+ inline edge_pair const& ends(property_descriptor d) const
+ { return make_iterator(_props, d)->second; }
+
private:
mutable store_type _props;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -36,6 +36,19 @@
: ends(e), prop(p)
{ }
+ /** @name Descriptor-like Functions
+ * These allow you to treat the edge descriptor like a typical descriptor.
+ * That is, it can be tested for null status (which defers to the property
+ * descriptor).
+ */
+ //@{
+ inline bool is_null() const
+ { return prop.is_null(); }
+
+ inline operator bool() const
+ { return !is_null(); }
+ //@}
+
inline property_descriptor properties() const
{ return prop; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -25,6 +25,7 @@
// Underlying stores
typedef typename types::property_store property_store;
+ typedef typename types::incidence_store incidence_store;
typedef typename types::vertex_store vertex_store;
typedef typename types::vertex_key vertex_key;
typedef typename types::vertex_type vertex_type;
@@ -349,11 +350,11 @@
// Insert algorithm: Try to stub out the edge locally first. If it succeeds,
// then add the global property, and finally bind the incidence and property
- // descitpros into their respective "slots". Note that this is actually
- // faster than the
+ // descitpros into their respective "slots".
insertion_result<incidence_descriptor> first = src.connect(v);
if(first.succeeded()) {
- // Stub the incident edge on the other vertex.
+ // Stub the incident edge on the other vertex. Logically speaking, if
+ // an edge (u, v) can be added, then (v,u) must not exist.
insertion_result<incidence_descriptor> second = tgt.connect(u);
BOOST_ASSERT(second.succeeded());
@@ -361,7 +362,7 @@
property_descriptor p = _props.add(ep);
src.bind(first.value, p);
tgt.bind(second.value, p);
- _props.bind(p, make_pair(u, v));
+ _props.bind(p, make_pair(first.value, second.value));
return edge_descriptor(u, v, p);
}
else if(first.retained()) {
@@ -463,22 +464,23 @@
void
undirected_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
{
- /*
// Grab descriptors out of the edge.
property_descriptor p = e.properties();
- vertex_descriptor u = e.first();
- vertex_descriptor v = e.second();
+ vertex_descriptor u = e.first(), v = e.second();
+ vertex_type &src = _verts.vertex(u), &tgt = _verts.vertex(v);
- // And translate to real data structres.
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
+ // Get incidence iterators from the property and arranging them to match
+ // their owning vertices.
+ incidence_descriptor i = _props.ends(p).first, j = _props.ends(p).second;
+ if(src.connected_vertex(i) == v) {
+ i.swap(j);
+ }
// Disconnect the incidence ends and then remove the property from the
// global property store.
- tgt.disconnect(u, p);
- src.disconnect(v, p);
+ src.disconnect(j);
+ tgt.disconnect(i);
_props.remove(p);
- */
}
/**
@@ -489,30 +491,29 @@
void
undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor v)
{
- /*
- // Disconnecting a vertex is not quite so simple as clearing the incidence
- // set since we have to remove all the edge properties and remove the
- // opposite edges from other vertices.
- // TODO: Can we specialize this at all?
-
vertex_type& src = _verts.vertex(v);
// Start by disconnecting all of the incident edges from adjacent vertices.
incident_edge_range rng = incident_edges(v);
- for( ; rng.first != rng.second; ++rng.first) {
- edge_descriptor e = *rng.first;
- vertex_type& opp = _verts.vertex(e.opposite(v));
- opp.disconnect(v, e.properties());
-
- // Remove all the properties too. Does this make sense here?
+ for(incident_edge_iterator i = rng.first ; i != rng.second; ++i) {
+ edge_descriptor e = *i;
+ vertex_type& tgt = _verts.vertex(e.opposite(v));
+
+ // Get an incidence descriptor into the target into tgt's edge store,
+ // so we can remove the edge record and the properties of the removed
+ // edge.
+ property_descriptor p = e.properties();
+ std::pair<incidence_descriptor, incidence_descriptor> x = _props.ends(p);
+ if(src.connected_vertex(x.first) != v) {
+ x.first.swap(x.second);
+ }
+ tgt.disconnect(x.first);
_props.remove(e.properties());
}
- // Clear the incident edge set of the vertex. We don't do this in the
- // previous loop because we'll probably end up invalidating our own
- // iterators.
+ // Clear the incident edge set of the vertex. We can't do this in the
+ // previous loop because it will invalidate the our iterators.
src.clear();
- */
}
/**
@@ -544,30 +545,40 @@
undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u,
vertex_descriptor v)
{
- /*
// Canonicalize the ordering of vertices first and the get the vertices.
reorder(u, v);
vertex_type& src = _verts.vertex(u);
vertex_type& tgt = _verts.vertex(v);
- // Iterate over the incident edges of the source vertex.
- typename vertex_type::iterator i = src.begin(), end = src.end();
- for( ; i != end; ) {
- vertex_descriptor o = i->first;
- property_descriptor p = i->second;
- // If this is the opposite end of the edge, then we need to remove this
- // from a) the incidence store of the opposite vertex and b) the global
- // edge property.
- if(i->first == v) {
- tgt.disconnect(u, p);
+ // Iterate over the incident edges of the source vertex. If we the edge
+ // (u, *i) is the same as (u, v), then we need to remove that edge. We
+ // also have to cache these iterators and remove them in a second pass.
+ std::vector<incidence_descriptor> iters;
+ incident_edge_range rng = incident_edges(u);
+ for(incident_edge_iterator i = rng.first ; i != rng.second; ++i) {
+ edge_descriptor e = *i;
+ vertex_descriptor o = e.opposite(u);
+ if(o == v) {
+ // Grab descriptors to the property and the incident edge on the
+ // target vertex and remove them,
+ property_descriptor p = e.properties();
+ pair<incidence_descriptor, incidence_descriptor> x = _props.ends(p);
+ if(src.connected_vertex(x.first) == v) {
+ x.first.swap(x.second);
+ }
+ tgt.disconnect(x.first);
_props.remove(p);
- i = src.disconnect(i);
- }
- else {
- ++i;
+
+ // Stash the iterator for the second pass.
+ iters.push_back(x.second);
}
}
- */
+
+ // Second pass: disconnect all of the incident edges from src.
+ typename std::vector<incidence_descriptor>::iterator i, end = iters.end();
+ for(i = iters.begin(); i != end; ++i) {
+ src.disconnect(*i);
+ }
}
/**
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -43,7 +43,7 @@
typedef typename EdgeStore::incidence_descriptor incidence_descriptor;
// Generate the property store and related types.
- typedef typename EdgeStore::template property_store<EdgeProps, vertex_descriptor>::type property_store;
+ typedef typename EdgeStore::template property_store<EdgeProps>::type property_store;
typedef typename property_store::size_type edges_size_type;
// Generate stuff related to edges
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -32,8 +32,13 @@
typedef typename incidence_store::iterator iterator;
typedef typename incidence_store::size_type size_type;
- inline undirected_vertex();
- inline undirected_vertex(vertex_properties const& vp);
+ inline undirected_vertex()
+ : _props(), _edges()
+ { }
+
+ inline undirected_vertex(vertex_properties const& vp)
+ : _props(vp), _edges()
+ { }
/** @name Edge Connection and Disconnection
* These functions control how edges are added to and removed from the
@@ -47,11 +52,8 @@
inline void bind(incidence_descriptor i, property_descriptor p)
{ _edges.bind(i, p); }
- inline void disconnect(vertex_descriptor, property_descriptor)
- { }
-
- inline void disconnect(incidence_descriptor)
- { }
+ inline void disconnect(incidence_descriptor i)
+ { _edges.remove(i); }
//@}
/** Find return an iterator the edge end with the given vertex. */
@@ -62,6 +64,9 @@
inline property_descriptor edge_properties(incidence_descriptor i) const
{ return _edges.properties(i); }
+ inline vertex_descriptor connected_vertex(incidence_descriptor i) const
+ { return _edges.vertex(i) ;}
+
/** @name Property Accessors */
//@{
@@ -70,7 +75,6 @@
inline vertex_properties const& properties() const
{ return _props; }
-
//@}
/** @name Iterators */
@@ -98,21 +102,8 @@
{ return _props < x._props; }
private:
- vertex_properties _props;
- incidence_store _edges;
+ vertex_properties _props;
+ incidence_store _edges;
};
-template <typename VP, typename IS>
-undirected_vertex<VP,IS>::undirected_vertex()
- : _props()
- , _edges()
-{ }
-
-template <typename VP, typename IS>
-undirected_vertex<VP,IS>::undirected_vertex(vertex_properties const& vp)
- : _props(vp)
- , _edges()
-{ }
-
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp 2008-07-09 10:45:45 EDT (Wed, 09 Jul 2008)
@@ -131,8 +131,8 @@
//@}
private:
- store_type _verts;
- size_type _size;
+ mutable store_type _verts;
+ size_type _size;
};
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