|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-11 09:59:02
Author: asutton
Date: 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
New Revision: 47310
URL: http://svn.boost.org/trac/boost/changeset/47310
Log:
Mostly finished reimplementing the directed graphs. Mostly went as exected,
but had to make the out iterator reference the undelying vertex types because
I can't translate between iterators and descriptors without a container. It's
a little overhead, but won't kill anything.
Add incidence and adjacency iterators for directed graphs to add interface
parity/symmetry with undirected graphs.
Changed the interface to the edge() test functions to simply return an
edge descriptor. These can be tested for null-ness, so we don't need a
pair with a bool.
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 206 +++++++++++++++++++++++++++------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp | 11 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 33 ++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp | 12 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp | 12 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp | 21 ++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp | 40 +++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp | 6
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp | 4
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 18 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp | 6
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 69 ++++++++++---
sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp | 6
15 files changed, 329 insertions(+), 121 deletions(-)
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 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -68,10 +68,10 @@
typedef typename types::out_edge_range out_edge_range;
typedef typename types::in_edge_iterator in_edge_iterator;
typedef typename types::in_edge_range in_edge_range;
- // typedef typename types::incident_edge_iterator incident_edge_iterator;
- // typedef typename types::incident_edge_range incident_edge_range;
- // typedef typename types::adjacent_vertex_iterator adjacent_vertex_iterator;
- // typedef typename types::adjacent_vertex_range adjacent_vertex_range;
+ typedef typename types::incident_edge_iterator incident_edge_iterator;
+ typedef typename types::incident_edge_range incident_edge_range;
+ typedef typename types::adjacent_vertex_iterator adjacent_vertex_iterator;
+ typedef typename types::adjacent_vertex_range adjacent_vertex_range;
// Sizes for vertices, and degree.
typedef typename types::vertices_size_type vertices_size_type;
@@ -170,9 +170,9 @@
* convenience overloads that depend on the type of vertex store.
*/
//@{
- std::pair<edge_descriptor, bool> edge(vertex_descriptor, vertex_descriptor);
- std::pair<edge_descriptor, bool> edge(vertex_properties const&, vertex_properties const&);
- std::pair<edge_descriptor, bool> edge(vertex_key const&, vertex_key const&);
+ edge_descriptor edge(vertex_descriptor, vertex_descriptor) const;
+ edge_descriptor edge(vertex_properties const&, vertex_properties const&) const;
+ edge_descriptor edge(vertex_key const&, vertex_key const&) const;
//@}
/** @name Remove Edge(s)
@@ -231,6 +231,14 @@
in_edge_iterator begin_in_edges(vertex_descriptor) const;
in_edge_iterator end_in_edges(vertex_descriptor) const;
in_edge_range in_edges(vertex_descriptor) const;
+
+ incident_edge_iterator begin_incident_edges(vertex_descriptor) const;
+ incident_edge_iterator end_incident_edges(vertex_descriptor) const;
+ incident_edge_range incident_edges(vertex_descriptor) const;
+
+ adjacent_vertex_iterator begin_adjacent_vertices(vertex_descriptor) const;
+ adjacent_vertex_iterator end_adjacent_vertices(vertex_descriptor) const;
+ adjacent_vertex_range adjacent_vertices(vertex_descriptor) const;
//@}
/** @name Property Accessors
@@ -242,8 +250,8 @@
//@}
private:
- vertex_store _verts;
- edges_size_type _edges;
+ mutable vertex_store _verts;
+ edges_size_type _edges;
};
#define BOOST_GRAPH_DG_PARAMS \
@@ -465,13 +473,18 @@
void
directed_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
{
- // Removing the edge involves the removal of both parts from the two
- // connected vertices. We have to disconnect the source first because that
- // will /not/ erase the edge's iterator.
+ // Grab the vertices in question
vertex_type& src = _verts.vertex(e.source());
vertex_type& tgt = _verts.vertex(e.target());
- tgt.disconnect_source(e);
- src.disconnect_target(e);
+
+ // Grab the in and out descriptors corresponding to the out edge and its
+ // reverse in edge.
+ out_descriptor o = e.out_edge();
+ in_descriptor i = src.in_edge(o);
+
+ // And disconnect them.
+ src.disconnect_target(o);
+ tgt.disconnect_source(i);
}
/**
@@ -518,18 +531,24 @@
void
directed_graph<VP,EP,VS,ES>::remove_out_edges(vertex_descriptor v)
{
- // Basically, just iterate over the out edges of v and remove all of the
- // incoming parts of each out edge. Don't forget to drop the edge count.
- out_edge_range out = out_edges(v);
- for( ; out.first != out.second; ++out.first) {
- edge_descriptor e = *out.first;
+ vertex_type& src = _verts.vertex(v);
+
+ // Iterate over the out edges of v and remove all of the incoming parts of
+ // each out edge and decrement the edge count.
+ out_edge_range rng = out_edges(v);
+ for( ; rng.first != rng.second; ++rng.first) {
+ edge_descriptor e = *rng.first;
+ out_descriptor o = e.out_edge();
+ in_descriptor i = src.in_edge(o);
+
+ // Disconnect the vertices.
vertex_type& tgt = _verts.vertex(e.target());
- tgt.disconnect_source(e);
- --_edges;
+ tgt.disconnect_source(i);
}
// Clear the out edges.
- _verts.vertex(v).clear_out();
+ _edges -= src.out_degree();
+ src.clear_out();
}
/**
@@ -562,18 +581,21 @@
void
directed_graph<VP,EP,VS,ES>::remove_in_edges(vertex_descriptor v)
{
- // we have to disconnect the source of the opposite edge. Don't forget to
- // drop the edge count.
- in_edge_range in = in_edges(v);
- for( ; in.first != in.second; ++in.first) {
- edge_descriptor e = *in.first;
+ vertex_type& tgt = _verts.vertex(v);
+
+ // Remove all in edges from v, making v a source vertex (all out, no in).
+ // The edge is actually removed from the source of the in edges of this
+ // vertex.
+ in_edge_range rng = in_edges(v);
+ for( ; rng.first != rng.second; ++rng.first) {
+ edge_descriptor e = *rng.first;
vertex_type& src = _verts.vertex(e.source());
- src.disconnect_target(e);
- --_edges;
+ src.disconnect_target(e.out_edge());
}
// Clear out the vertices lists.
- _verts.vertex(v).clear_in();
+ _edges -= tgt.in_degree();
+ tgt.clear_in();
}
/**
@@ -613,22 +635,29 @@
vertex_type& src = _verts.vertex(u);
vertex_type& tgt = _verts.vertex(v);
- // Iterate over the out edges of the source, removing them.
+ // Iterate over the out edges of the source, storing out edges for
+ // subsequent removal and actually removing in edges.
+ std::vector<out_descriptor> outs;
out_edge_range rng = out_edges(u);
- for(out_edge_iterator i = rng.first ; i != rng.second; ) {
- // If the target vertex is one that we want to remove, remove it from
- // the out list of this vertex. Also, brute-force remove it from the
- // in list of other vertex.
+ for(out_edge_iterator i = rng.first ; i != rng.second; ++i) {
+ // If the target vertex is one that we want to remove, remove the in
+ // edge from the target and stash the out edge for subsequent removal
+ // in a second pass.
edge_descriptor e = *i;
- if(v == e.target()) {
- tgt.disconnect_source(e.in_edge());
- i = out_edge_iterator(u, src.disconnect_target(e.out_edge()));
- --_edges;
- }
- else {
- ++i;
+ if(e.target() == v) {
+ out_descriptor o = e.out_edge();
+ in_descriptor i = src.in_edge(e.out_edge());
+ tgt.disconnect_source(i);
+ outs.push_back(o);
}
}
+
+ // Second pass: remove all the out edge descriptors and decrement the count.
+ typename std::vector<out_descriptor>::iterator i, end = outs.end();
+ for(i = outs.begin(); i != end; ++i) {
+ src.disconnect_target(*i);
+ --_edges;
+ }
}
template <BOOST_GRAPH_DG_PARAMS>
@@ -656,14 +685,12 @@
* @todo Consider making descriptors "self-invalidating".
*/
template <BOOST_GRAPH_DG_PARAMS>
-std::pair<typename directed_graph<VP,EP,VS,ES>::edge_descriptor, bool>
-directed_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v)
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
+directed_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v) const
{
vertex_type& src = _verts.vertex(u);
- typename vertex_type::out_iterator i = src.find_out(v);
- return i != src.end_out() ?
- std::make_pair(edge_descriptor(u, i), true) :
- std::make_pair(edge_descriptor(), false);
+ out_descriptor o = src.find_target(v);
+ return o ? edge_descriptor(u, v, o) : edge_descriptor();
}
/**
@@ -673,9 +700,9 @@
* exists or not. This is equivalent to edge(find_vertex(u), find_vertex(v)).
*/
template <BOOST_GRAPH_DG_PARAMS>
-std::pair<typename directed_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
directed_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
- vertex_properties const& v)
+ vertex_properties const& v) const
{
return edge(find_vertex(u), find_vertex(v));
}
@@ -686,9 +713,9 @@
* exists or not. This is equivalent to edge(find_vertex(u), find_vertex(v)).
*/
template <BOOST_GRAPH_DG_PARAMS>
-std::pair<typename directed_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
directed_graph<VP,EP,VS,ES>::edge(vertex_key const& u,
- vertex_key const& v)
+ vertex_key const& v) const
{
return edge(find_vertex(u), find_vertex(v));
}
@@ -794,7 +821,10 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::out_edge_iterator
directed_graph<VP,EP,VS,ES>::begin_out_edges(vertex_descriptor v) const
-{ return out_edge_iterator(v, _verts.vertex(v).begin_out()); }
+{
+ vertex_type& vert = _verts.vertex(v);
+ return out_edge_iterator(vert, v, vert.begin_out());
+}
/**
* Return an iterator past the end of then out edges of the given vertex.
@@ -803,7 +833,8 @@
typename directed_graph<VP,EP,VS,ES>::out_edge_iterator
directed_graph<VP,EP,VS,ES>::end_out_edges(vertex_descriptor v) const
{
- return out_edge_iterator(v, _verts.vertex(v).end_out());
+ vertex_type& vert = _verts.vertex(v);
+ return out_edge_iterator(vert, v, vert.end_out());
}
/**
@@ -832,9 +863,7 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::in_edge_iterator
directed_graph<VP,EP,VS,ES>::end_in_edges(vertex_descriptor v) const
-{
- return in_edge_iterator(v, _verts.vertex(v).end_in());
-}
+{ return in_edge_iterator(v, _verts.vertex(v).end_in()); }
/**
* Return an iterator range over the in edges of the given vertex.
@@ -842,9 +871,58 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::in_edge_range
directed_graph<VP,EP,VS,ES>::in_edges(vertex_descriptor v) const
-{
- return std::make_pair(begin_in_edges(v), end_in_edges(v));
-}
+{ return std::make_pair(begin_in_edges(v), end_in_edges(v)); }
+
+/**
+ * Return an iterator to the first incident edge of the given vertex. This is
+ * an alias for begin_out_edges(v).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::incident_edge_iterator
+directed_graph<VP,EP,VS,ES>::begin_incident_edges(vertex_descriptor v) const
+{ return begin_out_edges(v); }
+
+/**
+ * Return an iterator past the end of the incident edges of the given vertex.
+ * This is an alias for end_out_edges(v).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::incident_edge_iterator
+directed_graph<VP,EP,VS,ES>::end_incident_edges(vertex_descriptor v) const
+{ return end_out_edges(v); }
+
+/**
+ * Return an iterator range over the incident edges of the given vertex. This
+ * is an alias for out_edges(v).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::incident_edge_range
+directed_graph<VP,EP,VS,ES>::incident_edges(vertex_descriptor v) const
+{ return out_edges(v); }
+
+/**
+ * Return an iterator to the first adjacent vertex of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
+directed_graph<VP,EP,VS,ES>::begin_adjacent_vertices(vertex_descriptor v) const
+{ return adjacent_vertex_iterator(begin_incident_edges(v)); }
+
+/**
+ * Return an iterator past the end of the adjacent vertices of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
+directed_graph<VP,EP,VS,ES>::end_adjacent_vertices(vertex_descriptor v) const
+{ return adjacent_vertex_iterator(end_incident_edges(v)); }
+
+/**
+ * Return an iterator range over the adjacent vertices of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::adjacent_vertex_range
+directed_graph<VP,EP,VS,ES>::adjacent_vertices(vertex_descriptor v) const
+{ return std::make_pair(begin_adjacent_vertices(v), end_adjacent_vertices(v)); }
/**
* Return the properties for the given vertex.
@@ -852,9 +930,7 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::vertex_properties&
directed_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v)
-{
- return _verts.properties(v);
-}
+{ return _verts.properties(v); }
/**
* Return the properties for the given edge.
@@ -862,9 +938,7 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_properties&
directed_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
-{
- return e.properties();
-}
+{ return e.properties(); }
#undef BOOST_GRAPH_DG_PARAMS
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -67,12 +67,21 @@
typedef typename VertexStore::key_type vertex_key;
// Generate a bunch of iterators
- typedef basic_out_iterator<out_store, edge_descriptor> out_edge_iterator;
+ typedef basic_out_iterator<vertex_type, edge_descriptor> out_edge_iterator;
typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
typedef basic_in_iterator<typename in_store::iterator, edge_descriptor> in_edge_iterator;
typedef std::pair<in_edge_iterator, in_edge_iterator> in_edge_range;
typedef directed_edge_iterator<vertex_store, edge_descriptor> edge_iterator;
typedef std::pair<edge_iterator, edge_iterator> edge_range;
+
+ // Generate incident edge iterators as out edge iterators - not a
+ // combination of in and out edges.
+ typedef out_edge_iterator incident_edge_iterator;
+ typedef out_edge_range incident_edge_range;
+
+ // Generate adjacent vertx iterators over the incidence iterator
+ typedef adjacency_iterator<incident_edge_iterator> adjacent_vertex_iterator;
+ typedef std::pair<adjacent_vertex_iterator, adjacent_vertex_iterator> adjacent_vertex_range;
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -40,7 +40,10 @@
/** @name Edge Connection and Disconnection
* These functions provide an interface to the in and out stores of the
- * vertex.
+ * vertex. The connection of this vertex to a target is a two-phase
+ * operation. First, the connection is made to the target and vice-versa
+ * from the source. Then, the target is bound with the in edge descriptor
+ * of the source.
*/
//@{
insertion_result<out_descriptor> connect_target(vertex_descriptor v, edge_properties const& ep)
@@ -52,6 +55,17 @@
void bind_target(out_descriptor o, in_descriptor i)
{ _out.bind(o, i); }
+ void disconnect_target(out_descriptor o)
+ { _out.remove(o); }
+
+ void disconnect_source(in_descriptor i)
+ { _in.remove(i); }
+
+ /** Find the (at least one?) out edge connected to the given vertex. */
+ out_descriptor find_target(vertex_descriptor v)
+ { return _out.find(v); }
+ //@}
+
/** @name Property Accessors */
//@{
inline vertex_properties& properties()
@@ -61,6 +75,23 @@
{ return _props; }
//@}
+ /** Return the reverse out descriptor for the given in edge. */
+ inline out_descriptor out_edge(in_descriptor i) const
+ { return _in.out_edge(i); }
+
+ /** Return the reverse in descriptor for the given out edge. */
+ inline in_descriptor in_edge(out_descriptor o) const
+ { return _out.in_edge(o); }
+
+
+ /** Return a descriptor for the iterator into the underlying container. */
+ inline out_descriptor out_edge(out_iterator o) const
+ { return _out.out_edge(o) ;}
+
+ /** Return a descriptor for the iterator into the underlying container */
+ inline in_descriptor in_edge(in_iterator i) const
+ { return _in.in_edge(i); }
+
/** @name Out Edges */
//@{
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -56,7 +56,7 @@
{ return iter != x.iter; }
inline reference operator*() const
- { return Edge(source(), target(), iter->second()); }
+ { return Edge(source(), target(), iter->second); }
vertex_descriptor tgt;
iterator iter;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -88,6 +88,18 @@
{ return _edges.end(); }
//@}
+ /** Return the source vertex of the in edge. */
+ inline vertex_descriptor source(in_descriptor i) const
+ { return make_iterator(_edges, i)->first; }
+
+ /** Return the reverse edge descriptor bound to the in edge. */
+ inline out_descriptor out_edge(in_descriptor i) const
+ { return make_iterator(_edges, i)->second; }
+
+ /** Return a desecriptor for an iterator into this object. */
+ inline in_descriptor in_edge(iterator i) const
+ { return make_descriptor(_edges, i); }
+
private:
mutable store_type _edges;
size_type _size;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -76,6 +76,18 @@
{ return _edges.end(); }
//@}
+ /** Return the source vertex of the in edge. */
+ inline vertex_descriptor source(in_descriptor i) const
+ { return make_iterator(_edges, i)->first; }
+
+ /** Return the reverse edge descriptor bound to the in edge. */
+ inline out_descriptor out_edge(in_descriptor i) const
+ { return make_iterator(_edges, i)->second; }
+
+ /** Return a desecriptor for an iterator into this object. */
+ inline in_descriptor in_edge(iterator i) const
+ { return make_descriptor(_edges, i); }
+
private:
mutable store_type _edges;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -61,6 +61,27 @@
inline bool empty() const
{ return _edges.empty(); }
+ /** @name Iterators */
+ //@{
+ inline iterator begin() const
+ { return _edges.begin(); }
+
+ inline iterator end() const
+ { return _edges.end(); }
+ //@}
+
+ /** Return the source vertex of the in edge. */
+ inline vertex_descriptor source(in_descriptor i) const
+ { return make_iterator(_edges, i)->first; }
+
+ /** Return the reverse edge descriptor bound to the in edge. */
+ inline out_descriptor out_edge(in_descriptor i) const
+ { return make_iterator(_edges, i)->second; }
+
+ /** Return a desecriptor for an iterator into this object. */
+ inline in_descriptor in_edge(iterator i) const
+ { return make_descriptor(_edges, i); }
+
private:
mutable store_type _edges;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -4,14 +4,23 @@
/**
* The out edge iterator is a wrapper around out store iterators that, when
- * dereferenced will return an edge descriptor. The properties of the iterator
- * are taken from the underlying store.
+ * dereferenced will return an edge descriptor.
+ *
+ * @note This is unfortunately parameterized over the entire vertex type. Why?
+ * Basically because we can't tranlstate between the underlying iterator and
+ * its own descriptor without access to its store. Unfortunately, the store
+ * that defines the underlying iterator is buried beneath the vertex, preventing
+ * easy construction from the outer graph class. Why o' why do I not have self-
+ * transflating descriptors? It could greatly simplify some aspects of these
+ * implementations.
*/
-template <typename Store, typename Edge>
+template <typename Vertex, typename Edge>
class basic_out_iterator
{
- typedef Store store_type;
- typedef typename Store::iterator iterator;
+public:
+ // Decode some type information from the wrapped out iterator.
+ typedef Vertex vertex_type;
+ typedef typename Vertex::out_iterator iterator;
typedef typename iterator::value_type base_value_type;
typedef typename base_value_type::first_type vertex_descriptor;
typedef typename base_value_type::second_type edge_pair;
@@ -28,21 +37,28 @@
typedef value_type pointer;
inline basic_out_iterator()
- : src(), iter(), outs(0)
+ : vert(0), src(), iter()
{ }
- inline basic_out_iterator(vertex_descriptor v, iterator x, store_type& store)
- : src(v), iter(x), outs(&store)
+ inline basic_out_iterator(vertex_type& vert, vertex_descriptor v, iterator x)
+ : vert(&vert), src(v), iter(x)
{ }
/** Return the source vertex of the iterated edge. */
- vertex_descriptor source() const
+ inline vertex_descriptor source() const
{ return src; }
/** Return the target vertex of the iterated edge. */
- vertex_descriptor target() const
+ inline vertex_descriptor target() const
{ return iter->first; }
+ /**
+ * Return the "opposite" (target) vertex of the iterated edge. This is
+ * provided to work with the adjacency iterator.
+ */
+ inline vertex_descriptor opposite() const
+ { return target(); }
+
inline basic_out_iterator& operator++()
{ ++iter; return *this; }
@@ -59,11 +75,11 @@
//@}
inline reference operator*() const
- { return Edge(source(), target(), outs->edge(iter)); }
+ { return Edge(source(), target(), vert->out_edge(iter)); }
+ vertex_type* vert;
vertex_descriptor src;
iterator iter;
- store_type* outs;
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -108,11 +108,11 @@
{ return make_iterator(_edges, o)->second.first; }
/** Return the in edge descriptor bound to this edge. */
- inline in_descriptor reverse(out_descriptor o) const
+ inline in_descriptor in_edge(out_descriptor o) const
{ return make_iterator(_edges, o)->second.second; }
/** Return an out descriptor for the given iterator. */
- inline out_descriptor edge(iterator i)
+ inline out_descriptor out_edge(iterator i) const
{ return make_descriptor(_edges, i); }
private:
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -87,7 +87,7 @@
{ return _edges.begin(); }
inline iterator end() const
- { return iterator(); }
+ { return _edges.end(); }
//@}
/** Bind the edge to the corresponding in edge descriptor. */
@@ -103,11 +103,11 @@
{ return make_iterator(_edges, o)->second.first; }
/** Return the in edge descriptor bound to this edge. */
- inline in_descriptor reverse(out_descriptor o) const
+ inline in_descriptor in_edge(out_descriptor o) const
{ return make_iterator(_edges, o)->second.second; }
/** Return an out descriptor for the given iterator. */
- inline out_descriptor edge(iterator i)
+ inline out_descriptor out_edge(iterator i) const
{ return make_descriptor(_edges, i); }
private:
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -84,11 +84,11 @@
{ return make_iterator(_edges, o)->second.first; }
/** Return the in edge descriptor bound to this edge. */
- inline in_descriptor reverse(out_descriptor o) const
+ inline in_descriptor in_edge(out_descriptor o) const
{ return make_iterator(_edges, o)->second.second; }
/** Return an out descriptor for the given iterator. */
- inline out_descriptor edge(iterator i)
+ inline out_descriptor out_edge(iterator i) const
{ return make_descriptor(_edges, i); }
private:
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 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -143,9 +143,9 @@
* convenience overloads that depend on the type of vertex store.
*/
//@{
- std::pair<edge_descriptor, bool> edge(vertex_descriptor, vertex_descriptor) const;
- std::pair<edge_descriptor, bool> edge(vertex_properties const&, vertex_properties const&) const;
- std::pair<edge_descriptor, bool> edge(vertex_key const&, vertex_key const&) const;
+ edge_descriptor edge(vertex_descriptor, vertex_descriptor) const;
+ edge_descriptor edge(vertex_properties const&, vertex_properties const&) const;
+ edge_descriptor edge(vertex_key const&, vertex_key const&) const;
//@}
/** @name Remove Edge(s)
@@ -417,15 +417,13 @@
* whether or not the edge did exist.
*/
template <BOOST_GRAPH_UG_PARAMS>
-std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
undirected_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v) const
{
reorder(u, v);
vertex_type const& src = _verts.vertex(u);
- typename vertex_type::iterator i = src.find(v);
- return i != src.end() ?
- std::make_pair(edge_descriptor(u, v, i->second), true) :
- std::make_pair(edge_descriptor(), false);
+ incidence_descriptor i = src.find_vertex(v);
+ return i ? edge_descriptor(u, v, src.properties(i)) : edge_descriptor();
}
/**
@@ -435,7 +433,7 @@
* edge(find_vertex(u), find_vertex(v)).
*/
template <BOOST_GRAPH_UG_PARAMS>
-std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
undirected_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
vertex_properties const& v) const
{
@@ -449,7 +447,7 @@
* expression edge(find_vertex(u), find_vertex(v)).
*/
template <BOOST_GRAPH_UG_PARAMS>
-std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
undirected_graph<VP,EP,VS,ES>::edge(vertex_key const& u,
vertex_key const& v) const
{
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 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -53,11 +53,11 @@
inline void disconnect(incidence_descriptor i)
{ _edges.remove(i); }
- //@}
- /** Find return an iterator the edge end with the given vertex. */
- inline iterator find(vertex_descriptor v) const
+ /** Find an incident edge connecting this to the given vertex. */
+ inline incidence_descriptor find(vertex_descriptor v) const
{ return _edges.find(v); }
+ //@}
/** Return the properties of the given incident edge. */
inline property_descriptor edge_properties(incidence_descriptor i) const
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 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -6,6 +6,7 @@
#include <boost/graphs/directed_graph.hpp>
#include "typestr.hpp"
+#include "out_edge_traits.hpp"
using namespace std;
using namespace boost;
@@ -17,6 +18,26 @@
void vec_vec();
void set_set();
+namespace dispatch
+{
+ bool allows_parallel_edges(unique_associative_container_tag)
+ { return false; }
+
+ bool allows_parallel_edges(multiple_associative_container_tag)
+ { return false; }
+
+ bool allows_parallel_edges(sequence_tag)
+ { return true; }
+}
+
+template <typename Graph>
+bool allows_parallel_edges(Graph const& g)
+{
+ typedef typename Graph::out_store Store;
+ return dispatch::allows_parallel_edges(typename out_edge_traits<Store>::category());
+}
+
+
template <typename Graph>
void print_types(const Graph&)
{
@@ -44,10 +65,13 @@
void test_add_remove_vertices()
{
Graph g;
+ cout << " * adding vertices" << endl;
list<typename Graph::vertex_descriptor> V;
for(int i = 0; i < 5; ++i) {
V.push_back(g.add_vertex(i));
}
+
+ cout << " * removing vertices" << endl;
BOOST_ASSERT(g.num_vertices() == 5);
while(!V.empty()) {
g.remove_vertex(V.front());
@@ -85,6 +109,8 @@
for(int i = 0; i < 3; ++i) {
V.push_back(g.add_vertex(i));
}
+
+ cout << " * adding edges" << endl;
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]));
@@ -94,6 +120,7 @@
BOOST_ASSERT(g.out_degree(V[0]) == 1);
BOOST_ASSERT(g.in_degree(V[0]) == 1);
+ cout << " * removing edges" << endl;
g.remove_edge(E.front());
BOOST_ASSERT(g.degree(V[1]) == 1);
BOOST_ASSERT(g.out_degree(V[0]) == 0);
@@ -127,8 +154,8 @@
BOOST_ASSERT(g.in_degree(V[0]) == 1);
BOOST_ASSERT(g.in_degree(V[1]) == 1);
BOOST_ASSERT(g.in_degree(V[2]) == 1);
- BOOST_ASSERT(g.edge(V[0], V[1]).second);
- BOOST_ASSERT(g.edge(V[2], V[0]).second);
+ BOOST_ASSERT(g.edge(V[0], V[1]));
+ BOOST_ASSERT(g.edge(V[2], V[0]));
// Disconnect the vertex
g.remove_edges(V[0]);
@@ -181,6 +208,8 @@
Graph g;
typename Graph::vertex_descriptor u = g.add_vertex(1);
typename Graph::vertex_descriptor v = g.add_vertex(2);
+
+ cout << " * adding multiple edge" << endl;
g.add_edge(u, v);
g.add_edge(v, u);
g.add_edge(u, v);
@@ -188,10 +217,11 @@
BOOST_ASSERT(g.num_vertices() == 2);
if(allows_parallel_edges(g)) {
- BOOST_ASSERT(g.num_edges() == 1);
+ BOOST_ASSERT(g.num_edges() == 4);
}
else {
- BOOST_ASSERT(g.num_edges() == 4);
+ // Two edges: (u,v) and (v,u)
+ BOOST_ASSERT(g.num_edges() == 2);
}
}
@@ -201,15 +231,19 @@
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);
+ cout << " * removing multiple edges" << endl;
g.remove_edges(u, v);
- BOOST_ASSERT(g.num_edges() == 2);
- BOOST_ASSERT(g.out_degree(v) == 2);
- BOOST_ASSERT(g.in_degree(u) == 2);
+ BOOST_ASSERT(g.out_degree(u) == 0);
+ BOOST_ASSERT(g.in_degree(v) == 0);
+ BOOST_ASSERT(g.num_edges() == allows_parallel_edges(g) ? 2 : 1);
+ BOOST_ASSERT(g.out_degree(v) == allows_parallel_edges(g) ? 2 : 1);
+ BOOST_ASSERT(g.in_degree(u) == allows_parallel_edges(g) ? 2 : 1);
}
template <typename Graph>
@@ -223,9 +257,11 @@
g.add_edge(u, v, 3);
g.add_edge(v, u, 4);
- typename Graph::incident_edge_range x = g.incident_edges(v);
- for( ; x.first != x.second; ++x.first) {
- // cout << "test: " << g[*x.first] << 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;
+ BOOST_ASSERT(e.source() == u);
+ BOOST_ASSERT(e.target() == v);
}
}
@@ -235,14 +271,15 @@
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, 1);
g.add_edge(v, u, 2);
g.add_edge(u, v, 3);
g.add_edge(v, u, 4);
- typename Graph::adjacent_vertex_range x = g.adjacent_vertices(v);
- for( ; x.first != x.second; ++x.first) {
- // cout << "test: " << g[*x.first] << endl;
+ typename Graph::adjacent_vertex_range rng = g.adjacent_vertices(u);
+ for( ; rng.first != rng.second; ++rng.first) {
+ BOOST_ASSERT(*rng.first == v);
}
}
@@ -261,8 +298,8 @@
typedef directed_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
test_add_vertices<Graph>();
test_add_edges<Graph>();
- /*
test_add_multi_edges<Graph>();
+ /*
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
*/
@@ -271,7 +308,6 @@
void list_list()
{
cout << "---- list/list ----" << endl;
- /*
typedef directed_graph<City, Road, vertex_list<>, edge_list<> > Graph;
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
@@ -279,6 +315,7 @@
test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
test_remove_multi_edges<Graph>();
+ /*
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
*/
@@ -288,7 +325,6 @@
void set_set()
{
cout << "---- set/set ----" << endl;
- /*
typedef directed_graph<City, Road, vertex_set<>, edge_set<> > Graph;
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
@@ -298,6 +334,5 @@
test_remove_multi_edges<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
- */
}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/out_edge_traits.hpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -2,9 +2,9 @@
#ifndef OUT_EDGE_TRAITS_HPP
#define OUT_EDGE_TRAITS_HPP
-struct out_vector_tag : sequence_tag, unstable_remove_tag { };
-struct out_list_tag : sequence_tag, stable_mutators_tag { };
-struct out_set_tag : associative_container_tag, stable_mutators_tag { };
+struct out_vector_tag : vector_tag, unstable_remove_tag { };
+struct out_list_tag : list_tag, stable_mutators_tag { };
+struct out_set_tag : set_tag, stable_mutators_tag { };
template <typename Outs>
struct out_edge_traits
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp 2008-07-11 09:59:00 EDT (Fri, 11 Jul 2008)
@@ -0,0 +1,57 @@
+
+#include <iostream>
+
+#include <boost/graphs/in_vector.hpp>
+#include <boost/graphs/in_list.hpp>
+#include <boost/graphs/in_set.hpp>
+
+#include "typestr.hpp"
+#include "in_edge_traits.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef index_descriptor<size_t> VertexDesc;
+typedef index_descriptor<size_t> OutDesc;
+typedef pair<VertexDesc, OutDesc> InEdge;
+typedef allocator<InEdge> Alloc;
+typedef less<VertexDesc> Compare;
+
+template <typename Ins>
+void test_remove(Ins& ins, stable_mutators_tag)
+{
+ size_t n = ins.size();
+ ins.remove(ins.find(3));
+ BOOST_ASSERT(ins.size() == n - 1);
+ cout << " * size after remove: " << ins.size() << endl;
+}
+
+template <typename Ins>
+void test_remove(Ins&, unstable_remove_tag)
+{ /* Don't do anything. */ }
+
+template <typename Ins>
+void test()
+{
+ Ins ins;
+ cout << "--- " << typestr(in_edge_category(ins)) << " ---" << endl;
+
+ // Add some vertices.
+ BOOST_ASSERT(ins.empty());
+ for(int i = 0; i < 5; ++i) {
+ ins.add(VertexDesc(i), OutDesc(i + 1));
+ }
+ BOOST_ASSERT(ins.size() == 5);
+ cout << " * size after building: " << ins.size() << endl;
+
+ test_remove(ins, in_edge_category(ins));
+}
+
+int main()
+{
+ test<in_vector<InEdge, Alloc>>();
+ test<in_list<InEdge, Alloc>>();
+ test<in_set<InEdge, Compare, Alloc>>();
+
+ return 0;
+}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk