Boost logo

Boost-Commit :

From: asutton_at_[hidden]
Date: 2007-07-09 16:38:43


Author: asutton
Date: 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
New Revision: 7402
URL: http://svn.boost.org/trac/boost/changeset/7402

Log:
Added a path graph generator/inducer and rewrote some of the more
simple inducers to use forward iterators rather than random access.

Added:
   sandbox/SOC/2007/graphs/boost/graph/generators/path_graph.hpp
Text files modified:
   sandbox/SOC/2007/graphs/boost/graph/generators/complete_graph.hpp | 28 +------
   sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp | 21 +++---
   sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp | 80 +++++++++++++-----------
   sandbox/SOC/2007/graphs/boost/graph/generators/prism_graph.hpp | 16 +++-
   sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp | 14 ++-
   sandbox/SOC/2007/graphs/boost/graph/generators/web_graph.hpp | 6 +
   sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp | 11 ++-
   sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp | 129 ++++++++++++++++++++++++++++-----------
   8 files changed, 182 insertions(+), 123 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/generators/complete_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/generators/complete_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/complete_graph.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -10,44 +10,28 @@
 #include <vector>
 #include <boost/utility.hpp>
 #include <boost/graph/graph_traits.hpp>
+#include <boost/graph/generators/options.hpp>
 
 namespace boost
 {
     namespace detail
     {
- template <typename Graph>
- inline void
- complete_edge(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- directed_tag)
- {
- add_edge(u, v, g);
- add_edge(v, u, g);
- }
-
- template <typename Graph>
- inline void
- complete_edge(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- undirected_tag)
- {
- add_edge(u, v, g);
- }
+ template <> struct edge_gen_policy<undirected_tag> { typedef with_forward_edges creation_policy; };
+ template <> struct edge_gen_policy<directed_tag> { typedef with_bidirected_edges creation_policy; };
+ template <> struct edge_gen_policy<bidirectional_tag> { typedef with_bidirected_edges creation_policy; };
     }
 
     template <class Graph, class RandomAccessContainer>
     inline void
     make_complete_graph(Graph& g, size_t k, RandomAccessContainer& verts)
     {
- typename graph_traits<Graph>::directed_category cat;
+ typedef typename graph_traits<Graph>::directed_category Directed;
         for(size_t i = 0; i < k; ++i) {
             verts[i] = add_vertex(g);
         }
         for(size_t i = 0; i < k; ++i) {
             for(size_t j = i + 1; j < k; ++j) {
- detail::complete_edge(g, verts[i], verts[j], cat);
+ detail::generate_edge(g, verts[i], verts[j], Directed());
             }
         }
     }

Modified: sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -9,27 +9,28 @@
 
 #include <vector>
 #include <boost/utility.hpp>
-#include <boost/type_traits/is_convertible.hpp>
 #include <boost/graph/graph_traits.hpp>
 #include <boost/graph/generators/options.hpp>
+#include <boost/graph/generators/path_graph.hpp>
 
 namespace boost
 {
- template <typename Graph,class RandomAccessIterator, class CycleDirection>
- inline void
+ template <typename Graph,class ForwardIterator, class CycleDirection>
+ inline ForwardIterator
     induce_cycle_graph(Graph& g, size_t n,
- RandomAccessIterator iter,
+ ForwardIterator iter,
                        CycleDirection cycle)
     {
- typedef RandomAccessIterator iterator;
+ typename detail::edge_gen_policy<CycleDirection>::creation_policy policy;
 
- for(size_t i = 0; i < n - 1; ++i) {
- iterator u = iter + i, v = next(u);
- detail::add_cycle_edge(g, *u, *v, cycle);
- }
+ // start by inducing a path, saving the last iterator in the chain
+ ForwardIterator last = induce_path_graph(g, n, iter, policy);
 
         // connect the last edge back to the beginning
- detail::add_cycle_edge(g, *(iter + (n - 1)), *iter, cycle);
+ detail::generate_edge(g, *last, *iter, cycle);
+
+ // last element added to the cycle
+ return last;
     }
 
     template <class Graph, class RandomAccessContainer, class CycleDirection>

Modified: sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -24,70 +24,76 @@
     // These options control the direction of edges added to
     // graphs that have form star with a central vertex. These
     // options only apply to directed graphs.
- struct with_inward_spokes { };
     struct with_outward_spokes { };
+ struct with_inward_spokes { };
     struct with_bidirected_spokes
- : public with_inward_spokes
- , public with_outward_spokes
+ : public with_outward_spokes
+ , public with_inward_spokes
+ { };
+
+ // Forward and reverse edge options apply to edges in path
+ // graphs. Note that reverse and bidirected edges only apply
+ // to directed or bidirectional graphs.
+ struct with_forward_edges { };
+ struct with_reverse_edges { };
+ struct with_bidirected_edges
+ : public with_forward_edges
+ , public with_reverse_edges
     { };
 
     namespace detail
     {
- // Helper functions for connecting vertices
+ // These structs are used to map graph-specific options onto
+ // the basic forward, reverse and bidirected edges.
+ template <typename Option> struct edge_gen_policy { };
+
+ template <> struct edge_gen_policy<with_clockwise_cycle> { typedef with_forward_edges creation_policy; };
+ template <> struct edge_gen_policy<with_counterclockwise_cycle> { typedef with_reverse_edges creation_policy; };
+ template <> struct edge_gen_policy<with_bidirected_cycle> { typedef with_bidirected_edges creation_policy; };
+
+ template <> struct edge_gen_policy<with_outward_spokes> { typedef with_forward_edges creation_policy; };
+ template <> struct edge_gen_policy<with_inward_spokes> { typedef with_reverse_edges creation_policy; };
+ template <> struct edge_gen_policy<with_bidirected_spokes> { typedef with_bidirected_edges creation_policy; };
+
 
+ // Helper functions for connecting vertices
         template <typename Graph>
         inline void
- add_cycle_edge(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_clockwise_cycle)
+ generate_edge(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ with_forward_edges)
         { add_edge(u, v, g); }
 
         template <typename Graph>
         inline void
- add_cycle_edge(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_counterclockwise_cycle)
+ generate_edge(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ with_reverse_edges)
         { add_edge(v, u, g); }
 
         template <typename Graph>
         inline void
- add_cycle_edge(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_bidirected_cycle)
+ generate_edge(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ with_bidirected_edges)
         {
             add_edge(u, v, g);
             add_edge(v, u, g);
         }
 
 
- template <typename Graph>
- inline void
- add_spoke_edge(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_outward_spokes)
- { add_edge(u, v, g); }
-
- template <typename Graph>
- inline void
- add_spoke_edge(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_inward_spokes)
- { add_edge(v, u, g); }
-
- template <typename Graph>
+ template <typename Graph, typename EdgeOption>
         inline void
- add_spoke_edge(Graph& g,
+ generate_edge(Graph& g,
                        typename graph_traits<Graph>::vertex_descriptor u,
                        typename graph_traits<Graph>::vertex_descriptor v,
- with_bidirected_spokes)
+ EdgeOption)
         {
- add_edge(u, v, g);
- add_edge(v, u, g);
+ typename edge_gen_policy<EdgeOption>::creation_policy policy;
+ generate_edge(g, u, v, policy);
         }
     }
 }

Added: sandbox/SOC/2007/graphs/boost/graph/generators/path_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/path_graph.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,63 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_GENERATORS_PATH_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_PATH_GRAPH_HXX
+
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/generators/options.hpp>
+
+namespace boost
+{
+ // The path graph P(n) is a tree (or chain).
+
+ template <typename Graph,class ForwardIterator, class EdgeDirection>
+ inline ForwardIterator
+ induce_path_graph(Graph& g, size_t n,
+ ForwardIterator iter,
+ EdgeDirection dir)
+ {
+ // iterate n - 1 times (edges in a chain)
+ for(size_t i = 0; i < n - 1; ++i) {
+ ForwardIterator p = iter++;
+ detail::generate_edge(g, *p, *iter, dir);
+ }
+ return iter;
+ }
+
+ template <class Graph, class RandomAccessContainer, class EdgeDirection>
+ inline void
+ make_path_graph(Graph& g, size_t n,
+ RandomAccessContainer& verts,
+ EdgeDirection dir)
+ {
+ for(size_t i = 0; i < n; ++i) {
+ verts[i] = add_vertex(g);
+ }
+ induce_path_graph(g, n, &verts[0], dir);
+ }
+
+ template <class Graph, class EdgeDirection>
+ inline void
+ make_path_graph(Graph& g, size_t n, EdgeDirection dir)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ std::vector<Vertex> verts(n);
+ make_path_graph(g, n, verts, dir);
+ }
+
+ template <class Graph>
+ inline void
+ make_path_graph(Graph& g, size_t n)
+ {
+ make_path_graph(g, n, with_forward_edges());
+ }
+}
+
+#endif

Modified: sandbox/SOC/2007/graphs/boost/graph/generators/prism_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/generators/prism_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/prism_graph.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -19,20 +19,22 @@
     // The specification of a prism graphs is usually G = Y(m,n) such that
     // G is n concentric cycles with m vertices each.
 
+ // TODO: is it possible to write a forward-only induce for this? Essentially,
+ // we can just walk over all (m*n) vertices and at various places run
+ // different algorithms?
+
     template <
         class Graph,
         class RandomAccessIterator,
         class CycleDirection,
         class SpokeDirection
>
- inline void
+ inline RandomAccessIterator
     induce_prism_graph(Graph& g, size_t m, size_t n,
                        RandomAccessIterator iter,
                        CycleDirection cycle,
                        SpokeDirection spokes)
     {
- typedef RandomAccessIterator iterator;
-
         // start by inducing the n cycles on the graph
         for(size_t i = 0; i < n; ++i) {
             induce_cycle_graph(g, m, iter + (m * i), cycle);
@@ -42,11 +44,13 @@
         // concentric cycles
         for(size_t j = 0; j < n - 1; ++j) {
             for(size_t i = 0; i < m; ++i) {
- iterator u = iter + i + m * j;
- iterator v = iter + i + m * (j + 1);
- detail::add_spoke_edge(g, *u, *v, spokes);
+ RandomAccessIterator u = iter + i + m * j;
+ RandomAccessIterator v = iter + i + m * (j + 1);
+ detail::generate_edge(g, *u, *v, spokes);
             }
         }
+
+ return iter;
     }
 
     template <

Modified: sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -18,15 +18,19 @@
     // As a variant, we could introduce S(m, n) where m is the number of radial
     // vertices and n is the length of paths from the center to the periphery.
 
- template <class Graph, class RandomAccessIterator, class SpokeDirection>
- inline void
+ template <class Graph, class ForwardIterator, class SpokeDirection>
+ inline ForwardIterator
     induce_star_graph(Graph& g, size_t n,
- RandomAccessIterator iter,
+ ForwardIterator iter,
                       SpokeDirection spokes)
     {
- for(size_t i = 1; i < n; ++i) {
- detail::add_spoke_edge(g, *iter, *(iter + i), spokes);
+ ForwardIterator center = iter++;
+ for(size_t i = 0; i < n - 1; ++i) {
+ detail::generate_edge(g, *center, *iter++, spokes);
         }
+
+ // return the center of the star
+ return center;
     }
 
     template <class Graph, class RandomAccessContainer, class SpokeDirection>

Modified: sandbox/SOC/2007/graphs/boost/graph/generators/web_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/generators/web_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/web_graph.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -25,7 +25,7 @@
         class CycleDirection,
         class SpokeDirection
>
- inline void
+ inline RandomAccessIterator
     induce_web_graph(Graph& g, size_t m, size_t n,
                       RandomAccessIterator iter,
                       CycleDirection cycle,
@@ -40,8 +40,10 @@
         for(size_t i = 0; i < m; ++i) {
             iterator u = iter + i + m * (n - 1);
             iterator v = iter + i + m * (n);
- detail::add_spoke_edge(g, *u, *v, spokes);
+ detail::generate_edge(g, *u, *v, spokes);
         }
+
+ return iter;
     }
 
 

Modified: sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -19,13 +19,13 @@
 {
     template <
         class Graph,
- class RandomAccessIterator,
+ class ForwardIterator,
         class CycleDirection,
         class SpokeDirection
>
- inline void
+ inline ForwardIterator
     induce_wheel_graph(Graph& g, size_t n,
- RandomAccessIterator iter,
+ ForwardIterator iter,
                        CycleDirection cycle,
                        SpokeDirection spokes)
     {
@@ -33,7 +33,10 @@
         // of the star and then induce C(n - 1) with next(iter) as
         // the start of the cycle
         induce_star_graph(g, n, iter, spokes);
- induce_cycle_graph(g, n - 1, iter + 1, cycle);
+ induce_cycle_graph(g, n - 1, next(iter), cycle);
+
+ // return the center of the wheel
+ return iter;
     }
 
     template <

Modified: sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp 2007-07-09 16:38:41 EDT (Mon, 09 Jul 2007)
@@ -20,81 +20,127 @@
 #include <boost/graph/generators/wheel_graph.hpp>
 #include <boost/graph/generators/prism_graph.hpp>
 #include <boost/graph/generators/web_graph.hpp>
+#include <boost/graph/generators/path_graph.hpp>
 #include <boost/graph/graphviz.hpp>
 
 using namespace std;
 using namespace boost;
 
-static const int N = 10;
-static const int K = 2;
+static const int N = 3;
+static const int K = 3;
 
-template <class Graph, class Cycle, class Spoke>
-void test_complete(Cycle cycle, Spoke spoke)
+template <class Graph>
+void test_path()
 {
     Graph g;
- make_complete_graph(g, N);
+ make_path_graph(g, N);
     write_graphviz(cout, g);
 }
 
-template <class Graph, class Cycle, class Spoke>
-void test_cycle(Cycle cycle, Spoke spoke)
+template <class Graph, class Direction>
+void test_path(Direction dir)
+{
+ Graph g;
+ make_path_graph(g, N, dir);
+ write_graphviz(cout, g);
+}
+
+
+
+template <class Graph>
+void test_cycle()
+{
+ Graph g;
+ make_cycle_graph(g, N);
+ write_graphviz(cout, g);
+}
+
+template <class Graph, class Cycle>
+void test_cycle(Cycle cycle)
 {
     Graph g;
     make_cycle_graph(g, N, cycle);
     write_graphviz(cout, g);
 }
 
-template <class Graph, class Cycle, class Spoke>
-void test_star(Cycle cycle, Spoke spoke)
+
+template <class Graph>
+void test_star()
 {
     Graph g;
- make_star_graph(g, N, spoke);
+ make_star_graph(g, N);
     write_graphviz(cout, g);
 }
 
-template <class Graph, class Cycle, class Spoke>
-void test_wheel(Cycle cycle, Spoke spoke)
+template <class Graph, class Spoke>
+void test_star(Spoke spokes)
 {
     Graph g;
- make_wheel_graph(g, N, cycle, spoke);
+ make_star_graph(g, N, spokes);
     write_graphviz(cout, g);
 }
 
-template <class Graph, class Cycle, class Spoke>
-void test_prism(Cycle cycle, Spoke spoke)
+
+
+template <class Graph>
+void test_wheel()
 {
     Graph g;
- make_prism_graph(g, N, K, cycle, spoke);
+ make_wheel_graph(g, N);
     write_graphviz(cout, g);
 }
 
 template <class Graph, class Cycle, class Spoke>
-void test_web(Cycle cycle, Spoke spoke)
+void test_wheel(Cycle cycle, Spoke spokes)
 {
     Graph g;
- make_prism_graph(g, N, K, cycle, spoke);
+ make_wheel_graph(g, N, cycle, spokes);
+ write_graphviz(cout, g);
+}
+
+
+
+template <class Graph>
+void test_prism()
+{
+ Graph g;
+ make_prism_graph(g, N, K);
     write_graphviz(cout, g);
 }
 
 template <class Graph, class Cycle, class Spoke>
-void test(Cycle cycle, Spoke spoke)
+void test_prism(Cycle cycle, Spoke spokes)
 {
- test_complete<Graph>(cycle, spoke);
- test_cycle<Graph>(cycle, spoke);
- test_star<Graph>(cycle, spoke);
- test_wheel<Graph>(cycle, spoke);
- test_prism<Graph>(cycle, spoke);
- test_web<Graph>(cycle, spoke);
+ Graph g;
+ make_prism_graph(g, N, K, cycle, spokes);
+ write_graphviz(cout, g);
 }
 
+
 template <class Graph>
-void test()
+void test_web()
 {
- with_clockwise_cycle cycle;
- with_outward_spokes spoke;
- test<Graph>(cycle, spoke);
+ Graph g;
+ make_web_graph(g, N, K);
+ write_graphviz(cout, g);
 }
 
+template <class Graph, class Cycle, class Spoke>
+void test_web(Cycle cycle, Spoke spokes)
+{
+ Graph g;
+ make_web_graph(g, N, K, cycle, spokes);
+ write_graphviz(cout, g);
+}
+
+
+template <class Graph>
+void test_complete()
+{
+ Graph g;
+ make_complete_graph(g, N);
+ write_graphviz(cout, g);
+}
 
 int
 main(int argc, char *argv[])
@@ -102,15 +148,23 @@
     typedef undirected_graph<> Graph;
     typedef directed_graph<> DiGraph;
 
- with_clockwise_cycle clockwise;
- with_counterclockwise_cycle counterclockwise;
- with_bidirected_cycle bothwise;
-
- with_outward_spokes outward;
- with_inward_spokes inward;
- with_bidirected_spokes iospokes;
+ /*
+ test_complete<Graph>();
+ test_path<Graph>();
+ test_cycle<Graph>();
+ test_star<Graph>();
+ test_wheel<Graph>();
+ test_prism<Graph>();
+ */
+ test_web<Graph>();
+
+ /*
+ test_path<DiGraph>(with_forward_edges());
+ test_path<DiGraph>(with_reverse_edges());
+ test_path<DiGraph>(with_bidirected_edges());
+ */
 
- test<Graph>();
+ /*
     test<DiGraph>(clockwise, outward);
     test<DiGraph>(counterclockwise, outward);
     test<DiGraph>(bothwise, outward);
@@ -120,4 +174,5 @@
     test<DiGraph>(clockwise, iospokes);
     test<DiGraph>(counterclockwise, iospokes);
     test<DiGraph>(bothwise, iospokes);
+ */
 }


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk