From: asutton_at_[hidden]
Date: 2008-07-23 11:25:34
Author: asutton
Date: 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
New Revision: 47721
URL: http://svn.boost.org/trac/boost/changeset/47721
Log:
Implemented generic exterior maps that can self-contain their own data. These
probably need better names, but they work for now.
Implemented default propertied versions of the BFS.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_walk.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/vertex_walk.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp | 1
sandbox/SOC/2008/graphs/trunk/boost/graphs/colors.hpp | 35 +++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 11 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp | 7 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp | 169 +++++++++++++++++++++++++++++++--------
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/hashed_property_container.hpp | 9 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/indexed_property_container.hpp | 9 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 37 ++++++++
sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp | 23 ++++
sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp | 34 +++++--
10 files changed, 267 insertions(+), 68 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -34,7 +34,6 @@
inline operator bool() const
{ return !is_null(); }
-
/** @name Equality Comparable */
//@{
inline bool operator==(index_descriptor const& x) const
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -0,0 +1,17 @@
+
+#ifndef ALGORITHMS_BREADTH_FIRST_HPP
+#define ALGORITHMS_BREADTH_FIRST_HPP
+
+#include <boost/graphs/properties.hpp>
+#include <boost/graphs/colors.hpp>
+
+// Possible concept-related notions:
+// VertexWalk: A walk whose current state yields vertices.
+// EdgeWalk: A walk whose current state yields edges. Edge walks must also
+// provide edge-like interfaces (i.e., source/target) functions in order to
+// disambiguate the unordering of undirected graphs.
+
+#include <boost/graphs/algorithms/breadth_first/vertex_walk.hpp>
+#include <boost/graphs/algorithms/breadth_first/edge_walk.hpp>
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -0,0 +1,98 @@
+
+#ifndef BREADTH_FIRST_EDGE_ITERATOR_HPP
+#define BREADTH_FIRST_EDGE_ITERATOR_HPP
+
+namespace detail
+{
+ // Edges returned by edge iterators are best used in a directed sense. This
+ // because the walk flows from one vertex to the next and it is important
+ // to push this data to the user. However, undirected graphs don't have
+ // any notion of edge direction so we have to fake it by using rooted
+ // edges. A little extra space and time, but a viable solution.
+ template <typename Graph>
+ struct choose_rooted_edge
+ {
+ typedef typename Graph::edge_descriptor type;
+ };
+
+ template <typename VP, typename EP, typename VS, typename ES>
+ struct choose_rooted_edge<undirected_graph<VP,EP,VS,ES>>
+ {
+ typedef rooted_undirected_edge<
+ typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
+ > type;
+ };
+
+ // Helper functions for creating rooted edges. The default is to simply
+ // return the given edge, and does not use the source vertex.
+ template <typename Edge, typename Vertex>
+ inline Edge
+ make_rooted_edge(Edge const& e, Vertex)
+ { return e; }
+
+ template <typename Vertex, typename Prop>
+ inline rooted_undirected_edge<undirected_edge<Vertex,Prop>>
+ make_rooted_edge(undirected_edge<Vertex,Prop> const& e, Vertex src)
+ { return rooted_undirected_edge<undirected_edge<Vertex,Prop>>(e, src); }
+}
+
+/**
+ * Provide an iterator abstraction over the walk. Dereferencing a walk iterator
+ * returns the walk itself.
+ *
+ * This is kind of a strange iterator in the sense that it doesn't support
+ * post-increment operations. That would require making a copy of underlying
+ * algorithm, which would be very, very expensive. Is this a basic iterator
+ * concept?
+ */
+template <typename Walk>
+struct breadth_first_edge_iterator
+{
+ typedef Walk walk_type;
+ typedef typename Walk::graph_type Graph;
+
+ typedef std::forward_iterator_tag iterator_category;
+ typedef std::size_t difference_type;
+ typedef typename detail::choose_rooted_edge<Graph>::type value_type;
+ typedef value_type reference;
+
+ // Construct an end iterator.
+ breadth_first_edge_iterator()
+ : walk()
+ { }
+
+ // Explicitly build an iterator over the state of the given walk.
+ breadth_first_edge_iterator(walk_type* walk)
+ : walk(walk)
+ { }
+
+ inline breadth_first_edge_iterator& operator++()
+ { walk->next(); return *this; }
+
+ // Return true if this iterator is past the end. An iterator is past the
+ // end if a) the walk pointer is null or b) the current edge is null.
+ bool end() const
+ { return !walk || (walk && !walk->edge()); }
+
+ // Two iterators are equivalent if they're both at the end or both refer
+ // to the same edge.
+ inline bool operator==(breadth_first_edge_iterator const& x) const
+ {
+ return (!walk && x.end())
+ || (!x.walk && end())
+ || (walk && x.walk && walk->edge() == x.walk->edge());
+ }
+
+ inline bool operator!=(breadth_first_edge_iterator const& x) const
+ { return !operator==(x); }
+
+ inline reference operator*() const
+ { return detail::make_rooted_edge(walk->edge(), walk->source()); }
+
+ inline walk_type const* operator->() const
+ { return walk; }
+
+ walk_type* walk;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_walk.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_walk.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -0,0 +1,291 @@
+
+#ifndef BREADTH_FIRST_EDGE_WALK_HPP
+#define BREADTH_FIRST_EDGE_WALK_HPP
+
+#include <queue>
+
+#include "edge_iterator.hpp"
+
+// Multi-rooted BFS: A variant of a BFS that seeds the queue with multiple
+// initial vertices, but otherwise proceeds normally. The effect is of searching
+// for a vertex in the middle. Should work with both directed and undirected
+// graphs. This only applies to the walk, not the traversal.
+//
+// BF Topological Sort: (Directed only): A variant that postpones the visitation
+// of a vertex until all vertices on incoming edges have been visited. This
+// actually requires a fundamental change in the structure of the algorithm
+// and is not trivially implemented inside this framework. It requries a
+// prooperty map that counts the number of dependent edges, only visiting when
+// the count reaches 0. This probably only applies to the traversal.
+
+
+/**
+ * The edge-walk implements a breadth-first walk that provides access to the
+ * current edge. This is one of the most fundamental algorithm abstractions
+ * since it can be used to build any kind of breadth first search including
+ * a vertex walk because the source of each edge is the current vertex.
+ *
+ * This algorithm also supports a multirooted version of the walk. In a multi-
+ * homed (or rooted) breadth-first walk, the queue is seeded with multiple
+ * vertices. The algorithm proceeds normally.
+ *
+ * This algorithm object essentially provides the next tree edge at each step.
+ *
+ * @requires IncidenceGraph<Graph>
+ * @requires ReadWritePropertyMap<ColorMap>
+ * @requires Queue<Queue>
+ */
+template <
+ typename Graph,
+ typename ColorMap = generic_vertex_map<Graph, color>,
+ typename Queue = std::queue<typename Graph::vertex_descriptor>>
+struct breadth_first_edge_walk
+{
+ typedef breadth_first_edge_walk<Graph, ColorMap, Queue> this_type;
+
+ typedef typename ColorMap::value_type Color;
+ typedef color_traits<Color> ColorTraits;
+
+ typedef Graph graph_type;
+ typedef typename Graph::vertex_descriptor vertex_descriptor;
+ typedef typename Graph::edge_descriptor edge_descriptor;
+ typedef typename Graph::incident_edge_range IncidenceRange;
+
+ typedef breadth_first_edge_iterator<this_type> iterator;
+
+ breadth_first_edge_walk(Graph& g, vertex_descriptor v)
+ : graph(g), color(g, ColorTraits::white()), queue(), range()
+ { start(v); }
+
+ breadth_first_edge_walk(Graph& g, vertex_descriptor v, ColorMap color)
+ : graph(g), color(color), queue(), range()
+ { start(v); }
+
+ // Multi-rooted constructor.
+ template <typename Iter>
+ breadth_first_edge_walk(Graph& g, Iter f, Iter l, ColorMap color)
+ : graph(g), color(color), queue(), range()
+ { start(f, l); }
+
+ template <typename Iter>
+ breadth_first_edge_walk(Graph& g, Iter f, Iter l)
+ : graph(g), color(g, ColorTraits::white()), queue(), range()
+ { start(f, l); }
+
+ /** Initialize the walk to the given vertex. */
+ void start(vertex_descriptor v)
+ {
+ // Iniitalize the starting vertex
+ color(v) = ColorTraits::gray();
+ queue.push(v);
+
+ // Set the starting range and select the first valid edge.
+ range = graph.incident_edges(v);
+ next();
+ }
+
+ /** Initialize the walk with the sequence of roots. */
+ template <typename Iter>
+ void start(Iter f, Iter l)
+ {
+ for( ; f != l; ++f) {
+ vertex_descriptor v = *f;
+ color(v) = ColorTraits::gray();
+ queue.push(v);
+ }
+
+ // Set the starting range and select the first valid edge.
+ range = graph.incidenct_edges(queue.front());
+ next();
+ }
+
+ /** Move to the next tree edge. */
+ void next()
+ {
+ // Start by looking for the next target.
+ next_target();
+ if(queue.empty()) {
+ return;
+ }
+
+ // Set the color of the target to gray and push it into the queue.
+ vertex_descriptor v = target();
+ color(v) = ColorTraits::gray();
+ queue.push(v);
+ }
+
+ /**
+ * Move to the next vertex by popping the queue and resetting the incident
+ * edge range to that of the next vertex. Note that the current vertex is
+ * marked done or black at this point.
+ */
+ void next_vertex()
+ {
+ // We're done with the current vertex. Mark it black.
+ vertex_descriptor u = queue.front();
+ color(u) = ColorTraits::black();
+
+ // Move the the next vertex and reset the incident edge range.
+ queue.pop();
+ if(!queue.empty()) {
+ vertex_descriptor v = queue.front();
+ range = graph.incident_edges(v);
+ }
+ }
+
+ /**
+ * Find the next target. This will move the algorithm state so that the
+ * range points to the next valid edge.
+ */
+ void next_target()
+ {
+ // Basically, just keep looping until finished...
+ while(!queue.empty()) {
+ // If the range is empty, then get a new one by moving to the next
+ // vertex. This will color vertices as needed. If we exhaust the
+ // queue, break.
+ if(range.first == range.second) {
+ next_vertex();
+ if(queue.empty()) {
+ break;
+ }
+ }
+
+ // As long as we can check the range, try to find a vertex in this
+ // range that hasn't been discovered just yet.
+ while(range.first != range.second && !discoverable()) {
+ ++range.first;
+ }
+
+ // If we found something, then bail.
+ if(range.first != range.second) {
+ break;
+ }
+ }
+ }
+
+ /**
+ * Return the current edge "pointed" to by the algorithm, which will be
+ * null if the queue is empty (the algorithm has finished).
+ */
+ inline edge_descriptor edge() const
+ { return queue.empty() ? edge_descriptor() : *range.first; }
+
+ /**
+ * Returns the source vertex of the current edge. This is the vertex in the
+ * front of the queue, and the origin of the current incident edge.
+ */
+ inline vertex_descriptor source() const
+ { return queue.empty() ? vertex_descriptor() : queue.front(); }
+
+ /**
+ * Return the target vertex of the current edge. Note that the the edge
+ * pointed to by the algorithm.
+ */
+ inline vertex_descriptor target() const
+ { return queue.empty() ? vertex_descriptor() : edge().opposite(source()); }
+
+ /** Return true if the current target has already been visited. */
+ bool discoverable() const
+ { return color(target()) == ColorTraits::white(); }
+
+ inline iterator begin()
+ { return iterator(this); }
+
+ inline iterator end()
+ { return iterator(); }
+
+ Graph& graph;
+ ColorMap color;
+ Queue queue;
+ IncidenceRange range;
+};
+
+/**
+ * Perform a breadth first walk that reaches all vertices of the graph. This
+ * is done by performing walks at each vertex, maintaing the color map between
+ * individual executions.
+ *
+ * The choice of starting vertex is not given in this algorithm since all
+ * vertices and edges will be traversed.
+ */
+template <
+ typename Graph,
+ typename ColorMap = generic_vertex_map<Graph, color>,
+ typename Queue = std::queue<typename Graph::vertex_descriptor>>
+struct breadth_first_edge_traversal
+{
+ typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> this_type;
+
+ typedef Graph graph_type;
+ typedef typename Graph::edge_descriptor edge_descriptor;
+ typedef typename Graph::vertex_descriptor vertex_descriptor;
+ typedef typename Graph::vertex_range vertex_descriptorRange;
+
+ typedef typename ColorMap::value_type Color;
+ typedef color_traits<Color> ColorTraits;
+
+ typedef breadth_first_edge_walk<Graph, ColorMap, Queue> Walk;
+ typedef breadth_first_edge_iterator<this_type> iterator;
+
+ breadth_first_edge_traversal(Graph& g)
+ : graph(g), color(g, ColorTraits::white()), range(g.vertices())
+ , walk(graph, *range.first, color)
+ { }
+
+ breadth_first_edge_traversal(Graph& g, ColorMap color)
+ : graph(g), color(color), range(g.vertices())
+ , walk(graph, *range.first, color)
+ { }
+
+ void next()
+ {
+ // We can usually delegate the next step of the traversal to that of
+ // the current walk. However, if the next step of the traversal takes
+ // us to a null edge, then we have to search for the next unvisited
+ // vertex in the graph.
+ if(range.first != range.second) {
+ walk.next();
+ }
+
+ // Did we just walk off the edge?
+ if(!walk.edge()) {
+ // Find the next connected component.
+ while(range.first != range.second && !discoverable()) {
+ ++range.first;
+ }
+
+ // If we haven't walked off the edge yet, update the walk over
+ // the new vertex.
+ if(range.first != range.second) {
+ walk.start(*range.first);
+ }
+ }
+ }
+
+ inline edge_descriptor edge() const
+ { return walk.edge(); }
+
+ inline vertex_descriptor source() const
+ { return walk.source(); }
+
+ inline vertex_descriptor target() const
+ { return walk.target(); }
+
+ // Returns true if the current edge is discoverable.
+ inline bool discoverable() const
+ { return color(*range.first) == ColorTraits::white(); }
+
+ inline iterator begin()
+ { return iterator(this); }
+
+ inline iterator end()
+ { return iterator(); }
+
+ Graph& graph;
+ ColorMap color;
+ vertex_descriptorRange range;
+ Walk walk;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/vertex_walk.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/vertex_walk.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -0,0 +1,109 @@
+
+#ifndef BREADTH_FIRST_VERTEX_WALK_HPP
+#define BREADTH_FIRST_VERTEX_WALK_HPP
+
+/**
+ * The breadth first walk
+ */
+template <typename Graph, typename ColorMap, typename Queue>
+struct breadth_first_vertex_walk
+{
+ // Grab the color and traits from the map
+ typedef typename ColorMap::value_type Color;
+ typedef color_traits<Color> ColorTraits;
+
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::edge_descriptor Edge;
+ typedef typename Graph::adjacent_vertex_range AdjacencyRange;
+
+ breadth_first_vertex_walk(Graph& g, Queue& queue, ColorMap color, Vertex start)
+ : graph(g), queue(queue), color(color), start(start)
+ { initialize(); }
+
+ ~breadth_first_vertex_walk()
+ { finalize(); }
+
+ /**
+ * Initialize the walk. This does not initialize the data structures passed
+ * to the walk individually. It simply sets the starting state of the walk.
+ */
+ void initialize()
+ {
+ color(start) = ColorTraits::gray();
+ queue.push(start);
+ }
+
+ /** Finish the algorithm. */
+ void finalize()
+ { }
+
+ /**
+ * Move to the next vertex in the walk. At each step, this pops the current
+ * vertex and looks for unvisited adjacent vertices.
+ */
+ void next()
+ {
+ // Remvoe the top element from the queue and insert all unvisited
+ // adjacent vertices.
+ Vertex u = queue.front();
+ queue.pop();
+
+ AdjacencyRange ar = graph.adjacent_vertices(u);
+ for( ; ar.first != ar.second; ++ar.first) {
+ Vertex v = *ar.first;
+ if(color(v) == ColorTraits::white()) {
+ color(v) = ColorTraits::gray();
+
+ // TODO: Visit the discovered vertex here?
+ queue.push(v);
+ }
+ }
+
+ color(u) = ColorTraits::black();
+ }
+
+ /** Return the current vertex. */
+ Vertex vertex()
+ { return queue.empty() ? Vertex() : queue.front(); }
+
+ Graph& graph;
+ Queue& queue;
+ ColorMap color;
+ Vertex start;
+};
+
+/**
+ * Provide an iterator abstraction over the walk. The result of dereferencing
+ * an iterator is the current vertex of the underlying walk.
+ */
+template <typename Graph, typename ColorMap, typename Queue>
+struct breadth_first_vertex_iterator
+{
+ typedef breadth_first_vertex_walk<Graph, ColorMap, Queue> walk_type;
+
+ typedef std::forward_iterator_tag iterator_category;
+ typedef std::size_t difference_type;
+ typedef typename Graph::edge_descriptor value_type;
+ typedef typename Graph::edge_descriptor reference;
+ typedef walk_type* pointer;
+
+ breadth_first_vertex_iterator(walk_type& walk)
+ : walk(walk)
+ { }
+
+ inline breadth_first_vertex_iterator& operator++()
+ { walk.next(); return *this; }
+
+ inline bool operator==(breadth_first_vertex_iterator const& x) const
+ { return walk.vertex() == x.walk.vertex(); }
+
+ inline bool operator!=(breadth_first_vertex_iterator const& x) const
+ { return !operator=(x); }
+
+ inline reference operator*() const
+ { return walk.vertex(); }
+
+ walk_type& walk;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp
==============================================================================
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/colors.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/colors.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/colors.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -2,9 +2,13 @@
#ifndef COLORS_HPP
#define COLORS_HPP
-/**
- * Default color types for this library.
- */
+// This seems a bit extensive for a simple enumeration of colors. However, it
+// is certainly possible that somebody wants to use their own enumeration type
+// as the colors for an algorithm. All they have to do is provide a
+// specialization of the color_traits class in order to return the colors that
+// they want.
+
+/** Default color types for this library. */
enum color {
white_color,
gray_color,
@@ -18,17 +22,28 @@
* A traits class for colors. Specialize this if, for some reason, you ever
* plan to specialize the notion of colors - which may be possible.
*
- * @todo Obviously, this will be conceptized. See below.
+ * @todo This should be conceptized. See below.
*/
template <typename Color>
struct color_traits
{
- static color white() { return white_color; }
- static color gray() { return gray_color; }
- static color black() { return black_color; }
- static color red() { return red_color; }
- static color green() { return green_color; }
- static color blue() { return blue_color; }
+ static color white()
+ { return white_color; }
+
+ static color gray()
+ { return gray_color; }
+
+ static color black()
+ { return black_color; }
+
+ static color red()
+ { return red_color; }
+
+ static color green()
+ { return green_color; }
+
+ static color blue()
+ { return blue_color; }
};
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-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -45,14 +45,21 @@
{ return !is_null(); }
//@}
- /** Return the source vertex descriptor. */
+ /** @name End Points
+ * Provide access to the source and target of the directed edge. The
+ * opposite member provides parity with undirected edge type.
+ */
+ //@{
inline vertex_descriptor source() const
{ return ends.first; }
- /** Return the target vertex descriptor. */
inline vertex_descriptor target() const
{ return ends.second; }
+ inline vertex_descriptor opposite(vertex_descriptor v) const
+ { return v == source() ? target() : source(); }
+ //@}
+
/** Return the descriptor to the out edge, where the property is stored. */
inline out_descriptor out_edge() const
{ return out; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -13,7 +13,7 @@
public:
typedef Iter iterator;
typedef typename iterator::value_type base_value_type;
- typedef typename base_value_type::first_type vertex_descriptor;
+ typedef typename boost::remove_const<typename base_value_type::first_type>::type vertex_descriptor;
typedef typename base_value_type::second_type property_descriptor;
// This is a little misleading. This iterator can be either bidi or random.
@@ -30,7 +30,7 @@
: base(), iter()
{ }
- inline incidence_iterator(vertex_descriptor v, iterator const& x)
+ inline incidence_iterator(vertex_descriptor v, iterator x)
: base(v), iter(x)
{ }
@@ -50,6 +50,9 @@
inline vertex_descriptor opposite() const
{ return iter->first; }
+ inline incidence_iterator& operator=(incidence_iterator const& x)
+ { base = x.base; iter = x.iter; return *this; }
+
inline incidence_iterator& operator++()
{ ++iter; return *this; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -2,6 +2,8 @@
#ifndef PROPERTIES_HPP
#define PROPERTIES_HPP
+#include <boost/shared_ptr.hpp>
+
#include <boost/descriptors.hpp>
// Include associative adpaters for exterior properties.
@@ -13,48 +15,46 @@
#include "properties/simple_property_map.hpp"
#include "properties/bundled_property_map.hpp"
-// TODO: We currently distinguish between exterior and interior using the names
-// of the structures...
-
-// Define the mapping strategy based on the type of descriptor. By default,
-// we prefer to use hashing since the number of data structures that actually
-// index their vertices is... tiny.
-struct index_mapping { };
-struct hash_mapping { };
-
-template <typename Descriptor>
-struct descriptor_mapping
-{ typedef hash_mapping strategy; };
-
-template <typename Index>
-struct descriptor_mapping<index_descriptor<Index>>
-{ typedef index_mapping strategy;};
-
-// Select the type of container based on the underlying store selector.
-template <typename Selector, typename Descriptor, typename Property>
-struct choose_container
-{
- typedef typename boost::mpl::if_<
- boost::is_same<
- typename descriptor_mapping<Descriptor>::strategy,
- hash_mapping>,
- hashed_property_container<Descriptor, Property>,
- indexed_property_container<Descriptor, Property>
- >::type type;
-};
+namespace detail
+{
+ // Define the mapping strategy based on the type of descriptor. By default,
+ // we prefer to use hashing since the number of data structures that actually
+ // index their vertices is... tiny.
+ struct index_mapping { };
+ struct hash_mapping { };
+
+ template <typename Descriptor>
+ struct descriptor_mapping
+ { typedef hash_mapping strategy; };
+
+ template <typename Index>
+ struct descriptor_mapping<index_descriptor<Index>>
+ { typedef index_mapping strategy;};
+
+ // Select the type of container based on the underlying store selector.
+ template <typename Descriptor, typename Property>
+ struct choose_container
+ {
+ typedef typename boost::mpl::if_<
+ boost::is_same<
+ typename descriptor_mapping<Descriptor>::strategy,
+ hash_mapping>,
+ hashed_property_container<Descriptor, Property>,
+ indexed_property_container<Descriptor, Property>
+ >::type type;
+ };
+}
/**
* Used to cotnain exterior vertex properties.
*/
template <typename Graph, typename Property>
struct exterior_vertex_property
- : choose_container<
- typename Graph::vertex_store_selector, typename Graph::vertex_descriptor, Property
- >::type
-{
- typedef typename choose_container<
- typename Graph::vertex_store_selector, typename Graph::vertex_descriptor, Property
- >::type base_type;
+ : detail::choose_container<typename Graph::vertex_descriptor, Property>::type
+{
+ typedef typename detail::choose_container<
+ typename Graph::vertex_descriptor, Property
+ >::type base_type;
exterior_vertex_property(Graph const& g, Property const& p = Property())
: base_type(g.begin_vertices(), g.end_vertices(), p)
@@ -120,4 +120,101 @@
{ }
};
+
+// The following is a solution to require/supply problem present in a number
+// of generic graph algorithms with respect to the external data. Essentially,
+// we can choose to require the user to give us a property map, or we can
+// create our own data, releasing it when we're done. The property wrapper
+// and generic_*_property classes do this for us. Depending on the method of
+// construction, generic properties will either use an existing property map
+// or create the their own property container (using a shared pointer so it
+// gets deleted later.
+
+namespace detail
+{
+ template <typename Graph>
+ inline typename Graph::vertex_range
+ get_range(Graph const& g, typename Graph::vertex_descriptor)
+ { return g.vertices(); }
+
+ template <typename Graph>
+ inline typename Graph::edge_range
+ get_range(Graph const& g, typename Graph::edge_descriptor)
+ { return g.edges(); }
+}
+
+/**
+ * The property wrapper type allows the definition of exterior properties that
+ * can maintain either their own internal store (via shared pointers) or be
+ * constructed over an exterioir store. This is useful in algorithms that
+ * can provide default exterior properties or allow the user to provide their
+ * own.
+ *
+ * The use of this type incurs a slight overhead due to an additional level of
+ * indirection.
+ */
+template <typename Graph, typename Descriptor, typename Property>
+struct property_wrapper
+{
+ // Select the container and map type for the self-wrapping property.
+ typedef typename detail::choose_container<Descriptor, Property>::type container_type;
+ typedef container_property_map<container_type> map_type;
+
+ typedef typename map_type::value_type value_type;
+ typedef typename map_type::key_type key_type;
+ typedef typename map_type::reference reference;
+
+ // Construct an underlying store over the map.
+ property_wrapper(Graph const& g, value_type const& x = value_type())
+ : container(new container_type(detail::get_range(g, Descriptor()), x))
+ , map(*container)
+ { }
+
+ // Simply construct
+ property_wrapper(map_type map)
+ : container(), map(map)
+ { }
+
+ value_type& operator()(key_type const& key)
+ { return map(key); }
+
+ value_type const& operator()(key_type const& key) const
+ { return map(key); }
+
+ boost::shared_ptr<container_type> container;
+ map_type map;
+};
+
+template <typename Graph, typename Property>
+struct generic_vertex_map
+ : property_wrapper<Graph, typename Graph::vertex_descriptor, Property>
+{
+ typedef property_wrapper<Graph, typename Graph::vertex_descriptor, Property> base_type;
+ typedef typename base_type::map_type map_type;
+
+ generic_vertex_map(Graph const& g, Property const& x = Property())
+ : base_type(g, x)
+ { }
+
+ generic_vertex_map(map_type map)
+ : base_type(map)
+ { }
+};
+
+template <typename Graph, typename Property>
+struct generic_edge_map
+ : property_wrapper<Graph, typename Graph::edge_descriptor, Property>
+{
+ typedef property_wrapper<Graph, typename Graph::vertex_descriptor, Property> base_type;
+ typedef typename base_type::map_type map_type;
+
+ generic_edge_map(Graph const& g, Property const& x = Property())
+ : base_type(g, x)
+ { }
+
+ generic_edge_map(map_type map)
+ : base_type(map)
+ { }
+};
+
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/hashed_property_container.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/hashed_property_container.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/hashed_property_container.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -81,7 +81,14 @@
*/
template <typename Iter>
hashed_property_container(Iter f, Iter l, value_type const& x)
- : data(detail::make_key_value_iterator(f, x), detail::make_key_value_iterator(l, value_type()))
+ : data(detail::make_key_value_iterator(f, x),
+ detail::make_key_value_iterator(l, value_type()))
+ { }
+
+ template <typename Range>
+ hashed_property_container(Range rng, value_type const& x)
+ : data(detail::make_key_value_iterator(rng.first, x),
+ detail::make_key_value_iterator(rng.second, value_type()))
{ }
inline value_type& operator[](key_type const& k)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/indexed_property_container.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/indexed_property_container.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/indexed_property_container.hpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -73,7 +73,14 @@
*/
template <typename Iter>
inline indexed_property_container(Iter f, Iter l, value_type const& x)
- : data(detail::make_default_value_iterator(f, x), detail::make_default_value_iterator(l, value_type()))
+ : data(detail::make_default_value_iterator(f, x),
+ detail::make_default_value_iterator(l, value_type()))
+ { }
+
+ template <typename Range>
+ inline indexed_property_container(Range rng, value_type const& x)
+ : data(detail::make_default_value_iterator(rng.first, x),
+ detail::make_default_value_iterator(rng.second, value_type()))
{ }
inline value_type& operator[](key_type const& k)
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-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -58,6 +58,13 @@
inline edge_pair const& edge() const
{ return ends; }
+ /** @name End Points
+ * Provide access to the end points of the undirected edge. Because the
+ * ends of this edge are unordered, they do not provide a source and target
+ * interface. See the rooted_undirected_edge class for a variant of this
+ * type that imposes a source/target interface on these edges.
+ */
+ //@{
inline vertex_descriptor first() const
{ return ends.first(); }
@@ -66,6 +73,7 @@
inline vertex_descriptor opposite(vertex_descriptor v)
{ return v == first() ? second() : first(); }
+ //@}
/** Return true if the edge connects the two vertices. */
inline bool connects(vertex_descriptor u, vertex_descriptor v) const
@@ -118,6 +126,35 @@
}
/**
+ * The rooted undirected edge is a variant of undirected edges that imposes
+ * a source/target ordering over the edges in the graph. This is done by
+ * maintaining an additional vertex descriptor references the source of an
+ * edge.
+ */
+template <typename Edge>
+class rooted_undirected_edge
+ : public Edge
+{
+public:
+ typedef typename Edge::vertex_descriptor vertex_descriptor;
+
+ /** @name Constructors */
+ inline rooted_undirected_edge(Edge const& edge, vertex_descriptor src)
+ : Edge(edge), src(src)
+ { }
+
+ /** Return the source of the rooted edge. */
+ inline vertex_descriptor source() const
+ { return src; }
+
+ /** Return the target of the rooted edge. */
+ inline vertex_descriptor target() const
+ { return this->opposite(src); }
+
+ vertex_descriptor src;
+};
+
+/**
* The undirected edge iterator simply wraps the iterator over the global edge
* property store of undirected graphs.
*/
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -36,24 +36,39 @@
typedef exterior_property_map<ColorProp> ColorMap;
typedef queue<Vertex> Queue;
- typedef breadth_first_edge_walk<Graph, ColorMap, Queue> BreadthFirstWalk;
- typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> BreadthFirstTraversal;
+ {
+ typedef breadth_first_edge_walk<Graph> Walk;
+ cout << "--- default walk ----" << endl;
+ Walk walk(g, *g.begin_vertices());
+ iterate(g, walk );
+ }
{
- cout << "--- walk ---" << endl;
+ typedef breadth_first_edge_walk<Graph, ColorMap, Queue> BreadthFirstWalk;
+ cout << "--- custom walk ---" << endl;
ColorProp color_prop(g, white_color);
ColorMap color(color_prop);
BreadthFirstWalk walk(g, *g.begin_vertices(), color);
iterate(g, walk);
}
+
+ {
+ typedef breadth_first_edge_traversal<Graph> Traversal;
+ cout << "--- default traversal ---" << endl;
+ Traversal trav(g);
+ iterate(g, trav);
+ }
+
{
- cout << "--- traversal ---" << endl;
+ typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> BreadthFirstTraversal;
+ cout << "--- custom traversal ---" << endl;
ColorProp color_prop(g, white_color);
ColorMap color(color_prop);
BreadthFirstTraversal trav(g, color);
iterate(g, trav);
}
+
}
int main()
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp 2008-07-23 11:25:33 EDT (Wed, 23 Jul 2008)
@@ -64,7 +64,6 @@
// If bundled, constructed over the entire bundle.
-
{
typedef interior_property_map<Graph, Vertex> PropMap;
typedef interior_property_map<Graph, Vertex, string VertexProps::*> NameMap;
@@ -88,6 +87,19 @@
cout << names(e) << endl;
}
}
+
+ {
+ // Generic stuff?
+ exterior_vertex_property<Graph, double> these_weights(g, 6.28);
+
+ generic_vertex_map<Graph, double> my_weights(g, 3.14);
+ generic_vertex_map<Graph, double> your_weights(these_weights);
+
+ for(vr.first = g.begin_vertices(); vr.first != vr.second; ++vr.first) {
+ Vertex v = *vr.first;
+ cout << my_weights(v) << ", " << your_weights(v) << endl;
+ }
+ }
}
@@ -99,6 +111,9 @@
int id;
string name;
+
+ inline bool operator<(Object const& x) const
+ { return id < x.id; }
};
typedef Object City;
@@ -106,28 +121,25 @@
int main()
{
- /*
{
- typedef undirected_graph<int, int, vertex_vector<>, edge_vector<>> G1;
- typedef undirected_graph<int, int, vertex_list<>, edge_list<>> G2;
- typedef undirected_graph<int, int, vertex_set<>, edge_set<>> G3;
+ typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<>> G1;
+ typedef undirected_graph<City, Road, vertex_list<>, edge_list<>> G2;
+ typedef undirected_graph<City, Road, vertex_set<>, edge_set<>> G3;
test_props<G1>();
test_props<G2>();
test_props<G3>();
}
- */
{
typedef directed_graph<City, Road, vertex_vector<>, edge_vector<>> G1;
- typedef directed_graph<int, int, vertex_list<>, edge_list<>> G2;
- typedef directed_graph<int, int, vertex_set<>, edge_set<>> G3;
+ typedef directed_graph<City, Road, vertex_list<>, edge_list<>> G2;
+ typedef directed_graph<City, Road, vertex_set<>, edge_set<>> G3;
test_props<G1>();
- // test_props<G2>();
- // test_props<G3>();
+ test_props<G2>();
+ test_props<G3>();
}
-
return 0;
}
\ No newline at end of file