From: asutton_at_[hidden]
Date: 2007-08-21 10:21:43
Author: asutton
Date: 2007-08-21 10:21:42 EDT (Tue, 21 Aug 2007)
New Revision: 38824
URL: http://svn.boost.org/trac/boost/changeset/38824
Log:
Renamed tiernan test..
Added:
sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp
- copied, changed from r38795, /sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
Removed:
sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 | 5
sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp | 122 +++++++++++----------------------------
2 files changed, 39 insertions(+), 88 deletions(-)
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-08-21 10:21:42 EDT (Tue, 21 Aug 2007)
@@ -13,6 +13,7 @@
[ run closeness_centrality.cpp ]
[ run mean_geodesic.cpp ]
[ run eccentricity.cpp ]
+ [ run tiernan_all_cycles.cpp ]
;
# exe properties : properties.cpp ;
@@ -34,8 +35,8 @@
#
# exe exterior : exterior.cpp ;
#
-exe cycle : cycle.cpp ;
+
#
-# exe clique : clique.cpp ;
+exe clique : clique.cpp ;
#
# exe mapping : mapping.cpp ;
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp 2007-08-21 10:21:42 EDT (Tue, 21 Aug 2007)
+++ (empty file)
@@ -1,130 +0,0 @@
-// (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/tiernan_all_cycles.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;
-
-template <typename OStream>
-struct cycle_printer
- : public cycle_visitor
-{
- cycle_printer(OStream& os)
- : m_os(os)
- { }
-
- template <typename Path, typename Graph>
- void cycle(const Path& p, const Graph& g)
- {
- m_os << "cycle: ";
- typename Path::const_iterator i, end = p.end();
- for(i = p.begin(); i != end; ++i) {
- m_os << get(vertex_index, g, *i) << " ";
- }
- m_os << "\n";
- }
-
- OStream& m_os;
-};
-
-template <typename SizeType>
-struct cycle_counter
- : public cycle_visitor
-{
- cycle_counter(SizeType& count)
- : m_count(count)
- { }
-
- template <typename Path, typename Graph>
- void cycle(const Path& p, const Graph& g)
- {
- ++m_count;
- }
-
- SizeType& m_count;
-};
-
-template <typename Stream>
-inline cycle_printer<Stream>
-print_cycles(Stream& os)
-{
- return cycle_printer<Stream>(os);
-}
-
-template <typename SizeType>
-inline cycle_counter<SizeType>
-count_cycles(SizeType& count)
-{
- return cycle_counter<SizeType>(count);
-}
-
-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);
- }
-
- // 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);
- */
-};
-
-template <typename Graph>
-void test()
-{
- Graph g;
- // build_graph(g);
- make_prism_graph(g, 3, 2, with_clockwise_cycle(), with_bidirected_spokes());
- // make_complete_graph(g, 4, with_clockwise_cycle());
-
- size_t count = 0;
- tiernan_all_cycles(g, count_cycles(count));
- std::cout << "number of cycles: " << count << "\n";
-
- tiernan_all_cycles(g, print_cycles(cout));
-}
-
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> DiGraph;
-
- std::cout << "*** undirected ***\n";
- test<Graph>();
-
- std::cout << "*** directed ***\n";
- test<DiGraph>();
-}
Copied: sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp (from r38795, /sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp 2007-08-21 10:21:42 EDT (Tue, 21 Aug 2007)
@@ -5,116 +5,66 @@
// 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/graph_utility.hpp>
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/tiernan_all_cycles.hpp>
-#include <boost/graph/generators/cycle_graph.hpp>
-#include <boost/graph/generators/prism_graph.hpp>
-#include <boost/graph/generators/complete_graph.hpp>
+#include <boost/graph/erdos_renyi_generator.hpp>
+
+#include <boost/random/linear_congruential.hpp>
using namespace std;
using namespace boost;
-template <typename OStream>
-struct cycle_printer
- : public cycle_visitor
+struct cycle_validator
{
- cycle_printer(OStream& os)
- : m_os(os)
+ cycle_validator(size_t& c)
+ : cycles(c)
{ }
template <typename Path, typename Graph>
void cycle(const Path& p, const Graph& g)
{
- m_os << "cycle: ";
- typename Path::const_iterator i, end = p.end();
- for(i = p.begin(); i != end; ++i) {
- m_os << get(vertex_index, g, *i) << " ";
+ ++cycles;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+ // Check to make sure that each of the vertices in the path
+ // is truly connected and that the back is connected to the
+ // front - it's not validating that we find all paths, just
+ // that the paths are valid.
+ typename Path::const_iterator i, j, last = prior(p.end());
+ for(i = p.begin(); i != last; ++i) {
+ j = next(i);
+ BOOST_ASSERT(edge(*i, *j, g).second);
}
- m_os << "\n";
- }
-
- OStream& m_os;
-};
-
-template <typename SizeType>
-struct cycle_counter
- : public cycle_visitor
-{
- cycle_counter(SizeType& count)
- : m_count(count)
- { }
-
- template <typename Path, typename Graph>
- void cycle(const Path& p, const Graph& g)
- {
- ++m_count;
+ BOOST_ASSERT(edge(p.back(), p.front(), g).second);
}
- SizeType& m_count;
-};
-
-template <typename Stream>
-inline cycle_printer<Stream>
-print_cycles(Stream& os)
-{
- return cycle_printer<Stream>(os);
-}
-
-template <typename SizeType>
-inline cycle_counter<SizeType>
-count_cycles(SizeType& count)
-{
- return cycle_counter<SizeType>(count);
-}
-
-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);
- }
-
- // 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);
- */
+ size_t& cycles;
};
template <typename Graph>
void test()
{
- Graph g;
- // build_graph(g);
- make_prism_graph(g, 3, 2, with_clockwise_cycle(), with_bidirected_spokes());
- // make_complete_graph(g, 4, with_clockwise_cycle());
-
- size_t count = 0;
- tiernan_all_cycles(g, count_cycles(count));
- std::cout << "number of cycles: " << count << "\n";
+ typedef erdos_renyi_iterator<boost::minstd_rand, Graph> er;
- tiernan_all_cycles(g, print_cycles(cout));
-}
+ // Generate random graphs with 15 vertices and 15% probability
+ // of edge connection.
+ static const size_t N = 20;
+ static const float P = 0.1;
+ boost::minstd_rand rng;
+
+ Graph g(er(rng, N, P), er(), N);
+ renumber_indices(g);
+ print_edges(g, get(vertex_index, g));
+
+ size_t cycles = 0;
+ cycle_validator vis(cycles);
+ tiernan_all_cycles(g, vis);
+ cout << "# cycles: " << vis.cycles << "\n";
+}
int
main(int argc, char *argv[])