[Boost-commit] svn:boost r46681 - in sandbox/SOC/2008/graphs/trunk: boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-25 11:29:34

Author: asutton
Date: 2008-06-25 11:29:33 EDT (Wed, 25 Jun 2008)
New Revision: 46681
URL: http://svn.boost.org/trac/boost/changeset/46681

Log:
Implemented an edge iterator for directed edges.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/colors.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp  |    68 +++++++++++++++++++++++++++++++++++++++ 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp |    68 ++++++++++++++++++++++++++++++++++----- 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile             |     1                                         
   3 files changed, 126 insertions(+), 11 deletions(-)

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/colors.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/colors.hpp	2008-06-25 11:29:33 EDT (Wed, 25 Jun 2008)
@@ -0,0 +1,36 @@
+
+#ifndef COLORS_HPP
+#define COLORS_HPP
+
+/**
+ * Default color types for this library.
+ */
+enum color {
+    white_color,
+    gray_color,
+    black_color,
+    red_color,
+    green_color,
+    blue_color
+};
+
+/**
+ * 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.
+ */
+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; }
+};
+
+
+
+#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-06-25 11:29:33 EDT (Wed, 25 Jun 2008)
@@ -1,8 +1,8 @@
-
 #ifndef DIRECTED_EDGE_HPP
 #define DIRECTED_EDGE_HPP
 
 #include <iosfwd>
+#include <iterator>
 
 /**
  * A directed edge represents an edge in a directed graph. A directed edge is
@@ -86,4 +86,70 @@
 std::ostream& operator<<(std::ostream& os, const directed_edge<O,I>& e)
 { return os << "(" << e.source() << " " << e.target() << ")"; }
 
+/**
+ * The directed edge iterator provides functionality for iterating over the
+ * edges of a directed graph. This is essenitally done by iterating over the
+ * out edges of each vertex in the order in which they were added to the graph.
+ */
+template <typename Graph>
+struct directed_edge_iterator
+{
+    typedef typename Graph::vertex_iterator vertex_iterator;
+    typedef typename Graph::out_edge_iterator edge_iterator;
+
+    typedef std::forward_iterator_tag iterator_category;
+    typedef std::size_t difference_type;
+
+    typedef typename Graph::edge_descriptor value_type;
+    typedef value_type reference;
+    typedef value_type pointer;
+
+    // Used to construct the end iterator.
+    directed_edge_iterator(Graph const& g, vertex_iterator v)
+        : graph(g), vert(v), edge()
+    { }
+
+    // Typically used to construct the begin iterator.
+    directed_edge_iterator(Graph const& g, vertex_iterator v, edge_iterator e)
+        : graph(g), vert(v), edge(e)
+    { }
+
+    inline directed_edge_iterator& operator++()
+    {
+        // If we're not done, increment the current edge. If that increment
+        // pushes the edge iterator off the vertex, move to the next vertex
+        // and reset the edge iterator.
+        if(vert != graph.end_vertices()) {
+            ++edge;
+            if(edge == graph.end_out_edges(*vert)) {
+                ++vert;
+                if(vert != graph.end_vertices()) {
+                    edge = graph.begin_out_edges(*vert);
+                }
+                else {
+                    edge = edge_iterator();
+                }
+            }
+        }
+        return *this;
+    }
+
+    inline reference operator*() const
+    { return  *edge; }
+
+    Graph const& graph;
+    vertex_iterator vert;
+    edge_iterator edge;
+};
+
+template <typename Graph>
+inline bool
+operator==(directed_edge_iterator<Graph> const& a, directed_edge_iterator<Graph> const& b)
+{ return (a.vert == b.vert) && (a.edge == b.edge); }
+
+template <typename Graph>
+inline bool
+operator!=(directed_edge_iterator<Graph> const& a, directed_edge_iterator<Graph> const& b)
+{ return !(a == b); }
+
 #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-06-25 11:29:33 EDT (Wed, 25 Jun 2008)
@@ -99,6 +99,8 @@
     // Additional iterator types. I'm cheating here and using the edge
     // descriptor to piggyback type information to these iterators. It kinda
     // works.
+    typedef directed_edge_iterator<this_type> edge_iterator;
+    typedef std::pair<edge_iterator, edge_iterator> edge_range;
     typedef basic_out_iterator<edge_descriptor> out_edge_iterator;
     typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
     typedef basic_in_iterator<edge_descriptor> in_edge_iterator;
@@ -245,15 +247,20 @@
     incident_edges_size_type degree(vertex_descriptor v) const;
     //@}
 
-    /** @name Out Edge Iterator */
+    /** @name Iterators */
     //@{
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
+    vertex_range vertices() const;
+
+    edge_iterator begin_edges() const;
+    edge_iterator end_edges() const;
+    edge_range edges() const;
+
     out_edge_iterator begin_out_edges(vertex_descriptor) const;
     out_edge_iterator end_out_edges(vertex_descriptor) const;
     out_edge_range out_edges(vertex_descriptor) const;
-    //@}
 
-    /** @name In Edge Iterator */
-    //@{
     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;
@@ -778,16 +785,57 @@
     return _verts.vertex(v).degree();
 }
 
-/**
- * Return an iterator to the first out edge of the given vertex.
- */
+/** Return an iterator to the first vertex. */
 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
+typename directed_graph<VP,EP,VS,ES>::vertex_iterator
+directed_graph<VP,EP,VS,ES>::begin_vertices() const
+{ return _verts.begin_vertices(); }
+
+/** Return an iterator past the end of the vertices. */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_iterator
+directed_graph<VP,EP,VS,ES>::end_vertices() const
+{ return _verts.end_vertices(); }
+
+/** Return an iterator range over the vertices in the graph. */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_range
+directed_graph<VP,EP,VS,ES>::vertices() const
+{ return _verts.vertices(); }
+
+/** Return an iterator to the first edge. */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_iterator
+directed_graph<VP,EP,VS,ES>::begin_edges() const
 {
-    return out_edge_iterator(v, _verts.vertex(v).begin_out());
+    // Gotta handle the case where the graph is empty.
+    vertex_iterator i = begin_vertices();
+    if(i != end_vertices()) {
+        return edge_iterator(*this, i, begin_out_edges(*i));
+    }
+    else {
+        return edge_iterator(*this, i);
+    }
 }
 
+/** Return an iterator past the end of the edges. */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_iterator
+directed_graph<VP,EP,VS,ES>::end_edges() const
+{ return edge_iterator(*this, end_vertices()); }
+
+/** Return an iterator range over the edges in the graph. */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_range
+directed_graph<VP,EP,VS,ES>::edges() const
+{ return std::make_pair(begin_edges(), end_edges()); }
+
+/** Return an iterator to the first out edge of the given vertex. */
+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()); }
+
 /**
  * Return an iterator past the end of then out edges of the given vertex.
  */

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	2008-06-25 11:29:33 EDT (Wed, 25 Jun 2008)
@@ -5,3 +5,4 @@
 exe map : map.cpp : <include>../../ <include>/usr/local/include ;
 exe test : test.cpp : <include>../../ <include>/usr/local/include ;
 exe props : props.cpp : <include>../../ <include>/usr/local/include ;
+exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp	2008-06-25 11:29:33 EDT (Wed, 25 Jun 2008)
@@ -0,0 +1,45 @@
+
+#include <iostream>
+
+#include <boost/graphs/directed_graph.hpp>
+
+#include "square.hpp"
+
+using namespace std;
+
+typedef vertex_vector<> vvec;
+typedef edge_vector<> evec;
+
+void directed();
+
+int main()
+{
+    directed();
+
+    return 0;
+}
+
+void directed()
+{
+    typedef directed_graph<int, int, vvec, evec> Graph;
+    Graph g;
+    make_square(g);
+
+    Graph::edge_range rng = g.edges();
+    for(Graph::edge_iterator i = rng.first; i != rng.second; ++i) {
+        cout << *i << endl;
+    }
+
+
+    /*
+    // How can we iterate over the edges of a directed graph.. Iterate over
+    // the out edges of each vertex.
+    Graph::vertex_range v = g.vertices();
+    for(Graph::vertex_iterator i = v.first; i != v.second; ++i) {
+        Graph::out_edge_range o = g.out_edges(*i);
+        for(Graph::out_edge_iterator j = o.first; j != o.second; ++j) {
+            cout << g[*i] << " " << g[*j] << endl;
+        }
+    }
+    */
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/square.hpp	2008-06-25 11:29:33 EDT (Wed, 25 Jun 2008)
@@ -0,0 +1,18 @@
+
+#ifndef SQUARE_HPP
+#define SQUARE_HPP
+
+// Make a K4 square
+
+template <typename G>
+void make_square(G& g)
+{
+    typename G::vertex_descriptor v[4];
+    for(int i = 0; i < 4; ++i) v[i] = g.add_vertex(i);
+    for(int i = 0; i < 3; ++i) g.add_edge(v[i], v[i + 1], i);
+    g.add_edge(v[3], v[0], 3);
+    g.add_edge(v[0], v[2], 4);
+    g.add_edge(v[1], v[3], 5);
+}
+
+#endif