From: asutton_at_[hidden]
Date: 2007-07-13 12:35:57
Author: asutton
Date: 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
New Revision: 7421
URL: http://svn.boost.org/trac/boost/changeset/7421
Log:
Wrote some more documentation
Implemnented an algorithm for finding all cycles in a graph (more or less,
it has some problems, but I've documented them).
Added:
sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp | 6 +
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp | 21 ++++++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk | 122 +++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk | 5
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 | 12 +++
sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp | 4
6 files changed, 161 insertions(+), 9 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -37,7 +37,8 @@
directed_tag)
{
- return (edge(u, v, g).second ? 1 : 0) + (edge(v, u, g).second ? 1 : 0);
+ return (edge(u, v, g).second ? 1 : 0) +
+ (edge(v, u, g).second ? 1 : 0);
}
// This template matches undirectedS
@@ -67,6 +68,9 @@
return ret;
}
+ // This is seriously flawed for directed graphs...
+ // Adjacenct vertices correspond to out degrees.
+
template <typename Graph>
inline size_t
num_centered_triangles(const Graph& g,
Added: sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/cycle.hpp 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -0,0 +1,295 @@
+// (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_CYCLE_HXX
+#define BOOST_GRAPH_CYCLE_HXX
+
+#include <vector>
+#include <limits>
+
+#include <boost/utility.hpp>
+#include <boost/graph/graph_traits.hpp>
+
+namespace boost
+{
+
+ // The implementation of this algorithm is a reproduction of the Teirnan
+ // approach for directed graphs: bibtex follows
+ //
+ // @article{362819,
+ // author = {James C. Tiernan},
+ // title = {An efficient search algorithm to find the elementary circuits of a graph},
+ // journal = {Commun. ACM},
+ // volume = {13},
+ // number = {12},
+ // year = {1970},
+ // issn = {0001-0782},
+ // pages = {722--726},
+ // doi = {http://doi.acm.org/10.1145/362814.362819},
+ // publisher = {ACM Press},
+ // address = {New York, NY, USA},
+ // }
+ //
+ // It should be pointed out that the author does not provide a complete analysis for
+ // either time or space. This is in part, due to the fact that it's a fairly input
+ // sensitive problem related to the density and construction of the graph, not just
+ // its size.
+ //
+ // I've also taken some liberties with the interpretation of the algorithm - I've
+ // basically modernized it to use real data structures (no more arrays and matrices).
+ // Oh... and there's explicit control structures - not just gotos.
+ //
+ // The problem is definitely NP-complete, an an unbounded implementation of this
+ // will probably run for quite a while (i.e.) on a large graph. The conclusions
+ // of this paper alkso reference a Paton algorithm for undirected graphs as being
+ // much more efficient (apparently based on spanning trees). Although not implemented,
+ // it can be found here:
+ //
+ // @article{363232,
+ // author = {Keith Paton},
+ // title = {An algorithm for finding a fundamental set of cycles of a graph},
+ // journal = {Commun. ACM},
+ // volume = {12},
+ // number = {9},
+ // year = {1969},
+ // issn = {0001-0782},
+ // pages = {514--518},
+ // doi = {http://doi.acm.org/10.1145/363219.363232},
+ // publisher = {ACM Press},
+ // address = {New York, NY, USA},
+ // }
+
+ // TODO: The algorithm, as presented, suffers from a number of disappoinments (not
+ // just being slow. It only really works on the most simple directed and undirected
+ // graphs. Because of the requirement on increasingly large vertex indices, the
+ // algorithm will never follow bidirected or reflexive edges. This failure causes
+ // the algorithm to miss a number cycles that end up bridging those reflexive
+ // humps.
+ //
+ // An interesting tradeoff would be to remove the test for increasing indices
+ // in detail::ignore_vertex(), causing the algorithm to visit every permutation
+ // of each cycle - that actually hits them all. Some extra work could be done
+ // mapping permuations into combinations - if you really want to.
+ //
+ // However, I should point out that this never miscomputes triangles - which
+ // is what I'd intended it for.
+
+ struct cycle_visitor
+ {
+ template <class Vertex, class Graph>
+ inline void start_vertex(Vertex v, Graph& g)
+ { }
+
+ template <class Vertex, class Graph>
+ inline void finish_vertex(Vertex v, Graph& g)
+ { }
+
+ template <class Path, class Graph>
+ inline void cycle(const Path& p, Graph& g)
+ { }
+ };
+
+ struct cycle_counter
+ : public cycle_visitor
+ {
+ cycle_counter(std::size_t& num)
+ : m_num(num)
+ { }
+
+ template <class Path, class Graph>
+ inline void cycle(const Path& p, Graph& g)
+ { ++m_num; }
+
+ size_t& m_num;
+ };
+
+ namespace detail
+ {
+ template <typename Graph, typename Path>
+ inline bool
+ is_in_path(const Graph&,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ const Path& p)
+ {
+ return (std::find(p.begin(), p.end(), v) != p.end());
+ }
+
+ template <typename Graph, typename ClosedMatrix>
+ inline bool
+ is_path_closed(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ const ClosedMatrix& closed)
+ {
+ // the path from u to v is closed if v can be found in the list
+ // of closed vertices associated with u.
+ typedef typename ClosedMatrix::const_reference Row;
+ Row r = closed[get(vertex_index, g, u)];
+ if(find(r.begin(), r.end(), v) != r.end()) {
+ return true;
+ }
+ return false;
+ }
+
+ template <typename Graph, typename Path, typename ClosedMatrix>
+ inline bool
+ ignore_vertex(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ const Path& p,
+ const ClosedMatrix& m)
+ {
+ // for undirected graphs, we're actually going to follow the
+ // original algorithm and disallow back-tracking over the
+ // undirected edge.
+ return get(vertex_index, g, v) < get(vertex_index, g, u) ||
+ is_in_path(g, v, p) ||
+ is_path_closed(g, u, v, m);
+ }
+
+ template <typename Graph, typename Path, typename ClosedMatrix>
+ inline typename graph_traits<Graph>::vertex_descriptor
+ extend_path(const Graph& g, Path& p, ClosedMatrix& closed)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::adjacency_iterator AdjacencyIterator;
+
+ // basically, p is a sequence of vertex descriptors.
+ // we want to find an adjacent vertex that the path
+ // can extend over.
+
+ // get the current vertex
+ Vertex u = p.back();
+ Vertex ret = graph_traits<Graph>::null_vertex();
+
+ AdjacencyIterator i, end;
+ for(tie(i, end) = adjacent_vertices(u, g); i != end; ++i) {
+ Vertex v = *i;
+ if(ignore_vertex(g, u, v, p, closed)) {
+ continue;
+ }
+
+ // if we get here, we've actually satisfied the loop
+ // so we can just break and return
+ p.push_back(v);
+ ret = v;
+ break;
+ }
+ return ret;
+ }
+
+ template <typename Graph, typename Path, typename ClosedMatrix>
+ inline bool
+ exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // if there's more than one vertex in the path, this closes
+ // of some possible routes and returns true. otherwise, if there's
+ // only one vertex left, the vertex has been used up
+ if(p.size() > 1) {
+ // get the last and second to last vertices, popping the last
+ // vertex off the path
+ Vertex last, prev;
+ last = p.back();
+ p.pop_back();
+ prev = p.back();
+
+ // reset the closure for the last vertex of the path and
+ // indicate that the last vertex in p is now closed to
+ // the next-to-last vertex in p
+ closed[get(vertex_index, g, last)].clear();
+ closed[get(vertex_index, g, prev)].push_back(last);
+ return true;
+ }
+ else {
+ return false;
+ }
+ }
+ }
+
+ // TODO: I may need to templatize the path type - it would add a little extra
+ // flexibility, but I'm not certain its a great idea.
+
+ template <typename Graph, typename Visitor>
+ inline void
+ visit_cycles(const Graph& g,
+ Visitor vis,
+ std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
+ std::size_t minlen = 3)
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
+ typedef std::vector<Vertex> Path;
+ typedef std::vector<Vertex> VertexList;
+ typedef std::vector<VertexList> ClosedMatrix;
+
+ // closed contains the list of vertices that are "closed" to a vertex. this
+ // is a kind of strange half-mapped matrix. rows are indexed by vertex, but
+ // the columns are not - they simply store the list of vertices that are
+ // closed to the vertex represented by the row.
+
+ const Vertex null = graph_traits<Graph>::null_vertex();
+
+ VertexIterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ Path p;
+ ClosedMatrix closed(num_vertices(g), VertexList());
+ p.push_back(*i);
+
+ vis.start_vertex(*i, g);
+
+ while(1) {
+ // extend the path until we've reached the end or the maximum
+ // sized cycle
+ Vertex j = null;
+ while(((j = detail::extend_path(g, p, closed)) != null)
+ && (p.size() < maxlen))
+ ; // empty loop
+
+ // at this point, we need to see if there's a cycle
+ if(edge(p.back(), p.front(), g).second) {
+ if(p.size() >= minlen) {
+ vis.cycle(p, g);
+ }
+ }
+
+ if(!detail::exhaust_paths(g, p, closed)) {
+ break;
+ }
+ }
+
+ vis.finish_vertex(*i, g);
+ }
+ }
+
+ template <typename Graph>
+ inline size_t
+ count_cycles(const Graph& g,
+ std::size_t maxlen = std::numeric_limits<std::size_t>::max(),
+ std::size_t minlen = 3)
+ {
+ size_t ret = 0;
+ visit_triangles(g, cycle_counter(ret), maxlen, minlen);
+ return ret;
+ }
+
+ template <typename Graph, typename Visitor>
+ inline void
+ visit_triangles(const Graph& g, Visitor vis)
+ { visit_cycles(g, vis, 3, 3); }
+
+ template <typename Graph>
+ inline size_t
+ count_triangles(const Graph& g)
+ {
+ size_t ret = 0;
+ visit_triangles(g, cycle_counter(ret));
+ return ret;
+ }
+}
+
+#endif
Modified: sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -25,8 +25,9 @@
// property vectors. Otherwise, the descriptor is generally a void-cast
// pointer to the stored element.
- // Edge descriptors are a little different. They may be required to
- // be in associative maps.
+ // TODO: Edge descriptors are a little different. They may be required to
+ // be in associative maps regardless of actual type (maybe). There's not
+ // a single example of using exterior edge properties in Boost.Graph.
template <typename Vertex, typename Value>
struct choose_ext_vprop_container
@@ -66,6 +67,22 @@
detail::choose_ext_vprop_map<Graph, container_type>::type
map_type;
};
+
+ // These functions are needed to abstract the initialization sequence.
+ // If you know the actual container type of your exerior property, then
+ // you skip these functions. If you don't and you're declaring these
+ // generically, then you _must_ use these to ensure correct initialiation
+ // of the property map.
+
+ template <typename Key, typename Value>
+ static inline std::tr1::unordered_map<Key, Value>&
+ make_property_map(std::tr1::unordered_map<Key, Value>& c)
+ { return c; }
+
+ template <typename Value>
+ static inline typename std::vector<Value>::iterator
+ make_property_map(std::vector<Value>& c)
+ { return c.begin(); }
}
#endif
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -105,14 +105,130 @@
[include property_graph.qbk]
[include mutable_property_graph.qbk]
+[h3 Pseudo-Concepts]
+The concepts above describe the type and functional requirements of graphs. However,
+these do not directly common concepts such as "directed graph" or "multigraph". As
+such, there are a number of pseudo-concepts with which we can also describe graph objects.
+
+[h4 Directed and Undirected Graphs]
+The interface that Boost.Graph provides for accessing and manipulating an undirected
+graph is the same as the interface for directed graphs described in the following
+sections, however there are some differences in the behaviour and semantics. For example,
+in a directed graph we can talk about out-edges and in-edges of a vertex. In an
+undirected graph there is no "in" and "out", there are just edges incident to a vertex.
+Nevertheless, in Boost.Graph we still use the `out_edges()` function (or `in_edges()`)
+to access the incident edges in an undirected graph. Similarly, an undirected edge has
+no "source" and "target" but merely an unordered pair of vertices, but we still use
+`source()` and `target()` to access these vertices. The reason Boost.Graph does not
+provide a separate interface for undirected graphs is that many algorithms on directed
+graphs also work on undirected graphs, and it would be inconvenient to have to duplicate
+the algorithms just because of an interface difference. When using undirected graphs
+just mentally disregard the directionality in the function names. The example below
+demonstrates using the `out_edges()`, `source()`, and `target()` with an undirected
+graph. The source code for this example and the following one can be found in
+`examples/undirected.cpp`.
+
+
+ const int V = 2;
+ typedef ... UndirectedGraph;
+ UndirectedGraph graph(V);
+
+ std::cout << "the edges incident to v: ";
+ boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
+ boost::graph_traits<UndirectedGraph>::vertex_descriptor s = vertex(0, graph);
+ for(tie(e, e_end) = out_edges(s, graph); e != e_end; ++e) {
+ std::cout << "(" << source(*e, graph)
+ << "," << target(*e, graph)
+ << ")" << endl;
+ }
+
+Even though the interface is the same for undirected graphs, there are some behavioral
+differences because edge equality is defined differently. In a directed graph,
+edge /(u,v)/ is never equal to edge /(v,u)/, but in an undirected graph they may
+be equal. If the undirected graph is a multigraph then /(u,v)/ and /(v,u)/ might be
+parallel edges. If the graph is not a multigraph then /(u,v)/ and /(v,u)/ must be the
+same edge.
+
+In the example below the edge equality test will return false for the directed graph
+and true for the undirected graph. The difference also affects the meaning of `add_edge()`.
+In the example below, if we had also written `add_add(v, u, graph)`, this would have
+added a parallel edge between `u` and `v` (provided the graph type allows parallel edges -
+which most do). The difference in edge equality also affects the association of edge
+properties. In the directed graph, the edges /(u,v)/ and /(v,u)/ can have distinct
+weight values, whereas in the undirected graph the weight of /(u,v)/ is the same as
+the weight of /(v,u)/ since they are the same edge.
+
+ typedef ... DirectedGraph;
+ typedef ... UndirectedGraph;
+
+ DirectedGraph digraph(V);
+ UndirectedGraph graph(V)
+
+ {
+ boost::graph_traits<DirectedGraph>::vertex_descriptor u, v;
+ u = vertex(0, digraph);
+ v = vertex(1, digraph);
+ add_edge(digraph, u, v, Weight(1.2));
+ add_edge(digraph, v, u, Weight(2.4));
+ boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;
+ bool found;
+ tie(e1, found) = edge(u, v, digraph);
+ tie(e2, found) = edge(v, u, digraph);
+ std::cout << "in a directed graph is ";
+ std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+ property_map<DirectedGraph, edge_weight_t>::type
+ weight = get(edge_weight, digraph);
+ cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+ cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+ }
+
+ {
+ boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;
+ u = vertex(0, graph);
+ v = vertex(1, graph);
+ add_edge(graph, u, v, Weight(3.1));
+ boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;
+ bool found;
+ tie(e1, found) = edge(u, v, graph);
+ tie(e2, found) = edge(v, u, graph);
+ std::cout << "in an undirected graph is ";
+ std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+ property_map<UndirectedGraph, edge_weight_t>::type
+ weight = get(edge_weight, graph);
+ cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+ cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+ }
+
+The output is:
+
+[pre
+in a directed graph is (u,v) == (v,u) ? 0
+weight\[(u,v)\] = 1.2
+weight\[(v,u)\] = 2.4
+in an undirected graph is (u,v) == (v,u) ? 1
+weight\[(u,v)\] = 3.1
+weight\[(v,u)\] = 3.1
+]
+
+[h4 Multigraphs]
+A /multigraph/ is a graph (either directed or undirected) that has parallel edges
+between vertices. The Boost.Graph types are mostly unrestrictive about the addition
+of parallel edges, meaning that it is fairly easy to actually create multigraphs
+without any additional work.
+
+There are certain sets of graph types that do not allow the addition of parallel edges.
+Specifically, if the EdgeList and OutEdgeList of an [boost_adjacency_list] models an
+associative container, then the graph cannont be a multigraph.
+
+*Document this a little better*
+
[h3 Indexed Graphs]
Although not explicitly documented (yet), there's a concept of a Vertex-Indexed graph
that has some valid expressions related specifically to operations on vertex index
property of the graph. The [boost_undirected_graph] class has some addiitonal methods
that can also be ported.
-[h3 Undirected Graphs]
-
-Lots of stuff here on undirected graphs...
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -6,6 +6,7 @@
/]
[section Connectivity Measures]
+
size_t connectivity(
_graph,
_component_map,
@@ -13,8 +14,8 @@
_vertex_index_map = not_given(),
_components = not_given())
-The `connectivity()` algorithm is essentially a wrapper around the
-[boost_connected_components] algorithm, but provides additional (and optional)
+The `connectivity()` algorithm is a wrapper around the [boost_connected_components]
+algorithm, that provides some convenience for working with resultant concept maps.
functionality for working with connected components. The parameters have, with
the exeption of `_components`, the same purpose and requirements as
documented in [boost_connected_components].
Modified: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -47,3 +47,15 @@
: <include>$BOOST_ROOT
: <include>../../../
;
+
+exe exterior
+ : exterior.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
+
+exe cycle
+ : cycle.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
Added: sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp 2007-07-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -0,0 +1,94 @@
+// (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)
+
+#include <iostream>
+#include <iterator>
+#include <algorithm>
+#include <vector>
+#include <map>
+#include <tr1/unordered_map>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/cycle.hpp>
+#include <boost/graph/generators/cycle_graph.hpp>
+#include <boost/graph/generators/prism_graph.hpp>
+#include <boost/graph/generators/complete_graph.hpp>
+
+using namespace std;
+using namespace boost;
+using namespace __cxxabiv1;
+
+struct cycle_printer : public cycle_visitor
+{
+ template <typename Path, typename Graph>
+ void cycle(const Path& p, const Graph& g)
+ {
+ cout << "path: ";
+ for(typename Path::const_iterator i = p.begin(); i != p.end(); ++i) {
+ cout << get(vertex_index, g, *i) << " ";
+ }
+ cout << "\n";
+ };
+};
+
+template <typename Graph>
+void build_graph(Graph& g)
+{
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::edge_descriptor Edge;
+
+ static const unsigned N = 5;
+ vector<Vertex> v(N);
+
+ // add some vertices
+ for(size_t i = 0; i < N; ++i) {
+ // v[i] = add_vertex(g);
+ v[i] = add_vertex(g);
+ }
+
+ // add some edges (with weights)
+ add_edge(v[0], v[1], g);
+ add_edge(v[1], v[2], g);
+ add_edge(v[2], v[0], g);
+
+ add_edge(v[0], v[3], g);
+ add_edge(v[3], v[4], g);
+ add_edge(v[4], v[0], g);
+};
+
+void test_1()
+{
+ typedef directed_graph<> Graph;
+
+ Graph g;
+ // build_graph(g);
+ make_prism_graph(g, 4, 3, with_bidirected_cycle(), with_bidirected_spokes());
+ // make_complete_graph(g, 4);
+
+ visit_cycles(g, cycle_printer());
+ std::cout << "number of triangles: " << count_triangles(g) << "\n";
+}
+
+void test_2()
+{
+ typedef undirected_graph<> Graph;
+
+ Graph g;
+ // build_graph(g);
+ make_prism_graph(g, 3, 2);
+
+ visit_cycles(g, cycle_printer());
+ std::cout << "number of triangles: " << count_triangles(g) << "\n";
+}
+
+
+int
+main(int argc, char *argv[])
+{
+ test_1();
+ // test_2();
+}
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-13 12:35:55 EDT (Fri, 13 Jul 2007)
@@ -156,7 +156,9 @@
test_wheel<Graph>();
test_prism<Graph>();
*/
- test_web<Graph>();
+ // test_web<Graph>();
+
+ test_prism<DiGraph>(with_clockwise_cycle(), with_bidirected_spokes());
/*
test_path<DiGraph>(with_forward_edges());