|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-11 14:17:36
Author: asutton
Date: 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
New Revision: 47322
URL: http://svn.boost.org/trac/boost/changeset/47322
Log:
Finished implementing and testing graph structures. Added vertex descriptors
into the the slots of property stores to enable the actual generation of edge
descriptors. Now, it takes more room.
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 77 ++++++++++++++++++++++----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 13 ----
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp | 5 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp | 5 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 5 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp | 32 +++++++++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp | 32 +++++++++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 35 +++++++++++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 24 +++++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp | 14 ++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp | 21 ++++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp | 10 +++
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp | 14 ++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 6 ++
sandbox/SOC/2008/graphs/trunk/libs/graphs/README | 6 ++
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 82 +++++++++++++++++++++++++++++++++-
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp | 10 +++
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp | 6 +
sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp | 94 +++++++++++++++++++++++++++++++++++----
21 files changed, 398 insertions(+), 99 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -58,7 +58,7 @@
/** @name Equality Comparable */
//@{
inline bool operator==(directed_edge const& x) const
- { return (ends == x.ends) && (out = x.out); }
+ { return (ends == x.ends) && (out == x.out); }
inline bool operator!=(directed_edge const& x) const
{ return !operator==(x); }
@@ -96,26 +96,54 @@
struct directed_edge_iterator
{
typedef VertexStore vertex_store;
- typedef typename vertex_store::iterator vertex_iterator;
typedef typename vertex_store::vertex_type vertex_type;
+ typedef typename vertex_store::vertex_iterator vertex_iterator;
+
+ typedef typename vertex_type::vertex_descriptor vertex_descriptor;
typedef typename vertex_type::out_iterator edge_iterator;
+ typedef typename vertex_type::out_descriptor out_descriptor;
typedef std::forward_iterator_tag iterator_category;
- typedef typename vertex_iterator::diffeerence_type difference_type;
+ typedef typename vertex_iterator::difference_type difference_type;
typedef Edge value_type;
typedef value_type reference;
typedef value_type pointer;
- // Used to construct the end iterator.
- directed_edge_iterator(vertex_store& store)
- : verts(&store), vert(store.end_vertices()), edge()
+ directed_edge_iterator()
+ : verts(0), vert(), edge()
{ }
- // Used to cosntruct the begin iterator.
- directed_edge_iterator(vertex_store& store, edge_iterator e)
- : verts(&store), vert(store.begin_vertices()), edge(e)
+ directed_edge_iterator(vertex_store& store, vertex_iterator i)
+ : verts(&store)
+ , vert(i)
+ , edge((i == store.end_vertices())
+ ? edge_iterator() // empty out iterator
+ : vertex(*i).begin_out()) // first out iterator of v
{ }
+ /** Return the vertex, given the descriptor. */
+ inline vertex_type& vertex(vertex_descriptor v)
+ { return verts->vertex(v); }
+
+ /** Return the vertex, given the descriptor. */
+ inline vertex_type const& vertex(vertex_descriptor v) const
+ { return verts->vertex(v); }
+
+ /** Return the source vertex of the current edge. */
+ inline vertex_descriptor source() const
+ { return *vert; }
+
+ /** Return the target vertex of the current edge. */
+ inline vertex_descriptor target() const
+ { return edge->first; }
+
+ /**
+ * Return the current out edge by translating the current iterator to a
+ * descriptor
+ */
+ inline out_descriptor out_edge() const
+ { return vertex(*vert).out_edge(edge); }
+
inline directed_edge_iterator& operator++()
{
// If we're not done, increment the current edge. If that increment
@@ -123,34 +151,35 @@
// and reset the edge iterator.
if(vert != verts->end_vertices()) {
++edge;
- if(edge == verts->vertex(*vert).end_out()) {
+ if(edge == vertex(*vert).end_out()) {
+ // Move to the next vertex, resetting the edge iterator.
++vert;
- if(vert != verts->end_vertices()) {
- edge = vert->vertex(*vert).begin_out();
- }
- else {
- edge = edge_iterator();
- }
+ edge = (vert != verts->end_vertices())
+ ? vertex(*vert).begin_out()
+ : edge_iterator();
}
}
return *this;
}
+ inline directed_edge_iterator operator++(int)
+ { directed_edge_iterator x(*this); operator++(); return x; }
+
/** @name Equality Comparable */
//@{
- inline bool operator==(directed_edge_iterator const& x)
- { return edge == x.edge; }
+ inline bool operator==(directed_edge_iterator const& x) const
+ { return (vert == x.vert) && (edge == x.edge); }
- inline bool operator!=(directed_edge_iterator const& x)
- { return edge != x.edge; }
+ inline bool operator!=(directed_edge_iterator const& x) const
+ { return !operator==(x); }
//@}
inline reference operator*() const
- { return *edge; }
+ { return Edge(source(), target(), out_edge()); }
- vertex_store* verts;
- vertex_iterator vert;
- edge_iterator edge;
+ vertex_store* verts;
+ vertex_iterator vert;
+ edge_iterator edge;
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -794,22 +794,13 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_iterator
directed_graph<VP,EP,VS,ES>::begin_edges() const
-{
- // Gotta handle the case where the graph is empty.
- vertex_iterator i = begin_vertices();
- if(i != end_vertices()) {
- return edge_iterator(*this, i, begin_out_edges(*i));
- }
- else {
- return edge_iterator(*this, i);
- }
-}
+{ return edge_iterator(_verts, _verts.begin_vertices()); }
/** Return an iterator past the end of the edges. */
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_iterator
directed_graph<VP,EP,VS,ES>::end_edges() const
-{ return edge_iterator(*this, end_vertices()); }
+{ return edge_iterator(_verts, _verts.end_vertices()); }
/** Return an iterator range over the edges in the graph. */
template <BOOST_GRAPH_DG_PARAMS>
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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -37,10 +37,11 @@
// The property store metafunction generates the underlying global store
// type for edge properties in undirected graphs.
- template <typename EdgeProps>
+ template <typename VertexDesc, typename EdgeProps>
struct property_store
{
- typedef std::pair<EdgeProps, std::pair<incidence_descriptor, incidence_descriptor>> edge;
+ typedef std::pair<VertexDesc, incidence_descriptor> end;
+ typedef std::pair<EdgeProps, std::pair<end, end>> 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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -44,10 +44,11 @@
// 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>
+ template <typename VertexDesc, typename EdgeProps>
struct property_store
{
- typedef std::pair<EdgeProps, std::pair<incidence_descriptor, incidence_descriptor>> edge;
+ typedef std::pair<VertexDesc, incidence_descriptor> end;
+ typedef std::pair<EdgeProps, std::pair<end, end>> 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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -51,10 +51,11 @@
// The property store metafunction generates the type of vector used to
// store global properties for undirected graphs.
- template <typename EdgeProps>
+ template <typename VertexDesc, typename EdgeProps>
struct property_store
{
- typedef std::pair<EdgeProps, std::pair<incidence_descriptor, incidence_descriptor>> edge;
+ typedef std::pair<VertexDesc, incidence_descriptor> end;
+ typedef std::pair<EdgeProps, std::pair<end, end>> edge;
typedef SecondAlloc<edge> allocator;
typedef property_vector<edge, allocator> type;
};
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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -29,7 +29,10 @@
typedef Edge edge_type;
typedef typename Edge::first_type edge_properties;
- typedef typename Edge::second_type edge_pair;
+ typedef typename Edge::second_type end_pair;
+ typedef typename end_pair::first_type end_type; // same as second_type
+ typedef typename end_type::first_type vertex_descriptor;
+ typedef typename end_type::second_type incidence_descriptor;
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
@@ -52,7 +55,7 @@
inline property_descriptor add(edge_properties const& ep)
{
++_size;
- iterator i = _props.insert(_props.end(), make_pair(ep, edge_pair()));
+ iterator i = _props.insert(_props.end(), make_pair(ep, end_pair()));
return make_descriptor(_props, i);
}
//@}
@@ -95,17 +98,38 @@
* 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)
+ void bind(property_descriptor d, end_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
+ inline end_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; }
+ /** Return the first vertex of the edge. */
+ inline vertex_descriptor first_vertex(property_descriptor d) const
+ { return make_iterator(_props, d)->second.first.first; }
+
+ /** Return the second vertex of the edge. */
+ inline vertex_descriptor second_vertex(property_descriptor d) const
+ { return make_iterator(_props, d)->second.second.first; }
+
+ /** Return the first incidence descriptor of the edge. */
+ inline incidence_descriptor first_edge(property_descriptor d) const
+ { return make_iterator(_props, d)->second.first.second; }
+
+ /** Return the second incidence descriptor of the edge. */
+ inline incidence_descriptor second_edge(property_descriptor d) const
+ { return make_iterator(_props, d)->second.second.second; }
+
+
+ /** Return a descriptor for the iterator. */
+ inline property_descriptor describe(iterator i) const
+ { return make_descriptor(_props, i); }
+
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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -21,7 +21,10 @@
typedef Edge edge_type;
typedef typename Edge::first_type edge_properties;
- typedef typename Edge::second_type edge_pair;
+ typedef typename Edge::second_type end_pair;
+ typedef typename end_pair::first_type end_type; // same as second_type
+ typedef typename end_type::first_type vertex_descriptor;
+ typedef typename end_type::second_type incidence_descriptor;
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
@@ -43,7 +46,7 @@
property_descriptor add(edge_properties const& ep)
{
- iterator i = _props.insert(_props.end(), make_pair(ep, edge_pair()));
+ iterator i = _props.insert(_props.end(), make_pair(ep, end_pair()));
return make_descriptor(_props, i);
}
//@}
@@ -79,7 +82,7 @@
* 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)
+ void bind(property_descriptor d, end_pair const& p)
{ make_iterator(_props, d)->second = p; }
/** Return the properties referenced by the given descriptor. */
@@ -87,9 +90,30 @@
{ return make_iterator(_props, d)->first; }
/** Return the ends referened by the given descriptor. */
- inline edge_pair const& ends(property_descriptor d) const
+ inline end_pair const& ends(property_descriptor d) const
{ return make_iterator(_props, d)->second; }
+ /** Return the first vertex of the edge. */
+ inline vertex_descriptor first_vertex(property_descriptor d) const
+ { return ends(d).first.first; }
+
+ /** Return the second vertex of the edge. */
+ inline vertex_descriptor second_vertex(property_descriptor d) const
+ { return ends(d).second.first; }
+
+ /** Return the first incidence descriptor of the edge. */
+ inline incidence_descriptor first_edge(property_descriptor d) const
+ { return ends(d).first.second; }
+
+ /** Return the second incidence descriptor of the edge. */
+ inline incidence_descriptor second_edge(property_descriptor d) const
+ { return ends(d).second.second; }
+
+
+ /** Return a descriptor for the iterator. */
+ inline property_descriptor describe(iterator i) const
+ { return make_descriptor(_props, i); }
+
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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -37,7 +37,7 @@
inline undirected_edge(unordered_pair<vertex_descriptor, vertex_descriptor> const& e, property_descriptor p)
: ends(e), prop(p)
{ }
- //@{
+ //@}
/** @name Descriptor-like Functions
* These allow you to treat the edge descriptor like a typical descriptor.
@@ -122,6 +122,9 @@
struct undirected_edge_iterator
{
typedef typename Store::iterator iterator;
+ typedef typename Store::vertex_descriptor vertex_descriptor;
+ typedef typename Store::incidence_descriptor incidence_descriptor;
+ typedef typename Store::property_descriptor property_descriptor;
typedef typename iterator::iterator_category iterator_category;
typedef typename iterator::difference_type difference_type;
@@ -133,6 +136,10 @@
: store(0), iter()
{ }
+ undirected_edge_iterator(undirected_edge_iterator const& x)
+ : store(x.store), iter(x.iter)
+ { }
+
undirected_edge_iterator(Store& store, iterator i)
: store(&store), iter(i)
{ }
@@ -143,14 +150,36 @@
inline undirected_edge_iterator& operator--()
{ --iter; return *this; }
- inline reference operator*() const
- { return Edge(iter->second, iter->second); }
+ inline undirected_edge_iterator operator++(int)
+ { undirected_edge_iterator x(*this); operator++(); return x; }
+
+ inline undirected_edge_iterator operator--(int)
+ { undirected_edge_iterator x(*this); operator--(); return x; }
+
+ inline undirected_edge_iterator& operator+=(difference_type n)
+ { iter += n; return *this; }
+
+ inline undirected_edge_iterator& operator-=(difference_type n)
+ { iter -= n; return *this; }
+ /** @name Equality Comparable */
+ //@{
inline bool operator==(undirected_edge_iterator const& x) const
{ return iter == x.iter; }
inline bool operator!=(undirected_edge_iterator const& x) const
{ return iter != x.iter; }
+ //@{
+
+ inline difference_type operator-(undirected_edge_iterator x) const
+ { return iter - x.iter; }
+
+ inline reference operator*() const
+ {
+ property_descriptor p = store->describe(iter);
+ return Edge(store->first_vertex(p), store->second_vertex(p), p);
+ }
+
Store* store;
iterator iter;
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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -201,8 +201,8 @@
edge_properties& operator[](edge_descriptor);
//@}
- property_store _props;
- vertex_store _verts;
+ mutable property_store _props;
+ mutable vertex_store _verts;
};
#define BOOST_GRAPH_UG_PARAMS \
@@ -362,11 +362,11 @@
property_descriptor p = _props.add(ep);
src.bind(first.value, p);
tgt.bind(second.value, p);
- _props.bind(p, make_pair(first.value, second.value));
+ _props.bind(p,make_pair(make_pair(u, first.value), make_pair(v, second.value)));
return edge_descriptor(u, v, p);
}
else if(first.retained()) {
- property_descriptor p = src.edge_properties(first.value);
+ property_descriptor p = src.properties(first.value);
return edge_descriptor(u, v, p);
}
else {
@@ -422,7 +422,7 @@
{
reorder(u, v);
vertex_type const& src = _verts.vertex(u);
- incidence_descriptor i = src.find_vertex(v);
+ incidence_descriptor i = src.find(v);
return i ? edge_descriptor(u, v, src.properties(i)) : edge_descriptor();
}
@@ -469,8 +469,8 @@
// 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) {
+ incidence_descriptor i = _props.first_edge(p), j = _props.second_edge(p);
+ if(src.opposite(i) == v) {
i.swap(j);
}
@@ -501,8 +501,9 @@
// 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) {
+ std::pair<incidence_descriptor, incidence_descriptor> x =
+ std::make_pair(_props.first_edge(p), _props.second_edge(p));
+ if(src.opposite(x.first) != v) {
x.first.swap(x.second);
}
tgt.disconnect(x.first);
@@ -560,8 +561,9 @@
// 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) {
+ pair<incidence_descriptor, incidence_descriptor> x =
+ make_pair(_props.first_edge(p), _props.second_edge(p));
+ if(src.opposite(x.first) == v) {
x.first.swap(x.second);
}
tgt.disconnect(x.first);
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-11 14:17:34 EDT (Fri, 11 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>::type property_store;
+ typedef typename EdgeStore::template property_store<vertex_descriptor, 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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -60,10 +60,10 @@
//@}
/** Return the properties of the given incident edge. */
- inline property_descriptor edge_properties(incidence_descriptor i) const
+ inline property_descriptor properties(incidence_descriptor i) const
{ return _edges.properties(i); }
- inline vertex_descriptor connected_vertex(incidence_descriptor i) const
+ inline vertex_descriptor opposite(incidence_descriptor i) const
{ return _edges.vertex(i) ;}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -5,7 +5,9 @@
#include <boost/descriptors.hpp>
/**
- * A simple vertex iterator for any underlying store.
+ * A simple vertex iterator for any underlying store. These iterators must
+ * cache references to the originating container because these dereference to
+ * descriptors.
*/
template <typename Container>
class basic_vertex_iterator
@@ -26,7 +28,7 @@
{ }
inline basic_vertex_iterator(Container& c, iterator x)
- : cont(c), iter(x)
+ : cont(&c), iter(x)
{ }
// Assignment and increment
@@ -42,6 +44,12 @@
inline basic_vertex_iterator& operator--()
{ --iter; return *this; }
+ inline basic_vertex_iterator operator++(int)
+ { basic_vertex_iterator x(*this); ++iter; return x; }
+
+ inline basic_vertex_iterator operator--(int)
+ { basic_vertex_iterator x(*this); --iter; return x; }
+
inline basic_vertex_iterator operator+(difference_type n) const
{ return indexed_basic_vertex_iterator(cont, iter + n); }
@@ -51,7 +59,7 @@
inline difference_type operator-(basic_vertex_iterator const& x) const
{ return iter - x.iter; }
- inline reference operator*()
+ inline reference operator*() const
{ return make_descriptor(*cont, iter); }
inline bool operator==(basic_vertex_iterator const& x) const
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-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -100,16 +100,25 @@
inline size_type size() const
{ return _size; }
- /** @name Vertex Iterators */
+ /** @name Vertex Iterators
+ * There are two sets of iterators here: those that provide iterators that
+ * dereference as descriptors and those that dereference as vertices.
+ */
//@{
- vertex_iterator begin_vertices() const
- { return _verts.begin(); }
+ inline vertex_iterator begin_vertices() const
+ { return vertex_iterator(_verts, _verts.begin()); }
- vertex_iterator end_vertices() const
- { return _verts.end(); }
+ inline vertex_iterator end_vertices() const
+ { return vertex_iterator(_verts, _verts.end()); }
- vertex_range vertices() const
+ inline vertex_range vertices() const
{ return std::make_pair(begin_vertices(), end_vertices()); }
+
+ inline iterator begin() const
+ { return _verts.begin(); }
+
+ inline iterator end() const
+ { return _verts.end(); }
//@}
/** @name Vertex Accessors */
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -111,13 +111,19 @@
/** @name Vertex Iteration */
//@{
inline vertex_iterator begin_vertices() const
- { return _verts.begin(); }
+ { return vertex_iterator(_verts, _verts.begin()); }
inline vertex_iterator end_vertices() const
- { return _verts.end(); }
+ { return vertex_iterator(_verts, _verts.end()); }
vertex_range vertices() const
{ return std::make_pair(begin_vertices(), end_vertices()); }
+
+ inline iterator begin() const
+ { return _verts.begin(); }
+
+ inline iterator end() const
+ { return _verts.end(); }
//@}
/** @name Vertex and Key Accessors */
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -109,14 +109,20 @@
/** @name Vertex Iteration */
//@{
- vertex_iterator begin_vertices() const
- { return _verts.begin(); }
+ inline vertex_iterator begin_vertices() const
+ { return vertex_iterator(_verts, _verts.begin()); }
- vertex_iterator end_vertices() const
- { return _verts.end(); }
+ inline vertex_iterator end_vertices() const
+ { return vertex_iterator(_verts, _verts.end()); }
vertex_range vertices() const
{ return std::make_pair(begin_vertices(), end_vertices()); }
+
+ inline iterator begin() const
+ { return _verts.begin(); }
+
+ inline iterator end() const
+ { return _verts.end(); }
//@}
/** @name Vertex Accessors */
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -115,6 +115,12 @@
vertex_range vertices() const
{ return std::make_pair(begin_vertices(), end_vertices()); }
+
+ inline typename store_type::iterator begin() const
+ { return _verts.begin(); }
+
+ inline iterator end() const
+ { return _verts.end(); }
//@}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/README
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/README (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/README 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -23,6 +23,12 @@
me). There is nothing to stop programmers from building these alternative
implementations - they're good projects.
+Update:
+I've expanded the number of descriptors in the property store to incldue the
+vertex descriptors for which the incidence descriptors are incident. It sucks,
+but there's just not much I can do about it since there's other way to get the
+vertices out of the property store.
+
Q: Why are the property list and vector different types when their
implementations are nearly identical.
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -196,6 +196,7 @@
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
+ cout << " * implicit disconnect" << endl;
g.remove_vertex(V[1]);
BOOST_ASSERT(g.num_vertices() == 2);
BOOST_ASSERT(g.degree(V[0]) == 1);
@@ -247,6 +248,72 @@
}
template <typename Graph>
+void test_edge()
+{
+ Graph g;
+ vector<typename Graph::vertex_descriptor> V;
+ list<typename Graph::edge_descriptor> E;
+ for(int i = 0; i < 3; ++i) {
+ V.push_back(g.add_vertex(i));
+ }
+ g.add_edge(V[0], V[1]);
+ g.add_edge(V[1], V[2]);
+ g.add_edge(V[2], V[0]);
+ BOOST_ASSERT(g.num_vertices() == 3);
+ BOOST_ASSERT(g.num_edges() == 3);
+
+ cout << " * find edges" << endl;
+ // Test for existence
+ BOOST_ASSERT(g.edge(V[0], V[1]));
+ BOOST_ASSERT(g.edge(V[1], V[2]));
+ BOOST_ASSERT(g.edge(V[2], V[0]));
+
+ // Test for inexstence
+ BOOST_ASSERT(!g.edge(V[1], V[0]));
+ BOOST_ASSERT(!g.edge(V[2], V[1]));
+ BOOST_ASSERT(!g.edge(V[0], V[2]));
+}
+
+template <typename Graph>
+void test_vertex_iterator()
+{
+ Graph g;
+ vector<typename Graph::vertex_descriptor> V;
+ list<typename Graph::edge_descriptor> E;
+ for(int i = 0; i < 3; ++i) {
+ V.push_back(g.add_vertex(i));
+ }
+
+ cout << " * testing vertex iterator" << endl;
+ typename Graph::vertex_range rng = g.vertices();
+ BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+ BOOST_ASSERT(*rng.first++ == V[0]);
+ BOOST_ASSERT(*rng.first++ == V[1]);
+ BOOST_ASSERT(*rng.first++ == V[2]);
+}
+
+template <typename Graph>
+void test_edge_iterator()
+{
+ Graph g;
+ vector<typename Graph::vertex_descriptor> V;
+ vector<typename Graph::edge_descriptor> E;
+ for(int i = 0; i < 3; ++i) {
+ V.push_back(g.add_vertex(i));
+ }
+ E.push_back(g.add_edge(V[0], V[1]));
+ E.push_back(g.add_edge(V[1], V[2]));
+ E.push_back(g.add_edge(V[2], V[0]));
+
+ cout << " * testing edge iterator" << endl;
+ typename Graph::edge_range rng = g.edges();
+ BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+ BOOST_ASSERT(*rng.first++ == E[0]);
+ BOOST_ASSERT(*rng.first++ == E[1]);
+ BOOST_ASSERT(*rng.first++ == E[2]);
+}
+
+template <typename Graph>
void test_incidence_iterator()
{
Graph g;
@@ -257,6 +324,7 @@
g.add_edge(u, v, 3);
g.add_edge(v, u, 4);
+ cout << " * testing incident edges" << endl;
typename Graph::incident_edge_range rng = g.incident_edges(u);
for( ; rng.first != rng.second; ++rng.first) {
typename Graph::edge_descriptor e = *rng.first;
@@ -277,6 +345,7 @@
g.add_edge(u, v, 3);
g.add_edge(v, u, 4);
+ cout << " * testing adjacent vertices" << endl;
typename Graph::adjacent_vertex_range rng = g.adjacent_vertices(u);
for( ; rng.first != rng.second; ++rng.first) {
BOOST_ASSERT(*rng.first == v);
@@ -299,10 +368,11 @@
test_add_vertices<Graph>();
test_add_edges<Graph>();
test_add_multi_edges<Graph>();
- /*
+ test_edge<Graph>();
+ test_vertex_iterator<Graph>();
+ test_edge_iterator<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
- */
}
void list_list()
@@ -315,10 +385,11 @@
test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
test_remove_multi_edges<Graph>();
- /*
+ test_edge<Graph>();
+ test_vertex_iterator<Graph>();
+ test_edge_iterator<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
- */
}
@@ -332,6 +403,9 @@
test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
test_remove_multi_edges<Graph>();
+ test_edge<Graph>();
+ test_vertex_iterator<Graph>();
+ test_edge_iterator<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -40,6 +40,7 @@
template <typename Props, typename Incs, typename Vertex, typename Edge>
void undirected_add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep)
{
+/*
typedef typename Props::property_descriptor PropDesc;
typedef typename Incs::incidence_descriptor IncDesc;
typedef insertion_result<IncDesc> Result;
@@ -53,7 +54,7 @@
// 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
+ // faster than the
Result r = incs.add(v);
if(r.succeeded()) {
PropDesc p = props.add(ep);
@@ -71,6 +72,7 @@
else {
cout << " * failed " << u << "," << v << endl;
}
+*/
}
template <typename Outs, typename Ins>
@@ -148,7 +150,7 @@
// Instantiate data structures related to the storage of edges and their
// properties.
- typedef typename EdgeStore::template property_store<EdgeProps>::type PropStore;
+ typedef typename EdgeStore::template property_store<VertexDesc, EdgeProps>::type PropStore;
typedef typename EdgeStore::template incidence_store<VertexDesc>::type IncStore;
PropStore props;
@@ -157,6 +159,10 @@
cout << " * " << typestr(properties_category(props)) << endl;
cout << " * " << typestr(incidence_category(incs)) << endl;
+ cout << typestr<typename PropStore::vertex_descriptor>() << endl;
+ cout << typestr<typename PropStore::incidence_descriptor>() << endl;
+
+
undirected_add_edges(props, incs);
}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -13,6 +13,7 @@
typedef int EdgeProperties;
typedef descriptor_traits<std::list<int>>::descriptor_type IncDesc;
+typedef descriptor_traits<std::list<int>>::descriptor_type VertexDesc;
template <typename PropSet>
void test_remove(PropSet& props, stable_mutators_tag)
@@ -48,8 +49,9 @@
int main()
{
- typedef pair<IncDesc, IncDesc> EdgePair;
- typedef pair<EdgeProperties, EdgePair> StoredEdge;
+ typedef pair<VertexDesc, IncDesc> End;
+ typedef pair<End, End> EndPair;
+ typedef pair<EdgeProperties, EndPair> StoredEdge;
typedef allocator<StoredEdge> Allocator;
test<property_vector<StoredEdge, Allocator>>();
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp 2008-07-11 14:17:34 EDT (Fri, 11 Jul 2008)
@@ -126,6 +126,7 @@
template <typename Graph>
void test_disconnect_vertex()
{
+ cout << " * disconnecting vertex" << std::endl;
Graph g;
vector<typename Graph::vertex_descriptor> V;
list<typename Graph::edge_descriptor> E;
@@ -138,7 +139,6 @@
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
- cout << " * disconnecting vertex" << std::endl;
g.remove_edges(V[1]);
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.degree(V[1]) == 0);
@@ -151,6 +151,7 @@
template <typename Graph>
void test_implicit_disconnect_vertex()
{
+ cout << " * removing conntected vertex" << endl;
Graph g;
vector<typename Graph::vertex_descriptor> V;
list<typename Graph::edge_descriptor> E;
@@ -163,7 +164,6 @@
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
- cout << " * removing conntected vertex" << endl;
g.remove_vertex(V[1]);
BOOST_ASSERT(g.num_vertices() == 2);
BOOST_ASSERT(g.degree(V[0]) == 1);
@@ -173,16 +173,14 @@
template <typename Graph>
void test_add_multi_edges()
{
- Graph g;
-
cout << " * adding parallel edges" << endl;
+ Graph g;
typename Graph::vertex_descriptor u = g.add_vertex(1);
typename Graph::vertex_descriptor v = g.add_vertex(2);
- g.add_edge(u, v);
- g.add_edge(v, u);
- g.add_edge(u, v);
- g.add_edge(v, u);
-
+ g.add_edge(u, v, 10);
+ g.add_edge(v, u, 20);
+ g.add_edge(u, v, 30);
+ g.add_edge(v, u, 40);
BOOST_ASSERT(g.num_vertices() == 2);
// If there are no parallel edges, then there should only be one edge.
@@ -197,6 +195,7 @@
template <typename Graph>
void test_remove_multi_edges()
{
+ cout << " * removing parallel edges" << endl;
Graph g;
typename Graph::vertex_descriptor u = g.add_vertex(1);
typename Graph::vertex_descriptor v = g.add_vertex(2);
@@ -205,13 +204,79 @@
g.add_edge(u, v);
g.add_edge(v, u);
- cout << " * removing parallel edges" << endl;
g.remove_edges(u, v);
BOOST_ASSERT(g.num_edges() == 0);
BOOST_ASSERT(g.degree(u) == 0);
BOOST_ASSERT(g.degree(v) == 0);
}
+
+template <typename Graph>
+void test_edge()
+{
+ cout << " * find edges" << endl;
+ Graph g;
+ vector<typename Graph::vertex_descriptor> V;
+ list<typename Graph::edge_descriptor> E;
+ for(int i = 0; i < 3; ++i) {
+ V.push_back(g.add_vertex(i));
+ }
+ g.add_edge(V[0], V[1]);
+ g.add_edge(V[1], V[2]);
+ BOOST_ASSERT(g.num_vertices() == 3);
+ BOOST_ASSERT(g.num_edges() == 2);
+
+ // Test for existence
+ BOOST_ASSERT(g.edge(V[0], V[1]));
+ BOOST_ASSERT(g.edge(V[1], V[0]));
+ BOOST_ASSERT(g.edge(V[1], V[2]));
+ BOOST_ASSERT(g.edge(V[2], V[1]));
+
+ // Test for inexstence
+ BOOST_ASSERT(!g.edge(V[0], V[2]));
+ BOOST_ASSERT(!g.edge(V[2], V[0]));
+}
+
+template <typename Graph>
+void test_vertex_iterator()
+{
+ Graph g;
+ vector<typename Graph::vertex_descriptor> V;
+ list<typename Graph::edge_descriptor> E;
+ for(int i = 0; i < 3; ++i) {
+ V.push_back(g.add_vertex(i));
+ }
+
+ cout << " * testing vertex iterator" << endl;
+ typename Graph::vertex_range rng = g.vertices();
+ BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+ BOOST_ASSERT(*rng.first++ == V[0]);
+ BOOST_ASSERT(*rng.first++ == V[1]);
+ BOOST_ASSERT(*rng.first++ == V[2]);
+}
+
+template <typename Graph>
+void test_edge_iterator()
+{
+ Graph g;
+ vector<typename Graph::vertex_descriptor> V;
+ vector<typename Graph::edge_descriptor> E;
+ for(int i = 0; i < 3; ++i) {
+ V.push_back(g.add_vertex(i));
+ }
+ E.push_back(g.add_edge(V[0], V[1], 10));
+ E.push_back(g.add_edge(V[1], V[2], 20));
+ E.push_back(g.add_edge(V[2], V[0], 30));
+
+ cout << " * testing edge iterator" << endl;
+
+ typename Graph::edge_range rng = g.edges();
+ BOOST_ASSERT(distance(rng.first, rng.second) == 3);
+ BOOST_ASSERT(*rng.first++ == E[0]);
+ BOOST_ASSERT(*rng.first++ == E[1]);
+ BOOST_ASSERT(*rng.first++ == E[2]);
+}
+
template <typename Graph>
void test_incidence_iterator()
{
@@ -266,6 +331,9 @@
test_add_vertices<Graph>();
test_add_edges<Graph>();
test_add_multi_edges<Graph>();
+ test_edge<Graph>();
+ test_vertex_iterator<Graph>();
+ test_edge_iterator<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
}
@@ -280,6 +348,9 @@
test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
test_remove_multi_edges<Graph>();
+ test_edge<Graph>();
+ test_vertex_iterator<Graph>();
+ test_edge_iterator<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
}
@@ -295,6 +366,9 @@
test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
test_remove_multi_edges<Graph>();
+ test_edge<Graph>();
+ test_vertex_iterator<Graph>();
+ test_edge_iterator<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
}
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