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

From: asutton_at_[hidden]
Date: 2008-07-22 11:47:22

Author: asutton
Date: 2008-07-22 11:47:21 EDT (Tue, 22 Jul 2008)
New Revision: 47691
URL: http://svn.boost.org/trac/boost/changeset/47691

Log:
Started implementing iterable BFS's. These apparently shake out int two
distinct types of iteration sequences: vertices and edges. Of course the
edge iteration provides its own difficulties (i.e., with undirected edges)
so I had to introduce a new edge "concept" called a rooted edge, which
implements source and target functions and an adapter type for undirected
edges.

Started adding some basic test data.

Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/data/
   sandbox/SOC/2008/graphs/trunk/libs/graphs/data/disjoint_trees   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/data/tree   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile |     2 ++                                      
   1 files changed, 2 insertions(+), 0 deletions(-)

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-07-22 11:47:21 EDT (Tue, 22 Jul 2008)
@@ -16,3 +16,5 @@
 exe di : di.cpp ;
 
 exe propmaps : propmaps.cpp ;
+
+exe bfs : bfs.cpp ;
\ No newline at end of file

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp	2008-07-22 11:47:21 EDT (Tue, 22 Jul 2008)
@@ -0,0 +1,69 @@
+
+#include <iostream>
+#include <queue>
+
+#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/algorithms/breadth_first.hpp>
+
+#include "typestr.hpp"
+#include "read.hpp"
+
+using namespace std;
+
+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 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;
+    }
+}
+
+template <typename Graph>
+void edge_walk(Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+    typedef exterior_vertex_property<Graph, color> ColorProp;
+    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;
+
+    {
+        cout << "--- walk ---" << endl;
+        ColorProp color_prop(g, white_color);
+        ColorMap color(color_prop);
+        BreadthFirstWalk walk(g, *g.begin_vertices(), color);
+        iterate(g, walk);
+    }
+
+    {
+        cout << "--- traversal ---" << endl;
+        ColorProp color_prop(g, white_color);
+        ColorMap color(color_prop);
+        BreadthFirstTraversal trav(g, color);
+        iterate(g, trav);
+    }
+}
+
+int main()
+{
+    typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
+
+    Graph g;
+    read(cin, g);
+
+    edge_walk(g);
+
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/data/disjoint_trees
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/data/disjoint_trees	2008-07-22 11:47:21 EDT (Tue, 22 Jul 2008)
@@ -0,0 +1,7 @@
+# Small tree 1
+a b 1
+a c 2
+
+# Small tree 2
+q r 3
+q s 4

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/data/tree
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/data/tree	2008-07-22 11:47:21 EDT (Tue, 22 Jul 2008)
@@ -0,0 +1,6 @@
+a b 1
+a c 2
+b d 3
+b e 4
+c f 5
+c g 6