From: asutton_at_[hidden]
Date: 2008-07-24 11:05:51
Author: asutton
Date: 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
New Revision: 47759
URL: http://svn.boost.org/trac/boost/changeset/47759
Log:
Finished most of the bfs implementation and a number of little bug fixes and
tweaks to various data structures.
Formalized the directional edge concept and imlemented a wrapper for it.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/algorithm.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/concepts.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/iterator.hpp
- copied, changed from r47721, /sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/utility.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/read.hpp (contents, props changed)
Removed:
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp | 37 +++++++++++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_walk.hpp | 66 +++++++++++++++++++++-----
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/iterator.hpp | 96 +++++++++++++--------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 3 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 27 +++++++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp | 5 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp | 54 +++++++++++++++++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp | 23 ++++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 51 ++++++++++----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 30 +++++++-----
sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp | 65 +++++++++++++++++++++++---
sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp | 4
12 files changed, 302 insertions(+), 159 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -4,13 +4,40 @@
#include <boost/graphs/properties.hpp>
#include <boost/graphs/colors.hpp>
+#include <boost/graphs/directional_edge.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/utility.hpp>
+#include <boost/graphs/algorithms/iterator.hpp>
+struct bfs_visitor
+{
+ template <typename Graph, typename Vertex>
+ inline void discover_vertex(Graph const& g, Vertex v)
+ { }
+
+ template <typename Graph, typename Vertex>
+ inline void finish_vertex(Graph const& g, Vertex v)
+ { }
+
+ template <typename Graph, typename Vertex>
+ inline void gray_target(Graph const& g, Vertex v)
+ { }
+
+ template <typename Graph, typename Vertex>
+ inline void black_target(Graph const& g, Vertex v)
+ { }
+
+ template <typename Graph, typename Edge>
+ inline void tree_edge(Graph const& g, Edge e)
+ { }
+
+ template <typename Graph, typename Edge>
+ inline void non_tree_edge(Graph const& g, Edge e)
+ { }
+
+};
+
+#include <boost/graphs/algorithms/breadth_first/algorithm.hpp>
#include <boost/graphs/algorithms/breadth_first/vertex_walk.hpp>
#include <boost/graphs/algorithms/breadth_first/edge_walk.hpp>
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/algorithm.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/algorithm.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -0,0 +1,155 @@
+
+#ifndef BREADTH_FIRST_ALGORITHM_HPP
+#define BREADTH_FIRST_ALGORITHM_HPP
+
+// Contents:
+//
+// breadth_first_visit_edge - Visits a single edge.
+// breadth_first_visit_vertex - Visits a single vertex and all of its incident edges.
+// breadth_first_walk - Visits all queued vertices
+// breadth_first_visit (single) - Visits all vertices connected to the given vertex.
+// breadth_first_visit (mulitple) - Visits all vertices connected to the given vertices
+// breadth_first_search - Visits all vertices
+
+// Interesting options for extension:
+// visit_if - Only visit the vertex if the predicate is satsified.
+// visit_until - Continue the search until some predicate has been reached.
+
+template <typename Graph, typename Vertex, typename Edge, typename Visitor, typename ColorMap, typename Queue>
+void breadth_first_visit_edge(Graph const& g, Vertex u, Edge e, Visitor vis, ColorMap color, Queue& queue)
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+
+ // Look at the color of the target vertex and decide what to do with it.
+ Vertex v = e.target();
+ typename ColorMap::value_type c = color(v);
+ if(c == ColorTraits::white()) {
+ // Visit the new edge and vertex.
+ vis.tree_edge(g, e);
+ color(v) = ColorTraits::gray();
+ queue.push(v);
+ vis.discover_vertex(g, v);
+ }
+ else {
+ // Handle other cases - nontree edges, gray targets, black, etc.
+ vis.non_tree_edge(g, e);
+ if(c == ColorTraits::gray()) {
+ vis.gray_target(g, v);
+ }
+ else {
+ vis.black_target(g, v);
+ }
+ }
+}
+
+template <typename Graph, typename Vertex, typename Visitor, typename ColorMap, typename Queue>
+void
+breadth_first_visit_vertex(Graph const& g, Vertex u, Visitor vis, ColorMap color, Queue& queue)
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+ typedef typename Graph::edge_descriptor Edge;
+ typedef typename Graph::incident_edge_range EdgeRange;
+
+ EdgeRange edges = g.incident_edges(u);
+ for( ; edges.first != edges.second; ++edges.first) {
+ // Impose direction on this edge (if none exists).
+ directional_edge<Edge> e(*edges.first, u);
+ breadth_first_visit_edge(g, u, e, vis, color, queue);
+ }
+ color(u) = ColorTraits::black();
+ vis.finish_vertex(g, u);
+}
+
+template <typename Graph, typename Visitor, typename ColorMap, typename Queue>
+void
+breadth_first_walk(Graph const& g, Visitor vis, ColorMap color, Queue& queue)
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::edge_descriptor Edge;
+ typedef typename Graph::incident_edge_range EdgeRange;
+
+ // Run the walk on the vertices attached to start.
+ while(!queue.empty()) {
+ Vertex u = queue.front();
+ queue.pop();
+ breadth_first_visit_vertex(g, u, vis, color, queue);
+ }
+}
+
+template <
+ typename Graph,
+ typename Visitor,
+ typename ColorMap = optional_vertex_map<Graph, color>,
+ typename Queue = std::queue<typename Graph::vertex_descriptor>>
+void
+breadth_first_visit(
+ Graph const& g,
+ typename Graph::vertex_descriptor start,
+ Visitor vis,
+ ColorMap color = ColorMap(),
+ Queue queue = Queue())
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+ typedef typename Graph::vertex_descriptor Vertex;
+
+ detail::optional_prop_init(g, color, ColorTraits::white());
+
+ // Initialize the starting vertex and run the search.
+ color(start) = ColorTraits::white();
+ queue.push(start);
+ vis.discover_vertex(g, start);
+ breadth_first_walk(g, vis, color, queue);
+}
+
+
+template <
+ typename Graph,
+ typename Iter,
+ typename Visitor,
+ typename ColorMap = optional_vertex_map<Graph, color>,
+ typename Queue = std::queue<typename Graph::vertex_descriptor>>
+void
+breadth_first_visit(Graph const& g, Iter f, Iter l, Visitor vis, ColorMap color = ColorMap(), Queue queue = Queue())
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+ typedef typename Graph::vertex_descriptor Vertex;
+
+ detail::optional_prop_init(g, color, ColorTraits::white());
+
+ // Initialize the strarting vertices.
+ for( ; f != l; ++f) {
+ Vertex v = *f;
+ color(v) = ColorTraits::gray();
+ queue.push(v);
+ vis.discover_vertex(v, g);
+ }
+ breadth_first_walk(g, vis, color, queue);
+}
+
+template <
+ typename Graph,
+ typename Visitor,
+ typename ColorMap = optional_vertex_map<Graph, color>,
+ typename Queue = std::queue<typename Graph::vertex_descriptor>>
+void
+breadth_first_search(Graph& g, Visitor vis, ColorMap color = ColorMap(), Queue queue = Queue())
+{
+ typedef color_traits<typename ColorMap::value_type> ColorTraits;
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::vertex_range VertexRange;
+
+ detail::optional_prop_init(g, color, ColorTraits::white());
+
+ // Iterate over all vertices, running BFS visit on each that hasn't been
+ // discovered yet.
+ VertexRange verts = g.vertices();
+ for( ; verts.first != verts.second; ++verts.first) {
+ Vertex v = *verts.first;
+ if(color(v) == ColorTraits::white()) {
+ breadth_first_visit(g, v, vis, color, queue);
+ }
+ }
+}
+
+#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
+++ (empty file)
@@ -1,98 +0,0 @@
-
-#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
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_walk.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_walk.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_walk.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -4,8 +4,6 @@
#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
@@ -18,6 +16,35 @@
// prooperty map that counts the number of dependent edges, only visiting when
// the count reaches 0. This probably only applies to the traversal.
+/**
+ * The status object contains information about the current state of the breadth
+ * first edge algorithm. Specifically, this provides the walk state and also
+ * the color map used by the algorithm.
+ */
+template <typename Graph, typename ColorMap>
+struct breadth_first_edge_status
+{
+ typedef typename Graph::vertex_descriptor vertex_descriptor;
+ typedef typename Graph::edge_descriptor edge_descriptor;
+
+ breadth_first_edge_status(edge_descriptor e, vertex_descriptor u, vertex_descriptor v, ColorMap c)
+ : cur(e), src(u), tgt(v), color(c)
+ { }
+
+ inline edge_descriptor current() const
+ { return cur; }
+
+ inline vertex_descriptor source() const
+ { return src; }
+
+ inline vertex_descriptor target() const
+ { return tgt; }
+
+ edge_descriptor cur;
+ vertex_descriptor src, tgt;
+
+ ColorMap color;
+};
/**
* The edge-walk implements a breadth-first walk that provides access to the
@@ -31,13 +58,15 @@
*
* This algorithm object essentially provides the next tree edge at each step.
*
+ * As a walk, the returned edge must be directional.
+ *
* @requires IncidenceGraph<Graph>
* @requires ReadWritePropertyMap<ColorMap>
* @requires Queue<Queue>
*/
template <
typename Graph,
- typename ColorMap = generic_vertex_map<Graph, color>,
+ typename ColorMap = optional_vertex_map<Graph, color>,
typename Queue = std::queue<typename Graph::vertex_descriptor>>
struct breadth_first_edge_walk
{
@@ -48,10 +77,11 @@
typedef Graph graph_type;
typedef typename Graph::vertex_descriptor vertex_descriptor;
- typedef typename Graph::edge_descriptor edge_descriptor;
+ typedef directional_edge<typename Graph::edge_descriptor> edge_descriptor;
typedef typename Graph::incident_edge_range IncidenceRange;
- typedef breadth_first_edge_iterator<this_type> iterator;
+ typedef breadth_first_edge_status<Graph, ColorMap> status_type;
+ typedef algorithm_iterator<this_type> iterator;
breadth_first_edge_walk(Graph& g, vertex_descriptor v)
: graph(g), color(g, ColorTraits::white()), queue(), range()
@@ -165,11 +195,11 @@
}
/**
- * Return the current edge "pointed" to by the algorithm, which will be
+ * Return the current edge "pointed" to by the algorithm. This will be
* null if the queue is empty (the algorithm has finished).
*/
- inline edge_descriptor edge() const
- { return queue.empty() ? edge_descriptor() : *range.first; }
+ inline edge_descriptor current() const
+ { return queue.empty() ? edge_descriptor() : edge_descriptor(*range.first, queue.front()); }
/**
* Returns the source vertex of the current edge. This is the vertex in the
@@ -183,7 +213,11 @@
* pointed to by the algorithm.
*/
inline vertex_descriptor target() const
- { return queue.empty() ? vertex_descriptor() : edge().opposite(source()); }
+ { return queue.empty() ? vertex_descriptor() : current().target(); }
+
+ /** Return a copy of the current status. */
+ inline status_type status() const
+ { return status_type(current(), source(), target(), color); }
/** Return true if the current target has already been visited. */
bool discoverable() const
@@ -211,7 +245,7 @@
*/
template <
typename Graph,
- typename ColorMap = generic_vertex_map<Graph, color>,
+ typename ColorMap = optional_vertex_map<Graph, color>,
typename Queue = std::queue<typename Graph::vertex_descriptor>>
struct breadth_first_edge_traversal
{
@@ -226,7 +260,8 @@
typedef color_traits<Color> ColorTraits;
typedef breadth_first_edge_walk<Graph, ColorMap, Queue> Walk;
- typedef breadth_first_edge_iterator<this_type> iterator;
+ typedef breadth_first_edge_status<Graph, ColorMap> status_type;
+ typedef algorithm_iterator<this_type> iterator;
breadth_first_edge_traversal(Graph& g)
: graph(g), color(g, ColorTraits::white()), range(g.vertices())
@@ -249,7 +284,7 @@
}
// Did we just walk off the edge?
- if(!walk.edge()) {
+ if(!walk.current()) {
// Find the next connected component.
while(range.first != range.second && !discoverable()) {
++range.first;
@@ -263,8 +298,11 @@
}
}
- inline edge_descriptor edge() const
- { return walk.edge(); }
+ inline status_type status() const
+ { return status_type(current(), source(), target(), color); }
+
+ inline edge_descriptor current() const
+ { return walk.current(); }
inline vertex_descriptor source() const
{ return walk.source(); }
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/concepts.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/concepts.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -0,0 +1,100 @@
+
+#ifndef ALGORITHM_CONCEPTS_HPP
+#define ALGORITHM_CONCEPTS_HPP
+
+#if BOOST_HAS_CONCEPTS
+
+// Why are there concepts for algorithm objects? It seems unlikely that anybody
+// would ever build generic algorithms over generic algorithm objects. When is
+// the algorithm replaceable?
+//
+// One reason is to help describe requirements template arguments to the
+// algorithm iterator (which pretty much just requires an Algorithm, but it's
+// nice to know what else might work there).
+//
+// The other reason is simply to provide a taxonomy of graph algorithm styles
+// and what interfaces they /should/ support in order to be generically useful.\
+// This is more a way of telling programmers: if you're using this algorithm,
+// you have these options.
+
+/**
+ * The Algorithm concept describes common requirements on all algorithm objects.
+ * Specifically, an algorithm object must provide a next() function that puts
+ * the algorithm in the next logical state.
+ *
+ * The status() function returns an object that encapsulates the current status
+ * of the algorithm, but not necessarily the entire state of the algorithm.
+ */
+concept Algorithm<typename X>
+{
+ typename status_type;
+ void X::next();
+ status_type X::status() const;
+};
+
+/**
+ * The vertex state concept requires that algorithms modeling this concept
+ * provide access to the current vertex.
+ */
+concept VertexState<typename X>
+{
+ typename vertex_descriptor;
+ vertex_descriptor X::current();
+};
+
+/**
+ * The edge state concept requires that algorithms modeling this concept provide
+ * access to the current edge.
+ */
+concept EdgeState<typename X>
+{
+ typename edge_descriptor;
+ edge_descriptor X::current() const;
+}
+
+/**
+ * The walk state is a refinemnet of edge state that denotes the movement across
+ * the current edge, imposing source/target semantics on the edge, even when
+ * none may exist. Algorithms that walk across edge states require that the
+ * the edge descriptor be directional.
+ */
+concept WalkState<typename X> : EdgeState<X>
+{
+ typename vertex_descriptor;
+ requires<DirectionalEdge<edge_descriptor>;
+ vertex_descriptor Algorithm::source() const { source(this->current(); }
+ vertex_descriptor Algorithm::target() const { target(this->current(); }
+}
+
+/**
+ * A VertexAlgorithm is any algorithm that provides access to the current
+ * vertex, and the status returned by this algorithm also provides access to the
+ * current vertex.
+ */
+concept VertexAlgorithm<typename A> : Algorithm<A>, VertexState<A>
+{
+ requires VertexState<status_type>;
+};
+
+/**
+ * An EdgeAlgorithm is any algorithm that provides access to the current
+ * edge, and the status returned by this algorithm also provides access to the
+ * current vertex.
+ */
+concept EdgeAlgorithm<typename A> : Algorithm<A>, EdgeState<A>
+{
+ requires EdgeState<status_type>;
+};
+
+/**
+ * A WalkAlgorithm is any algorithm that provides access to the current state
+ * of the walk (i.e., the current edge and its source and target vertices).
+ */
+concept WalkAlgorithm<typename A> : Algorithm<A>, WalkState<A>
+{
+ requires WalkState<status_type>;
+};
+
+#endif /* BOOST_HAS_CONCEPTS */
+
+#endif
Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/iterator.hpp (from r47721, /sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/edge_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/iterator.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -1,98 +1,68 @@
-#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); }
-}
+#ifndef ALGORITHM_ITERATOR_HPP
+#define ALGORITHM_ITERATOR_HPP
/**
- * Provide an iterator abstraction over the walk. Dereferencing a walk iterator
- * returns the walk itself.
+ * Provide an iterator abstraction over algorithm objects. Dereferencing this
+ * iterator returns the algorithm which can then be queried for its current
+ * state.
*
* 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?
+ *
+ * @requires Algorithm<Algorithm>
+ *
+ * @todo This probably works on any algorithm as long as it provides a next
+ * function.
*/
-template <typename Walk>
-struct breadth_first_edge_iterator
+template <typename Algorithm>
+struct algorithm_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;
+ typedef Algorithm value_type;
+ typedef value_type const& reference;
+ typedef value_type const* pointer;
// Construct an end iterator.
- breadth_first_edge_iterator()
- : walk()
+ algorithm_iterator()
+ : algo()
{ }
- // Explicitly build an iterator over the state of the given walk.
- breadth_first_edge_iterator(walk_type* walk)
- : walk(walk)
+ // Explicitly build an iterator over the state of the given algo.
+ algorithm_iterator(Algorithm* algo)
+ : algo(algo)
{ }
- inline breadth_first_edge_iterator& operator++()
- { walk->next(); return *this; }
+ inline algorithm_iterator& operator++()
+ { algo->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.
+ // end if a) the algo pointer is null or b) the current edge is null.
bool end() const
- { return !walk || (walk && !walk->edge()); }
+ { return !algo || (algo && !algo->current()); }
// 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
+ inline bool operator==(algorithm_iterator const& x) const
{
- return (!walk && x.end())
- || (!x.walk && end())
- || (walk && x.walk && walk->edge() == x.walk->edge());
+ return (!algo && x.end())
+ || (!x.algo && end())
+ || (algo && x.algo && algo->current() == x.algo->current());
}
- inline bool operator!=(breadth_first_edge_iterator const& x) const
+ inline bool operator!=(algorithm_iterator const& x) const
{ return !operator==(x); }
inline reference operator*() const
- { return detail::make_rooted_edge(walk->edge(), walk->source()); }
+ { return *algo; }
- inline walk_type const* operator->() const
- { return walk; }
+ inline pointer operator->() const
+ { return algo; }
- walk_type* walk;
+ Algorithm* algo;
};
#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/utility.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/utility.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -0,0 +1,35 @@
+
+#ifndef ALGORITHM_UTILITY_HPP
+#define ALGORITHM_UTILITY_HPP
+
+namespace detail
+{
+ // Optionally initialize the container, but not if the map is already
+ // initialized.
+ template <typename Graph, typename Map>
+ void do_opt_init(Graph const& g, Map& map, typename Map::value_type x)
+ {
+ if(!map.container) {
+ Map t(g, x);
+ map.swap(t);
+ }
+ }
+
+ // Delayed initialization of optional property maps. The default solution
+ // is to do nothing (i.e,. the map is already initialized). Specialized
+ // variants simply swap the given map with one that's actually initialized.
+ template <typename Graph, typename Map>
+ void optional_prop_init(Graph const&, Map&, typename Map::value_type)
+ { }
+
+ template <typename Graph, typename Prop>
+ void optional_prop_init(Graph const& g, optional_vertex_map<Graph, Prop>& map, Prop x)
+ { do_opt_init(g, map, x); }
+
+ template <typename Graph, typename Prop>
+ void optional_prop_init(Graph const g, optional_edge_map<Graph, Prop>& map, Prop x)
+ { do_opt_init(g, map, x); }
+
+}
+
+#endif
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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -4,6 +4,8 @@
#include <iosfwd>
#include <iterator>
+#include <boost/graphs/directional_edge.hpp>
+
/**
* A directed edge represents an edge in a directed graph. A directed edge is
* uniquely identified by its source and target vertices the descriptor into
@@ -218,4 +220,5 @@
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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -246,7 +246,9 @@
*/
//@{
vertex_properties& operator[](vertex_descriptor);
+ vertex_properties const& operator[](vertex_descriptor) const;
edge_properties& operator[](edge_descriptor);
+ edge_properties const& operator[](edge_descriptor) const;
//@}
private:
@@ -915,24 +917,29 @@
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.
- */
+/** Return the properties for the given vertex. */
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 the properties for the given edge.
- */
+/** Return the properties for the given vertex. */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_properties const&
+directed_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v) const
+{ return _verts.properties(v); }
+
+/** Return the properties for the given edge. */
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_properties&
directed_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
-{
- vertex_type& vert = _verts.vertex(e.source());
- return vert.get_edge_properties(e.out_edge());
-}
+{ return _verts.vertex(e.source()).get_edge_properties(e.out_edge()); }
+
+/** Return the properties for the given edge. */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_properties const&
+directed_graph<VP,EP,VS,ES>::operator[](edge_descriptor e) const
+{ return _verts.vertex(e.source()).get_edge_properties(e.out_edge()); }
#undef BOOST_GRAPH_DG_PARAMS
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -0,0 +1,63 @@
+
+#ifndef DIRECTIONAL_EDGE_HPP
+#define DIRECTIONAL_EDGE_HPP
+
+// This basically wraps a concept called DirectionalEdge. A DirectionalEdge
+// is one that has directionality being imposed on it. Specializations of
+// these edge should be found with the graph types.
+
+namespace detail
+{
+ // By default, we assume that the edge is directed.
+ template <typename Edge>
+ struct directional_edge_adapter : Edge
+ {
+ typedef typename Edge::vertex_descriptor Vertex;
+
+ inline directional_edge_adapter()
+ : Edge()
+ { }
+
+ inline directional_edge_adapter(Edge e, Vertex)
+ : Edge(e)
+ { }
+
+ inline directional_edge_adapter(Vertex s, Vertex t)
+ : Edge(s, t)
+ { }
+ };
+}
+
+/**
+ * The diretional edge type forces directionality onto the given edge structure
+ * even when non exists. That this is not the same as a directed edge, which has
+ * a distinct direction to it. This simply imposes a direction over the edge
+ * with respect to the a source vertex. For directed graphs, this essentially
+ * does nothing. For undirected graphs, the source vertex is used to compute
+ * the opposite end (target).
+ *
+ * Directional edges are intended for use in algorithms that walk the graph
+ * structure. The act of walking from one vertex to another adds an implicit
+ * directionality to the edge. This class embodies that directionality for both
+ * directed and undirected graphs.
+ *
+ * Directional edge descriptors can be used interchangeably with normal edge
+ * descriptors.
+ */
+template <typename Edge>
+struct directional_edge
+ : detail::directional_edge_adapter<Edge>
+{
+ typedef Edge edge_descriptor;
+ typedef typename Edge::vertex_descriptor vertex_descriptor;
+
+ inline directional_edge()
+ : detail::directional_edge_adapter<Edge>()
+ { }
+
+ inline directional_edge(edge_descriptor e, vertex_descriptor v)
+ : detail::directional_edge_adapter<Edge>(e, v)
+ { }
+};
+
+#endif
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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -22,7 +22,7 @@
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 boost::remove_const<typename base_value_type::first_type>::type vertex_descriptor;
typedef typename base_value_type::second_type edge_pair;
typedef typename edge_pair::first_type edge_properties;
typedef typename edge_pair::second_type in_descriptor;
@@ -59,6 +59,9 @@
inline vertex_descriptor opposite() const
{ return target(); }
+ inline basic_out_iterator& operator=(basic_out_iterator const& x)
+ { vert = x.vert; src = x.src; iter = x.iter; return *this; }
+
inline basic_out_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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -164,55 +164,87 @@
typedef typename map_type::key_type key_type;
typedef typename map_type::reference reference;
+ // Delay initialization...
+ inline property_wrapper()
+ : container(), map()
+ { }
+
// Construct an underlying store over the map.
- property_wrapper(Graph const& g, value_type const& x = value_type())
+ inline 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)
+ // Construct the map over a user-provided property map. No container needed.
+ inline property_wrapper(map_type map)
: container(), map(map)
{ }
- value_type& operator()(key_type const& key)
+ inline value_type& operator()(key_type const& key)
{ return map(key); }
- value_type const& operator()(key_type const& key) const
+ inline value_type const& operator()(key_type const& key) const
{ return map(key); }
+ inline void swap(property_wrapper& x)
+ {
+ using std::swap;
+ container.swap(x.container);
+ swap(map, x.map);
+ }
+
boost::shared_ptr<container_type> container;
map_type map;
};
+/**
+ * The optional vertex map allows a user-provided property map or a self-
+ * contained exterior property to be passed to a generic function. The user
+ * provided property map is not required to be constructed over an exterior
+ * property.
+ */
template <typename Graph, typename Property>
-struct generic_vertex_map
+struct optional_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())
+ inline optional_vertex_map()
+ : base_type()
+ { }
+
+ inline optional_vertex_map(Graph const& g, Property const& x = Property())
: base_type(g, x)
{ }
- generic_vertex_map(map_type map)
+ inline optional_vertex_map(map_type map)
: base_type(map)
{ }
};
+/**
+ * The optional edge map allows a user-provided property map or a self-
+ * contained exterior property to be passed to a generic function. The user
+ * provided property map is not required to be constructed over an exterior
+ * property.
+ */
template <typename Graph, typename Property>
-struct generic_edge_map
+struct optional_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())
+ inline optional_edge_map()
+ : base_type()
+ { }
+
+ inline optional_edge_map(Graph const& g, Property const& x = Property())
: base_type(g, x)
{ }
- generic_edge_map(map_type map)
+ inline optional_edge_map(map_type map)
: base_type(map)
{ }
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -2,6 +2,8 @@
#ifndef CONTAINER_PROPERTY_MAP_HPP
#define CONTAINER_PROPERTY_MAP_HPP
+#include <algorithm>
+
template <typename Container>
struct container_property_map
{
@@ -9,17 +11,24 @@
typedef typename Container::value_type value_type;
typedef value_type& reference;
- container_property_map(Container& cont)
- : container(cont)
+ inline container_property_map()
+ : container(0)
+ { }
+
+ inline container_property_map(Container& cont)
+ : container(&cont)
{ }
- value_type& operator()(key_type const& key)
- { return container[key]; }
+ inline value_type& operator()(key_type const& key)
+ { return (*container)[key]; }
+
+ inline value_type const& operator()(key_type const& key) const
+ { return (*container)[key]; }
- value_type const& operator()(key_type const& key) const
- { return container[key]; }
+ inline void swap(container_property_map& x)
+ { std::swap(container, x.container); }
- Container& container;
+ Container* container;
};
#endif
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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -5,6 +5,7 @@
#include <iosfwd>
#include <boost/unordered_pair.hpp>
+#include <boost/graphs/directional_edge.hpp>
/**
* This structure implements an unordered edge - sort of. Because the undirected
@@ -71,7 +72,7 @@
inline vertex_descriptor second() const
{ return ends.second(); }
- inline vertex_descriptor opposite(vertex_descriptor v)
+ inline vertex_descriptor opposite(vertex_descriptor v) const
{ return v == first() ? second() : first(); }
//@}
@@ -125,34 +126,34 @@
return hash_value(e.prop);
}
-/**
- * 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
+namespace detail
{
-public:
- typedef typename Edge::vertex_descriptor vertex_descriptor;
-
- /** @name Constructors */
- inline rooted_undirected_edge(Edge const& edge, vertex_descriptor src)
- : Edge(edge), src(src)
- { }
+ // Provide an implementation of directionality for undirected edges.
+ template <typename Vert, typename Prop>
+ struct directional_edge_adapter<undirected_edge<Vert,Prop>>
+ : undirected_edge<Vert,Prop>
+ {
+ inline directional_edge_adapter()
+ : undirected_edge<Vert, Prop>(), src()
+ { }
+
+ inline directional_edge_adapter(undirected_edge<Vert,Prop> e, Vert s)
+ : undirected_edge<Vert,Prop>(e), src(s)
+ { }
+
+ inline directional_edge_adapter(Vert s, Vert t)
+ : undirected_edge<Vert,Prop>(s, t), src(s)
+ { }
- /** Return the source of the rooted edge. */
- inline vertex_descriptor source() const
- { return src; }
+ inline Vert source() const
+ { return src; }
- /** Return the target of the rooted edge. */
- inline vertex_descriptor target() const
- { return this->opposite(src); }
+ inline Vert target() const
+ { return this->opposite(src); }
- vertex_descriptor src;
-};
+ Vert src;
+ };
+}
/**
* The undirected edge iterator simply wraps the iterator over the global edge
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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -198,7 +198,9 @@
*/
//@{
vertex_properties& operator[](vertex_descriptor);
+ vertex_properties const& operator[](vertex_descriptor) const;
edge_properties& operator[](edge_descriptor);
+ edge_properties const& operator[](edge_descriptor) const;
//@}
mutable property_store _props;
@@ -724,25 +726,29 @@
return _verts.vertex(v).degree();
}
-/**
- * Return the properties for the given vertex.
- */
+/** Return the properties for the given vertex. */
template <BOOST_GRAPH_UG_PARAMS>
typename undirected_graph<VP,EP,VS,ES>::vertex_properties&
undirected_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v)
-{
- return _verts.properties(v);
-}
+{ return _verts.properties(v); }
-/**
- * Return the properties for the given edge.
- */
+/** Return the properties for the given vertex. */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_properties const&
+undirected_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v) const
+{ return _verts.properties(v); }
+
+/** Return the properties for the given edge. */
template <BOOST_GRAPH_UG_PARAMS>
typename undirected_graph<VP,EP,VS,ES>::edge_properties&
undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
-{
- return _props.properties(e.properties());
-}
+{ return _props.properties(e.properties()); }
+
+/** Return the properties for the given edge. */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_properties const&
+undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e) const
+{ return _props.properties(e.properties()); }
#undef BOOST_GRAPH_UG_PARAMS
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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -1,8 +1,10 @@
#include <iostream>
+#include <fstream>
#include <queue>
#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/directed_graph.hpp>
#include <boost/graphs/algorithms/breadth_first.hpp>
#include "typestr.hpp"
@@ -10,21 +12,33 @@
using namespace std;
+struct edge_printer : bfs_visitor
+{
+ template <typename Graph, typename Edge>
+ void tree_edge(Graph const& g, Edge e)
+ {
+ typedef typename Graph::vertex_descriptor Vertex;
+ Vertex u = e.source();
+ Vertex v = e.target();
+ cout << "(" << g[u] << g[v] << ") ";
+ }
+};
+
template <typename Graph, typename Walk>
void iterate(Graph& g, Walk& walk)
{
typedef typename Walk::vertex_descriptor Vertex;
- typedef typename Walk::iterator Iterator;
- typedef typename Iterator::value_type Edge;
+ typedef algorithm_iterator<Walk> Iterator;
typedef pair<Iterator, Iterator> Range;
Range rng(walk.begin(), walk.end());
for( ; rng.first != rng.second; ++rng.first) {
Vertex u = rng.first->source();
Vertex v = rng.first->target();
- cout << "edge: " << g[u] << g[v] << endl;
+ cout << "(" << g[u] << g[v] << ") ";
}
+ cout << endl;
}
template <typename Graph>
@@ -40,7 +54,7 @@
typedef breadth_first_edge_walk<Graph> Walk;
cout << "--- default walk ----" << endl;
Walk walk(g, *g.begin_vertices());
- iterate(g, walk );
+ iterate(g, walk);
}
{
@@ -69,16 +83,49 @@
iterate(g, trav);
}
+ {
+ ColorProp colors(g, white_color);
+ ColorMap color(colors);
+
+ cout << "--- algo visit ---" << endl;
+ breadth_first_visit(g, *g.begin_vertices(), edge_printer());
+ cout << endl;
+
+ cout << "--- algo multi visit ---" << endl;
+ breadth_first_visit(g, g.begin_vertices(), next(g.begin_vertices(), 2), edge_printer());
+ cout << endl;
+
+ cout << "--- algo bfs ---" << endl;
+ breadth_first_search(g, edge_printer());
+ cout << endl;
+ }
+
}
-int main()
+int main(int, char* argv[])
{
- typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
+ {
+ typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
+ Graph g;
+ ifstream f(argv[1]);
+ read(f, g);
+
+ cout << "=== undirected ===" << endl;
+ edge_walk(g);
+ cout << endl;
+ }
- Graph g;
- read(cin, g);
+ {
+ typedef directed_graph<string, string, vertex_set<>, edge_set<>> Graph;
+ Graph g;
+ ifstream f(argv[1]);
+ read(f, g);
+
+ cout << "=== directed ===" << endl;
+ edge_walk(g);
+ cout << endl;
+ }
- edge_walk(g);
return 0;
}
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-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -92,8 +92,8 @@
// 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);
+ optional_vertex_map<Graph, double> my_weights(g, 3.14);
+ optional_vertex_map<Graph, double> your_weights(these_weights);
for(vr.first = g.begin_vertices(); vr.first != vr.second; ++vr.first) {
Vertex v = *vr.first;
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/read.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/read.hpp 2008-07-24 11:05:46 EDT (Thu, 24 Jul 2008)
@@ -0,0 +1,35 @@
+
+#ifndef READ_HPP
+#define READ_HPP
+
+#include <iostream>
+#include <sstream>
+
+/**
+ * Populate the graph based on an incidence list. Here, we're assuming that the
+ * given graph is simple and has properties for both vertices and edges.
+ */
+template <typename Graph>
+void read(std::istream& is, Graph& g)
+{
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::vertex_properties VertexLabel;
+ typedef typename Graph::edge_properties EdgeLabel;
+
+ for(string line; std::getline(is, line); ) {
+ if(line.empty() || line[0] == '#') continue;
+
+ // Force these to be default constructed.
+ VertexLabel ul = VertexLabel();
+ VertexLabel vl = VertexLabel();
+ EdgeLabel el = EdgeLabel();
+ std::stringstream ss(line);
+ ss >> ul >> vl >> el;
+
+ Vertex u = g.add_vertex(ul);
+ Vertex v = g.add_vertex(vl);
+ g.add_edge(u, v, el);
+ }
+}
+
+#endif