From: asutton_at_[hidden]
Date: 2007-07-09 14:49:05
Author: asutton
Date: 2007-07-09 14:49:04 EDT (Mon, 09 Jul 2007)
New Revision: 7400
URL: http://svn.boost.org/trac/boost/changeset/7400
Log:
Added new generators for prism and web graphs.
Rewrote generation fromework to include "induce" functions which,
when given an iterator to vectors will induce a graph by adding
edges in a specified pattern. This allows graphs to be built
component-wise.
Added:
sandbox/SOC/2007/graphs/boost/graph/generators/prism_graph.hpp
sandbox/SOC/2007/graphs/boost/graph/generators/web_graph.hpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/generators/cycle_graph.hpp | 32 +++++++++++++++++---------
sandbox/SOC/2007/graphs/boost/graph/generators/options.hpp | 48 ++++++++++++++++++++--------------------
sandbox/SOC/2007/graphs/boost/graph/generators/star_graph.hpp | 41 +++++++++++++++++++---------------
sandbox/SOC/2007/graphs/boost/graph/generators/wheel_graph.hpp | 44 ++++++++++++++++++++++++------------
sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp | 21 +++++++++++++++++
5 files changed, 118 insertions(+), 68 deletions(-)
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 14:49:04 EDT (Mon, 09 Jul 2007)
@@ -15,23 +15,33 @@
namespace boost
{
- template <
- class Graph,
- class RandomAccessContainer,
- class CycleDirection
- >
+ template <typename Graph,class RandomAccessIterator, class CycleDirection>
inline void
- make_cycle_graph(Graph& g, size_t k,
+ induce_cycle_graph(Graph& g, size_t n,
+ RandomAccessIterator iter,
+ CycleDirection cycle)
+ {
+ typedef RandomAccessIterator iterator;
+
+ for(size_t i = 0; i < n - 1; ++i) {
+ iterator u = iter + i, v = next(u);
+ detail::add_cycle_edge(g, *u, *v, cycle);
+ }
+
+ // connect the last edge back to the beginning
+ detail::add_cycle_edge(g, *(iter + (n - 1)), *iter, cycle);
+ }
+
+ template <class Graph, class RandomAccessContainer, class CycleDirection>
+ inline void
+ make_cycle_graph(Graph& g, size_t n,
RandomAccessContainer& verts,
CycleDirection cycle)
{
- for(size_t i = 0; i < k; ++i) {
+ for(size_t i = 0; i < n; ++i) {
verts[i] = add_vertex(g);
}
- for(size_t i = 0; i < k - 1; ++i) {
- detail::connect_cycle_vertices(g, verts[i], verts[i + 1], cycle);
- }
- detail::connect_cycle_vertices(g, verts[k - 1], verts[0], cycle);
+ induce_cycle_graph(g, n, &verts[0], cycle);
}
template <class Graph, 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 14:49:04 EDT (Mon, 09 Jul 2007)
@@ -37,26 +37,26 @@
template <typename Graph>
inline void
- connect_cycle_vertices(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_clockwise_cycle)
+ add_cycle_edge(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ with_clockwise_cycle)
{ add_edge(u, v, g); }
template <typename Graph>
inline void
- connect_cycle_vertices(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_counterclockwise_cycle)
+ add_cycle_edge(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ with_counterclockwise_cycle)
{ add_edge(v, u, g); }
template <typename Graph>
inline void
- connect_cycle_vertices(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_bidirected_cycle)
+ add_cycle_edge(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ with_bidirected_cycle)
{
add_edge(u, v, g);
add_edge(v, u, g);
@@ -65,26 +65,26 @@
template <typename Graph>
inline void
- connect_spoke_vertices(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_outward_spokes)
+ 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
- connect_spoke_vertices(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_inward_spokes)
+ 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>
inline void
- connect_spoke_vertices(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- with_bidirected_spokes)
+ add_spoke_edge(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ with_bidirected_spokes)
{
add_edge(u, v, g);
add_edge(v, u, g);
Added: sandbox/SOC/2007/graphs/boost/graph/generators/prism_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/prism_graph.hpp 2007-07-09 14:49:04 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,93 @@
+// (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_PRISM_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_PRISM_GRAPH_HXX
+
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/graph/generators/options.hpp>
+#include <boost/graph/generators/cycle_graph.hpp>
+
+namespace boost
+{
+ // Prism graphs are kind of interesting... They're basically concentric
+ // cycle graphs with aligned vertices connected by an edge (spoke).
+ // The specification of a prism graphs is usually G = Y(m,n) such that
+ // G is n concentric cycles with m vertices each.
+
+ template <
+ class Graph,
+ class RandomAccessIterator,
+ class CycleDirection,
+ class SpokeDirection
+ >
+ inline void
+ 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);
+ }
+
+ // the, build the psuedo-spokes to connect the
+ // 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);
+ }
+ }
+ }
+
+ template <
+ class Graph,
+ class RandomAccessContainer,
+ class CycleDirection,
+ class SpokeDirection
+ >
+ inline void
+ make_prism_graph(Graph& g, size_t m, size_t n,
+ RandomAccessContainer& verts,
+ CycleDirection cycle,
+ SpokeDirection spokes)
+ {
+ size_t N = m * n;
+ for(size_t i = 0; i < N; ++i) {
+ verts[i] = add_vertex(g);
+ }
+ induce_prism_graph(g, m, n, &verts[0], cycle, spokes);
+
+ }
+
+ template <class Graph, class CycleDirection, class SpokeDirection>
+ inline void
+ make_prism_graph(Graph& g, size_t m, size_t n,
+ CycleDirection cycle,
+ SpokeDirection spoke)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ std::vector<Vertex> verts(m * n);
+ make_prism_graph(g, m, n, verts, cycle, spoke);
+ }
+
+ template <class Graph>
+ inline void
+ make_prism_graph(Graph& g, size_t m, size_t n)
+ {
+ make_prism_graph(g, m, n,
+ with_clockwise_cycle(),
+ with_outward_spokes());
+ }
+}
+
+#endif
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 14:49:04 EDT (Mon, 09 Jul 2007)
@@ -15,41 +15,46 @@
namespace boost
{
- template <
- class Graph,
- class RandomAccessContainer,
- class SpokeDirection
- >
+ // 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
+ induce_star_graph(Graph& g, size_t n,
+ RandomAccessIterator iter,
+ SpokeDirection spokes)
+ {
+ for(size_t i = 1; i < n; ++i) {
+ detail::add_spoke_edge(g, *iter, *(iter + i), spokes);
+ }
+ }
+
+ template <class Graph, class RandomAccessContainer, class SpokeDirection>
inline void
- make_star_graph(Graph& g, size_t k,
+ make_star_graph(Graph& g, size_t n,
RandomAccessContainer& verts,
SpokeDirection spokes)
{
- for(size_t i = 0; i < k; ++i) {
+ for(size_t i = 0; i < n; ++i) {
verts[i] = add_vertex(g);
}
- for(size_t i = 1; i < k - 1; ++i) {
- detail::connect_spoke_vertices(g, verts[0], verts[i], spokes);
- }
- detail::connect_spoke_vertices(g, verts[0], verts[k - 1], spokes);
+ induce_star_graph(g, n, &verts[0], spokes);
}
template <class Graph, class SpokeDirection>
inline void
- make_star_graph(Graph& g, size_t k, SpokeDirection spokes)
+ make_star_graph(Graph& g, size_t n, SpokeDirection spokes)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- std::vector<Vertex> verts(k);
- make_star_graph(g, k, verts, spokes);
+ std::vector<Vertex> verts(n);
+ make_star_graph(g, n, verts, spokes);
}
template <class Graph>
inline void
- make_star_graph(Graph& g, size_t k)
+ make_star_graph(Graph& g, size_t n)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- std::vector<Vertex> verts(k);
- make_star_graph(g, k, verts, with_outward_spokes());
+ make_star_graph(g, n, with_outward_spokes());
}
}
Added: sandbox/SOC/2007/graphs/boost/graph/generators/web_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/generators/web_graph.hpp 2007-07-09 14:49:04 EDT (Mon, 09 Jul 2007)
@@ -0,0 +1,88 @@
+// (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_WEB_GRAPH_HXX
+#define BOOST_GRAPH_GENERATORS_WEB_GRAPH_HXX
+
+#include <vector>
+#include <boost/utility.hpp>
+#include <boost/graph/generators/options.hpp>
+#include <boost/graph/generators/cycle_graph.hpp>
+
+namespace boost
+{
+ // Web graphs G = W(m, n) is the same as the prism graph P(m, n + 1) with
+ // the edges that comprise the outer cycle removed. This leaves m spokes
+ // extending from the graph. Note that these graphs will have m * n + 1
+ // vertices.
+
+ template <
+ class Graph,
+ class RandomAccessIterator,
+ class CycleDirection,
+ class SpokeDirection
+ >
+ inline void
+ induce_web_graph(Graph& g, size_t m, size_t n,
+ RandomAccessIterator iter,
+ CycleDirection cycle,
+ SpokeDirection spokes)
+ {
+ typedef RandomAccessIterator iterator;
+
+ // induce the prism on all but the last m vertices
+ induce_prism_graph(g, m, n, iter, cycle, spokes);
+
+ // connect the peripheral vertices to the outermost cycle
+ 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);
+ }
+ }
+
+
+ template <
+ class Graph,
+ class RandomAccessContainer,
+ class CycleDirection,
+ class SpokeDirection
+ >
+ inline void
+ make_web_graph(Graph& g, size_t m, size_t n,
+ RandomAccessContainer& verts,
+ CycleDirection cycle,
+ SpokeDirection spokes)
+ {
+ size_t N = m * (n + 1);
+ for(size_t i = 0; i < N; ++i) {
+ verts[i] = add_vertex(g);
+ }
+ induce_web_graph(g, m, n, &verts[0], cycle, spokes);
+ }
+
+ template <class Graph, class CycleDirection, class SpokeDirection>
+ inline void
+ make_web_graph(Graph& g, size_t m, size_t n,
+ CycleDirection cycle,
+ SpokeDirection spoke)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ std::vector<Vertex> verts(m * (n + 1));
+ make_web_graph(g, m, n, verts, cycle, spoke);
+ }
+
+ template <class Graph>
+ inline void
+ make_web_graph(Graph& g, size_t m, size_t n)
+ {
+ make_web_graph(g, m, n,
+ with_clockwise_cycle(),
+ with_outward_spokes());
+ }
+}
+
+#endif
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 14:49:04 EDT (Mon, 09 Jul 2007)
@@ -12,30 +12,46 @@
#include <boost/type_traits/is_convertible.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/generators/options.hpp>
+#include <boost/graph/generators/cycle_graph.hpp>
+#include <boost/graph/generators/star_graph.hpp>
namespace boost
{
template <
class Graph,
+ class RandomAccessIterator,
+ class CycleDirection,
+ class SpokeDirection
+ >
+ inline void
+ induce_wheel_graph(Graph& g, size_t n,
+ RandomAccessIterator iter,
+ CycleDirection cycle,
+ SpokeDirection spokes)
+ {
+ // this should be easy... induce S(n) with iter as the root
+ // 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);
+ }
+
+ template <
+ class Graph,
class RandomAccessContainer,
class CycleDirection,
class SpokeDirection
>
inline void
- make_wheel_graph(Graph& g, size_t k,
+ make_wheel_graph(Graph& g, size_t n,
RandomAccessContainer& verts,
CycleDirection cycle,
SpokeDirection spokes)
{
- for(size_t i = 0; i < k; ++i) {
+ for(size_t i = 0; i < n; ++i) {
verts[i] = add_vertex(g);
}
- for(size_t i = 1; i < k - 1; ++i) {
- detail::connect_spoke_vertices(g, verts[0], verts[i], spokes);
- detail::connect_cycle_vertices(g, verts[i], verts[i + 1], cycle);
- }
- detail::connect_spoke_vertices(g, verts[0], verts[k - 1], spokes);
- detail::connect_cycle_vertices(g, verts[k - 1], verts[1], cycle);
+ induce_wheel_graph(g, n, &verts[0], cycle, spokes);
}
template <
@@ -44,22 +60,20 @@
class SpokeDirection
>
inline void
- make_wheel_graph(Graph& g, size_t k,
+ make_wheel_graph(Graph& g, size_t n,
CycleDirection cycle,
SpokeDirection spokes)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- std::vector<Vertex> verts(k);
- make_wheel_graph(g, k, verts, cycle, spokes);
+ std::vector<Vertex> verts(n);
+ make_wheel_graph(g, n, verts, cycle, spokes);
}
template <class Graph>
inline void
- make_wheel_graph(Graph& g, size_t k)
+ make_wheel_graph(Graph& g, size_t n)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- std::vector<Vertex> verts(k);
- make_wheel_graph(g, k, verts,
+ make_wheel_graph(g, n,
with_clockwise_cycle(),
with_outward_spokes());
}
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 14:49:04 EDT (Mon, 09 Jul 2007)
@@ -18,12 +18,15 @@
#include <boost/graph/generators/cycle_graph.hpp>
#include <boost/graph/generators/star_graph.hpp>
#include <boost/graph/generators/wheel_graph.hpp>
+#include <boost/graph/generators/prism_graph.hpp>
+#include <boost/graph/generators/web_graph.hpp>
#include <boost/graph/graphviz.hpp>
using namespace std;
using namespace boost;
static const int N = 10;
+static const int K = 2;
template <class Graph, class Cycle, class Spoke>
void test_complete(Cycle cycle, Spoke spoke)
@@ -58,12 +61,30 @@
}
template <class Graph, class Cycle, class Spoke>
+void test_prism(Cycle cycle, Spoke spoke)
+{
+ Graph g;
+ make_prism_graph(g, N, K, cycle, spoke);
+ write_graphviz(cout, g);
+}
+
+template <class Graph, class Cycle, class Spoke>
+void test_web(Cycle cycle, Spoke spoke)
+{
+ Graph g;
+ make_prism_graph(g, N, K, cycle, spoke);
+ write_graphviz(cout, g);
+}
+
+template <class Graph, class Cycle, class Spoke>
void test(Cycle cycle, Spoke spoke)
{
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);
}
template <class Graph>