|
|
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