[Boost-commit] svn:boost r38824 - sandbox/SOC/2007/graphs/libs/graph/test

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[])