[Boost-commit] svn:boost r38831 - sandbox/SOC/2007/graphs/libs/graph/examples

From: asutton_at_[hidden]
Date: 2007-08-21 14:06:29

Author: asutton
Date: 2007-08-21 14:06:28 EDT (Tue, 21 Aug 2007)
New Revision: 38831
URL: http://svn.boost.org/trac/boost/changeset/38831

Log:
Added a couple of graphs
Added the missing tiernan examples
Fixed some issues with the b&k examples

Added:
   sandbox/SOC/2007/graphs/libs/graph/examples/prism_3_2.graph   (contents, props changed)
   sandbox/SOC/2007/graphs/libs/graph/examples/prob_network.graph   (contents, props changed)
   sandbox/SOC/2007/graphs/libs/graph/examples/tiernan_girth_circumference.cpp   (contents, props changed)
   sandbox/SOC/2007/graphs/libs/graph/examples/tiernan_print_cycles.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_clique_number.cpp |     2 +-                                      
   sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_print_cliques.cpp |     2 +-                                      
   2 files changed, 2 insertions(+), 2 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_clique_number.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_clique_number.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_clique_number.cpp	2007-08-21 14:06:28 EDT (Tue, 21 Aug 2007)
@@ -4,7 +4,7 @@
 // Boost Software License, Version 1.0 (See accompanying file
 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
 
-//[bron_kerbosch_clique_number
+//[code_bron_kerbosch_clique_number
 #include <iostream>
 
 #include <boost/graph/undirected_graph.hpp>

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_print_cliques.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_print_cliques.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/bron_kerbosch_print_cliques.cpp	2007-08-21 14:06:28 EDT (Tue, 21 Aug 2007)
@@ -4,7 +4,7 @@
 // Boost Software License, Version 1.0 (See accompanying file
 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
 
-//[bron_kerbosch_print_cliques
+//[code_bron_kerbosch_print_cliques
 #include <iostream>
 
 #include <boost/graph/undirected_graph.hpp>

Added: sandbox/SOC/2007/graphs/libs/graph/examples/prism_3_2.graph
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/prism_3_2.graph	2007-08-21 14:06:28 EDT (Tue, 21 Aug 2007)
@@ -0,0 +1,16 @@
+0,1
+1,2
+2,0
+
+3,4
+4,5
+5,3
+
+0,3
+3,0
+
+1,4
+4,1
+
+2,5
+5,2
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/examples/prob_network.graph
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/prob_network.graph	2007-08-21 14:06:28 EDT (Tue, 21 Aug 2007)
@@ -0,0 +1,18 @@
+myspace,myspace,.5
+myspace,digg,.5
+blogger,digg,.33
+blogger,slashdot,.33
+blogger,wikipedia,.33
+digg,slashdot,.33
+digg,wikipedia,.33
+digg,digg,.33
+blogspot,slashdot,.5
+blogspot,wikipedia,.5
+slashdot,bbc,.5
+slashdot,wikipedia,.5
+bbc,wikipedia,.5
+bbc,bbc,.5
+wikipedia,wikipedia,.25
+wikipedia,blogger,.25
+wikipedia,myspace,.25
+wikipedia,blogspot,.25
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/examples/tiernan_girth_circumference.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/tiernan_girth_circumference.cpp	2007-08-21 14:06:28 EDT (Tue, 21 Aug 2007)
@@ -0,0 +1,40 @@
+// (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)
+
+//[tiernan_girth_circumference
+#include <iostream>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and read it from standard input.
+    Graph g;
+    read_graph(g, cin);
+
+    // Compute the girth and circumference simulataneously
+    size_t girth, circ;
+    tie(girth, circ) = tiernan_girth_and_circumference(g);
+
+    // Print the result
+    cout << "girth: " << girth << endl;
+    cout << "circumference: " << circ << endl;
+
+    return 0;
+}
+//]

Added: sandbox/SOC/2007/graphs/libs/graph/examples/tiernan_print_cycles.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/tiernan_print_cycles.cpp	2007-08-21 14:06:28 EDT (Tue, 21 Aug 2007)
@@ -0,0 +1,68 @@
+// (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)
+
+//[tiernan_print_cycles
+#include <iostream>
+
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
+
+#include "helper.hpp"
+
+using namespace std;
+using namespace boost;
+
+// The cycle_printer is a visitor that will print the path that comprises
+// the cycle. Note that the back() vertex of the path is not the same as
+// the front(). It is implicit in the listing of vertices that the back()
+// vertex is connected to the front().
+template <typename OutputStream>
+struct cycle_printer
+{
+    cycle_printer(OutputStream& stream)
+        : os(stream)
+    { }
+
+    template <typename Path, typename Graph>
+    void cycle(const Path& p, const Graph& g)
+    {
+        // Get the property map containing the vertex indices
+        // so we can print them.
+        typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
+        IndexMap indices = get(vertex_index, g);
+
+        // Iterate over path printing each vertex that forms the cycle.
+        typename Path::const_iterator i, end = p.end();
+        for(i = p.begin(); i != end; ++i) {
+            os << get(indices, *i) << " ";
+        }
+        os << endl;
+    }
+    OutputStream& os;
+};
+
+// Declare the graph type and its vertex and edge types.
+typedef directed_graph<> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+int
+main(int argc, char *argv[])
+{
+    // Create the graph and read it from standard input.
+    Graph g;
+    read_graph(g, cin);
+
+    // Instantiate the visitor for printing cycles
+    cycle_printer<ostream> vis(cout);
+
+    // Use the Tiernan algorithm to visit all cycles, printing them
+    // as they are found.
+    tiernan_all_cycles(g, vis);
+
+    return 0;
+}
+//]