From: asutton_at_[hidden]
Date: 2007-08-24 09:28:17
Author: asutton
Date: 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
New Revision: 38892
URL: http://svn.boost.org/trac/boost/changeset/38892
Log:
Reorg of test directory
Added:
sandbox/SOC/2007/graphs/libs/graph/test/runtime/Jamfile.v2
- copied, changed from r38888, /sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
sandbox/SOC/2007/graphs/libs/graph/test/runtime/bron_kerbosch_all_cliques.cpp
- copied unchanged from r38890, /sandbox/SOC/2007/graphs/libs/graph/test/compile/bron_kerbosch_all_cliques.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/closeness_centrality.cpp
- copied unchanged from r38850, /sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/clustering_coefficient.cpp
- copied unchanged from r38850, /sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/components.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/components.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/constant_property_map.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/constant_property_map.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/degree_centrality.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/eccentricity.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/exterior.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/generate.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/index.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/index.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/io.hpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/io.hpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/k_pairs.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/k_pairs.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/mean_geodesic.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/misc.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/misc.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/mutable.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/properties.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/properties.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/range.cpp
- copied unchanged from r38779, /sandbox/SOC/2007/graphs/libs/graph/test/range.cpp
sandbox/SOC/2007/graphs/libs/graph/test/runtime/tiernan_all_cycles.cpp
- copied unchanged from r38832, /sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp
Removed:
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp
sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp
sandbox/SOC/2007/graphs/libs/graph/test/components.cpp
sandbox/SOC/2007/graphs/libs/graph/test/constant_property_map.cpp
sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp
sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp
sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp
sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
sandbox/SOC/2007/graphs/libs/graph/test/index.cpp
sandbox/SOC/2007/graphs/libs/graph/test/io.hpp
sandbox/SOC/2007/graphs/libs/graph/test/k_pairs.cpp
sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp
sandbox/SOC/2007/graphs/libs/graph/test/misc.cpp
sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp
sandbox/SOC/2007/graphs/libs/graph/test/properties.cpp
sandbox/SOC/2007/graphs/libs/graph/test/range.cpp
sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/test/runtime/Jamfile.v2 | 4 +---
1 files changed, 1 insertions(+), 3 deletions(-)
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,22 +0,0 @@
-
-import testing ;
-
-project
- : requirements
- <include>../../../
- <include>$BOOST_ROOT
- ;
-
-build-project concept ;
-
-test-suite graph_test :
- [ run constant_property_map.cpp ]
- [ run degree_centrality.cpp ]
- [ run closeness_centrality.cpp ]
- [ run mean_geodesic.cpp ]
- [ run eccentricity.cpp ]
- [ run tiernan_all_cycles.cpp ]
- [ run bron_kerbosch_all_cliques.cpp ]
- [ run clustering_coefficient.cpp ]
- ;
-
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,134 +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 <vector>
-
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/constant_property_map.hpp>
-#include <boost/graph/floyd_warshall_shortest.hpp>
-#include <boost/graph/closeness_centrality.hpp>
-
-using namespace std;
-using namespace boost;
-
-// number of vertices in the graph
-static const unsigned N = 5;
-
-template <typename Graph>
-struct vertex_vector
-{
- typedef graph_traits<Graph> traits;
- typedef vector<typename traits::vertex_descriptor> type;
-};
-
-template <typename Graph>
-void build_graph(Graph& g,
- typename vertex_vector<Graph>::type& v)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- // add vertices
- for(size_t i = 0; i < N; ++i) {
- v[i] = add_vertex(g);
- }
-
- // add edges
- add_edge(v[0], v[1], g);
- add_edge(v[1], v[2], g);
- add_edge(v[2], v[0], g);
- add_edge(v[3], v[4], g);
- add_edge(v[4], v[0], g);
-};
-
-
-template <typename Graph>
-void test_undirected()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- typedef exterior_vertex_property<Graph, float> CentralityProperty;
- typedef typename CentralityProperty::container_type CentralityContainer;
- typedef typename CentralityProperty::map_type CentralityMap;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
- typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
-
- typedef constant_property_map<Edge, int> WeightMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- CentralityContainer centralities(num_vertices(g));
- DistanceMatrix distances(num_vertices(g));
-
- CentralityMap cm(centralities, g);
- DistanceMatrixMap dm(distances, g);
-
- WeightMap wm(1);
-
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- all_closeness_centralities(g, dm, cm);
-
- BOOST_ASSERT(cm[v[0]] == float(1)/5);
- BOOST_ASSERT(cm[v[1]] == float(1)/7);
- BOOST_ASSERT(cm[v[2]] == float(1)/7);
- BOOST_ASSERT(cm[v[3]] == float(1)/9);
- BOOST_ASSERT(cm[v[4]] == float(1)/6);
-}
-
-template <typename Graph>
-void test_directed()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- typedef exterior_vertex_property<Graph, float> CentralityProperty;
- typedef typename CentralityProperty::container_type CentralityContainer;
- typedef typename CentralityProperty::map_type CentralityMap;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
- typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
-
- typedef constant_property_map<Edge, int> WeightMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- CentralityContainer centralities(num_vertices(g));
- DistanceMatrix distances(num_vertices(g));
-
- CentralityMap cm(centralities, g);
- DistanceMatrixMap dm(distances, g);
-
- WeightMap wm(1);
-
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- all_closeness_centralities(g, dm, cm);
-
- BOOST_ASSERT(cm[v[0]] == float(0));
- BOOST_ASSERT(cm[v[1]] == float(0));
- BOOST_ASSERT(cm[v[2]] == float(0));
- BOOST_ASSERT(cm[v[3]] == float(1)/10);
- BOOST_ASSERT(cm[v[4]] == float(0));
-}
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> Digraph;
-
- test_undirected<Graph>();
- test_directed<Digraph>();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/clustering_coefficient.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,108 +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 <boost/detail/lightweight_test.hpp>
-
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/clustering_coefficient.hpp>
-
-using namespace std;
-using namespace boost;
-
-// number of vertices in the graph
-static const unsigned N = 5;
-
-template <typename Graph>
- struct vertex_vector
-{
- typedef graph_traits<Graph> traits;
- typedef vector<typename traits::vertex_descriptor> type;
-};
-
-template <typename Graph>
- void build_graph(Graph& g,
- typename vertex_vector<Graph>::type& v)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- // add vertices
- for(size_t i = 0; i < N; ++i) {
- v[i] = add_vertex(g);
- }
-
- // add edges
- add_edge(v[0], v[1], g);
- add_edge(v[1], v[2], g);
- add_edge(v[2], v[0], g);
- add_edge(v[3], v[4], g);
- add_edge(v[4], v[0], g);
-};
-
-template <typename Graph>
-void test_undirected()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- typedef exterior_vertex_property<Graph, float> ClusteringProperty;
- typedef typename ClusteringProperty::container_type ClusteringContainer;
- typedef typename ClusteringProperty::map_type ClusteringMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- ClusteringContainer cc(num_vertices(g));
- ClusteringMap cm(cc, g);
-
- BOOST_TEST(num_paths_through_vertex(g, v[0]) == 3);
- BOOST_TEST(num_paths_through_vertex(g, v[1]) == 1);
- BOOST_TEST(num_paths_through_vertex(g, v[2]) == 1);
- BOOST_TEST(num_paths_through_vertex(g, v[3]) == 0);
- BOOST_TEST(num_paths_through_vertex(g, v[4]) == 1);
-
- BOOST_TEST(num_triangles_on_vertex(g, v[0]) == 1);
- BOOST_TEST(num_triangles_on_vertex(g, v[1]) == 1);
- BOOST_TEST(num_triangles_on_vertex(g, v[2]) == 1);
- BOOST_TEST(num_triangles_on_vertex(g, v[3]) == 0);
- BOOST_TEST(num_triangles_on_vertex(g, v[4]) == 0);
-
- BOOST_TEST(clustering_coefficient(g, v[0]) == float(1)/3);
- BOOST_TEST(clustering_coefficient(g, v[1]) == 1);
- BOOST_TEST(clustering_coefficient(g, v[2]) == 1);
- BOOST_TEST(clustering_coefficient(g, v[3]) == 0);
- BOOST_TEST(clustering_coefficient(g, v[4]) == 0);
-
- all_clustering_coefficients(g, cm);
-
- BOOST_TEST(cm[v[0]] == float(1)/3);
- BOOST_TEST(cm[v[1]] == 1);
- BOOST_TEST(cm[v[2]] == 1);
- BOOST_TEST(cm[v[3]] == 0);
- BOOST_TEST(cm[v[4]] == 0);
-
- // I would have used check_close, but apparently, that requires
- // me to link this against a library - which I don't really want
- // to do. Basically, this makes sure that that coefficient is
- // within some tolerance (like 1/10 million).
- float coef = mean_clustering_coefficient(g, cm);
- BOOST_TEST((coef - (7.0f / 15.0f)) < 1e-7f);
-}
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> Digraph;
-
- // TODO: write a test for directed clustering coefficient.
-
- test_undirected<Graph>();
- // test<Digraph>();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/components.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/components.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,11 +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)
-
-
-int
-main(int argc, char *argv[])
-{
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/constant_property_map.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/constant_property_map.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,54 +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 <vector>
-
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/constant_property_map.hpp>
-
-using namespace std;
-using namespace boost;
-
-// useful types
-// number of vertices in the graph
-static const unsigned N = 5;
-
-template <typename Graph>
-void build_graph(Graph& g)
-{
- for(size_t i = 0; i < N; ++i) {
- add_vertex(g);
- }
-};
-
-
-template <typename Graph>
-void test()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-
- typedef constant_property_map<Vertex, int> Map;
-
- Graph g;
- build_graph(g);
-
- Map m(1);
-
- VertexIterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- BOOST_ASSERT(m[*i] == 1);
- }
-}
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- test<Graph>();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,123 +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 <vector>
-
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/degree_centrality.hpp>
-
-using namespace std;
-using namespace boost;
-
-// useful types
-// number of vertices in the graph
-static const unsigned N = 5;
-
-template <typename Graph>
-void build_graph(Graph& g,
- vector<typename graph_traits<Graph>::vertex_descriptor>& v)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- // add vertices
- for(size_t i = 0; i < N; ++i) {
- v[i] = add_vertex(g);
- }
-
- // add edges
- add_edge(v[0], v[1], g);
- add_edge(v[1], v[2], g);
- add_edge(v[2], v[0], g);
- add_edge(v[3], v[4], g);
- add_edge(v[4], v[0], g);
-};
-
-template <typename Graph>
-void test_undirected()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
- typedef typename CentralityProperty::container_type CentralityContainer;
- typedef typename CentralityProperty::map_type CentralityMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- CentralityContainer cents(num_vertices(g));
- CentralityMap cm(cents, g);
- all_degree_centralities(g, cm);
-
- BOOST_ASSERT(cm[v[0]] == 3);
- BOOST_ASSERT(cm[v[1]] == 2);
- BOOST_ASSERT(cm[v[2]] == 2);
- BOOST_ASSERT(cm[v[3]] == 1);
- BOOST_ASSERT(cm[v[4]] == 2);
-}
-
-template <typename Graph>
-void test_influence()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
- typedef typename CentralityProperty::container_type CentralityContainer;
- typedef typename CentralityProperty::map_type CentralityMap;
-
- Graph g;
-
- vector<Vertex> v(N);
- build_graph(g, v);
-
- CentralityContainer cents(num_vertices(g));
- CentralityMap cm(cents, g);
- all_influence_values(g, cm);
-
- BOOST_ASSERT(cm[v[0]] == 1);
- BOOST_ASSERT(cm[v[1]] == 1);
- BOOST_ASSERT(cm[v[2]] == 1);
- BOOST_ASSERT(cm[v[3]] == 1);
- BOOST_ASSERT(cm[v[4]] == 1);
-}
-
-template <typename Graph>
-void test_prestige()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
- typedef typename CentralityProperty::container_type CentralityContainer;
- typedef typename CentralityProperty::map_type CentralityMap;
-
- Graph g;
-
- vector<Vertex> v(N);
- build_graph(g, v);
-
- CentralityContainer cents(num_vertices(g));
- CentralityMap cm(cents, g);
- all_prestige_values(g, cm);
-
- BOOST_ASSERT(cm[v[0]] == 2);
- BOOST_ASSERT(cm[v[1]] == 1);
- BOOST_ASSERT(cm[v[2]] == 1);
- BOOST_ASSERT(cm[v[3]] == 0);
- BOOST_ASSERT(cm[v[4]] == 1);
-}
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> Digraph;
-
- test_undirected<Graph>();
- test_influence<Digraph>();
- test_prestige<Digraph>();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,145 +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 <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/constant_property_map.hpp>
-
-#include <boost/graph/floyd_warshall_shortest.hpp>
-#include <boost/graph/eccentricity.hpp>
-#include "io.hpp"
-
-using namespace std;
-using namespace boost;
-
-// number of vertices in the graph
-static const unsigned N = 5;
-
-template <typename Graph>
-struct vertex_vector
-{
- typedef graph_traits<Graph> traits;
- typedef vector<typename traits::vertex_descriptor> type;
-};
-
-template <typename Graph>
-void build_graph(Graph& g,
- typename vertex_vector<Graph>::type& v)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- // add vertices
- for(size_t i = 0; i < N; ++i) {
- v[i] = add_vertex(g);
- }
-
- // add edges
- add_edge(v[0], v[1], g);
- add_edge(v[1], v[2], g);
- add_edge(v[2], v[0], g);
- add_edge(v[3], v[4], g);
- add_edge(v[4], v[0], g);
-};
-
-
-template <typename Graph>
-void test_undirected()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- typedef exterior_vertex_property<Graph, int> EccentricityProperty;
- typedef typename EccentricityProperty::container_type EccentricityContainer;
- typedef typename EccentricityProperty::map_type EccentricityMap;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
- typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
-
- typedef constant_property_map<Edge, int> WeightMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- EccentricityContainer eccs(num_vertices(g));
- DistanceMatrix distances(num_vertices(g));
-
- EccentricityMap em(eccs, g);
- DistanceMatrixMap dm(distances, g);
-
- WeightMap wm(1);
-
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- all_eccentricities(g, dm, em);
- int rad = radius(g, em);
- int dia = diameter(g, em);
-
- BOOST_ASSERT(em[v[0]] == 2);
- BOOST_ASSERT(em[v[1]] == 3);
- BOOST_ASSERT(em[v[2]] == 3);
- BOOST_ASSERT(em[v[3]] == 3);
- BOOST_ASSERT(em[v[4]] == 2);
- BOOST_ASSERT(rad == 2);
- BOOST_ASSERT(dia == 3);
-}
-
-template <typename Graph>
-void test_directed()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- typedef exterior_vertex_property<Graph, int> EccentricityProperty;
- typedef typename EccentricityProperty::container_type EccentricityContainer;
- typedef typename EccentricityProperty::map_type EccentricityMap;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
- typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
-
- typedef constant_property_map<Edge, int> WeightMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- EccentricityContainer eccs(num_vertices(g));
- DistanceMatrix distances(num_vertices(g));
-
- EccentricityMap em(eccs, g);
- DistanceMatrixMap dm(distances, g);
-
- WeightMap wm(1);
-
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- all_eccentricities(g, dm, em);
- int rad = radius(g, em);
- int dia = diameter(g, em);
-
- int inf = numeric_values<int>::infinity();
- BOOST_ASSERT(em[v[0]] == inf);
- BOOST_ASSERT(em[v[1]] == inf);
- BOOST_ASSERT(em[v[2]] == inf);
- BOOST_ASSERT(em[v[3]] == 4);
- BOOST_ASSERT(em[v[4]] == inf);
- BOOST_ASSERT(rad == 4);
- BOOST_ASSERT(dia == inf);
-}
-
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> Digraph;
-
- test_undirected<Graph>();
- test_directed<Digraph>();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/exterior.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,157 +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 <typeinfo>
-#include <cxxabi.h>
-
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-
-#include <boost/graph/constant_property_map.hpp>
-#include <boost/graph/breadth_first_search.hpp>
-#include <boost/graph/floyd_warshall_shortest.hpp>
-#include <boost/graph/visitors.hpp>
-
-using namespace std;
-using namespace boost;
-using namespace __cxxabiv1;
-
-template <typename T>
-const char *
-typename_of(const T&)
-{
- return __cxa_demangle(typeid(T).name(), 0, 0, 0);
-}
-
-template <typename T>
-const char *
-typename_of()
-{
- return __cxa_demangle(typeid(T).name(), 0, 0, 0);
-}
-
-struct VertexProp
-{
- int x;
-};
-
-struct EdgeProp
-{
- EdgeProp() : weight(1) { }
-
- int weight;
-};
-
-template <typename Graph>
-void build_graph(Graph& g)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- static const unsigned N = 5;
- vector<Vertex> v(N);
- vector<Edge> e;
-
- // 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)
- e.push_back(add_edge(v[0], v[1], g).first);
- e.push_back(add_edge(v[1], v[2], g).first);
- e.push_back(add_edge(v[2], v[0], g).first);
- e.push_back(add_edge(v[3], v[4], g).first);
- e.push_back(add_edge(v[4], v[0], g).first);
-};
-
-template <typename Graph>
-void test()
-{
- Graph g;
- build_graph(g);
-
-
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef typename DistanceProperty::container_type DistanceContainer;
- typedef typename DistanceProperty::map_type DistanceMap;
-
- // cout << typename_of<typename Graph::graph_tag>() << "\n";
- // cout << typename_of<DistanceContainer>() << "\n";
- cout << typename_of<DistanceMap>() << "\n";
-
- {
- DistanceContainer dc(num_vertices(g));
- DistanceMap dm(dc, g);
-
- breadth_first_search(g, *vertices(g).first,
- visitor(make_bfs_visitor(record_distances(dm, on_tree_edge())))
- );
- }
-
- // fun with matrices
- {
- typedef typename property_map<Graph, int EdgeProp::*>::type WeightMap;
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
- typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
-
- DistanceMatrix dist(num_vertices(g));
- DistanceMatrixMap dm(dist, g);
- WeightMap wm(get(&EdgeProp::weight, g));
-
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
-
- VertexIterator i, j, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- for(j = vertices(g).first; j != end; ++j) {
- Vertex u = *i, v = *j;
- std::cout << dm[u][v] << " ";
- }
- std::cout << "\n";
- }
-
- // now comes the really fun part... slicing the matrix into
- // a new property map... Good stuff.
- std::cout << "slice:\n";
- for(tie(i, end) = vertices(g); i != end; ++i) {
- DistanceMap d(dm[*i]);
- for(tie(j, end) = vertices(g); j != end; ++j) {
- std::cout << d[*j] << " ";
- }
- std::cout << "\n";
- }
- }
-}
-
-
-int
-main(int argc, char *argv[])
-{
- typedef adjacency_list<vecS, vecS, undirectedS, VertexProp, EdgeProp> AdjVector;
- typedef adjacency_list<listS, listS, undirectedS, VertexProp, EdgeProp> AdjList;
- typedef undirected_graph<VertexProp, EdgeProp> Graph;
-
- cout << "\n*** adjacency_list<vecS, vecS> ***\n";
- test<AdjVector>();
-
- // cout << "\n*** adjacency_list<listS, listS> ***\n";
- // test<AdjList>();
-
- cout << "\n*** undirected_graph<> ***\n";
- test<Graph>();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/generate.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,183 +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/adjacency_list.hpp>
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/generators/complete_graph.hpp>
-#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/generators/path_graph.hpp>
-#include <boost/graph/graphviz.hpp>
-
-using namespace std;
-using namespace boost;
-
-static const int N = 3;
-static const int K = 2;
-
-template <class Graph>
-void test_path()
-{
- Graph g;
- make_path_graph(g, N);
- write_graphviz(cout, g);
-}
-
-template <class Graph, class Direction>
-void test_path(Direction dir)
-{
- Graph g;
- make_path_graph(g, N, dir);
- write_graphviz(cout, g);
-}
-
-
-
-template <class Graph>
-void test_cycle()
-{
- Graph g;
- make_cycle_graph(g, N);
- write_graphviz(cout, g);
-}
-
-template <class Graph, class Cycle>
-void test_cycle(Cycle cycle)
-{
- Graph g;
- make_cycle_graph(g, N, cycle);
- write_graphviz(cout, g);
-}
-
-
-template <class Graph>
-void test_star()
-{
- Graph g;
- make_star_graph(g, N);
- write_graphviz(cout, g);
-}
-
-template <class Graph, class Spoke>
-void test_star(Spoke spokes)
-{
- Graph g;
- make_star_graph(g, N, spokes);
- write_graphviz(cout, g);
-}
-
-
-
-template <class Graph>
-void test_wheel()
-{
- Graph g;
- make_wheel_graph(g, N);
- write_graphviz(cout, g);
-}
-
-template <class Graph, class Cycle, class Spoke>
-void test_wheel(Cycle cycle, Spoke spokes)
-{
- Graph g;
- make_wheel_graph(g, N, cycle, spokes);
- write_graphviz(cout, g);
-}
-
-
-
-template <class Graph>
-void test_prism()
-{
- Graph g;
- make_prism_graph(g, N, K);
- write_graphviz(cout, g);
-}
-
-template <class Graph, class Cycle, class Spoke>
-void test_prism(Cycle cycle, Spoke spokes)
-{
- Graph g;
- make_prism_graph(g, N, K, cycle, spokes);
- write_graphviz(cout, g);
-}
-
-
-template <class Graph>
-void test_web()
-{
- Graph g;
- make_web_graph(g, N, K);
- write_graphviz(cout, g);
-}
-
-template <class Graph, class Cycle, class Spoke>
-void test_web(Cycle cycle, Spoke spokes)
-{
- Graph g;
- make_web_graph(g, N, K, cycle, spokes);
- write_graphviz(cout, g);
-}
-
-
-template <class Graph>
-void test_complete()
-{
- Graph g;
- make_complete_graph(g, N);
- write_graphviz(cout, g);
-}
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> DiGraph;
-
- with_clockwise_cycle clock;
- with_bidirected_spokes spokes;
-
- /*
- test_complete<Graph>();
- test_path<Graph>();
- test_cycle<Graph>();
- test_star<Graph>();
- test_wheel<Graph>();
- test_prism<Graph>();
- */
- // test_web<Graph>();
-
- test_prism<DiGraph>(clock, spokes);
-
- /*
- test_path<DiGraph>(with_forward_edges());
- test_path<DiGraph>(with_reverse_edges());
- test_path<DiGraph>(with_bidirected_edges());
- */
-
- /*
- test<DiGraph>(clockwise, outward);
- test<DiGraph>(counterclockwise, outward);
- test<DiGraph>(bothwise, outward);
- test<DiGraph>(clockwise, inward);
- test<DiGraph>(counterclockwise, inward);
- test<DiGraph>(bothwise, inward);
- test<DiGraph>(clockwise, iospokes);
- test<DiGraph>(counterclockwise, iospokes);
- test<DiGraph>(bothwise, iospokes);
- */
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/index.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/index.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,63 +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 <boost/test/minimal.hpp>
-#include <boost/graph/undirected_graph.hpp>
-
-using namespace std;
-using namespace boost;
-
-typedef undirected_graph<> Graph;
-typedef Graph::vertex_descriptor Vertex;
-typedef property_map<Graph, vertex_index_t>::type IndexMap;
-
-int test_main(int, char*[])
-{
- static const size_t N = 5;
- Graph g;
- Vertex v[N];
-
- IndexMap x = get(vertex_index, g);
-
- // build up the graph
- for(size_t i = 0; i < N; ++i) {
- v[i] = add_vertex(g);
- }
-
- // after the first build, we should have these conditions
- BOOST_CHECK(max_vertex_index(g) == N);
- for(size_t i = 0; i < N; ++i) {
- BOOST_CHECK(get_vertex_index(v[i], g) == i);
- }
-
- // remove some vertices and re-add them...
- for(size_t i = 0; i < N; ++i) remove_vertex(v[i], g);
- BOOST_CHECK(num_vertices(g) == 0);
-
- for(size_t i = 0; i < N; ++i) {
- v[i] = add_vertex(g);
- }
-
- // before renumbering, our vertices should be off by
- // about N...
- BOOST_CHECK(max_vertex_index(g) == 10);
- for(size_t i = 0; i < N; ++i) {
- BOOST_CHECK(get_vertex_index(v[i], g) == N + i);
- }
-
- // renumber vertices
- renumber_vertex_indices(g);
-
- // and we should be back to the initial condition
- BOOST_CHECK(max_vertex_index(g) == N);
- for(size_t i = 0; i < N; ++i) {
- BOOST_CHECK(get_vertex_index(v[i], g) == i);
- }
-
- return 0;
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/io.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/io.hpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,152 +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 <boost/graph/properties.hpp>
-
-template <typename V, typename G>
-struct vertex_printer
-{
- vertex_printer(V v, const G& g) : vert(v), graph(g) { }
- V vert;
- const G& graph;
-};
-
-template <typename V, typename G>
-inline vertex_printer<V,G> print_vertex(V v, const G& g)
-{ return vertex_printer<V,G>(v, g); }
-
-template <typename V, typename G>
-inline std::ostream& operator << (std::ostream& os, const vertex_printer<V, G>& vp)
-{
- os << boost::get(boost::vertex_index, vp.graph, vp.vert);
- return os;
-}
-
-template <typename E, typename G>
-struct edge_printer
-{
- edge_printer(E e, const G& g) : edge(e), graph(g) { }
- E edge;
- const G& graph;
-};
-
-template <typename E, typename G>
-inline edge_printer<E,G> print_edge(E e, const G& g)
-{ return edge_printer<E,G>(e, g); }
-
-template <typename E, typename G>
-inline std::ostream& operator <<(std::ostream& os, const edge_printer<E,G>& ep)
-{
- os << "(" << print_vertex(source(ep.edge, ep.graph), ep.graph) << ","
- << print_vertex(target(ep.edge, ep.graph), ep.graph) << ")";
- return os;
-}
-
-template <typename P, typename G>
-struct path_printer
-{
- path_printer(const P& p, const G& g) : path(p), graph(g) { }
- P path;
- const G& graph;
-};
-
-template <typename P, typename G>
-inline path_printer<P,G> print_path(const P& p, const G& g)
-{ return path_printer<P,G>(p, g); }
-
-template <typename P, typename G>
-inline std::ostream& operator <<(std::ostream& os, const path_printer<P,G>& pp)
-{
- typename P::const_iterator i, end = pp.path.end();
- for(i = pp.path.begin(); i != end; ++i) {
- os << print_vertex(*i, pp.graph) << " ";
- }
- return os;
-}
-
-template <typename M, typename G>
-struct vertex_map_printer
-{
- vertex_map_printer(M m, const G& g) : map(m), graph(g) { }
- M map;
- const G& graph;
-};
-
-template <typename M, typename G>
-inline vertex_map_printer<M,G>
-print_vertex_map(const M& m, const G& g)
-{ return vertex_map_printer<M,G>(m, g); }
-
-template <typename M, typename G>
-inline std::ostream&
-operator <<(std::ostream& os, const vertex_map_printer<M,G>& mp)
-{
- typename boost::graph_traits<G>::vertex_iterator i, end;
- os << "{\n";
- for(tie(i, end) = boost::vertices(mp.graph); i != end; ++i) {
- os << print_vertex(*i, mp.graph) << ": " << mp.map[*i] << "\n";
- }
- os << "}\n";
- return os;
-}
-
-template <typename M, typename G>
-struct edge_map_printer
-{
- edge_map_printer(M m, const G& g) : map(m), graph(g) { }
- M map;
- const G& graph;
-};
-
-template <typename M, typename G>
-inline edge_map_printer<M,G>
-print_edge_map(const M& m, const G& g)
-{ return edge_map_printer<M,G>(m, g); }
-
-template <typename M, typename G>
-inline std::ostream&
-operator <<(std::ostream& os, const edge_map_printer<M,G>& mp)
-{
- typename boost::graph_traits<G>::edge_iterator i, end;
- os << "{\n";
- for(tie(i, end) = boost::edges(mp.graph); i != end; ++i) {
- os << print_edge(*i, mp.graph) << mp.map[*i] << "\n";
- }
- os << "}\n";
- return os;
-}
-
-template <typename M, typename G>
-struct vertex_matrix_printer
-{
- vertex_matrix_printer(const M& m, const G& g) : matrix(m), graph(g) { }
- const M& matrix;
- const G& graph;
-};
-
-template <typename M, typename G>
-inline vertex_matrix_printer<M,G>
-print_vertex_matrix(const M& m, const G& g)
-{ return vertex_matrix_printer<M,G>(m, g); }
-
-template <typename M, typename G>
-inline std::ostream&
-operator <<(std::ostream& os, const vertex_matrix_printer<M,G>& mp)
-{
- typename boost::graph_traits<G>::vertex_iterator i, j, end;
- os << "{\n";
- for(tie(i, end) = boost::vertices(mp.graph); i != end; ++i) {
- os << "{ ";
- for(j = boost::vertices(mp.graph).first; j != end; ++j) {
- os << mp.matrix[*i][*j] << " ";
- }
- os << "}\n";
- }
- os << "}\n";
- return os;
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/k_pairs.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/k_pairs.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,299 +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 <vector>
-
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/constant_property_map.hpp>
-#include <boost/graph/breadth_first_search.hpp>
-#include <boost/graph/visitors.hpp>
-
-using namespace std;
-using namespace boost;
-
-// I think I see how this is done. Basically, there's an initial search
-// for a baseline path from every vertex to v. A second search can be
-// used to build heaps that record the off-path distance between the source
-// the off-path vertex and the target. Or something like that. I'm not sure.
-
-typedef property<edge_index_t, unsigned> EdgeIndex;
-
-struct path_visitor
-{
-};
-
-template <typename V, typename G>
-struct vertex_printer
-{
- vertex_printer(V v, const G& g) : vert(v), graph(g) { }
- V vert; const G& graph;
-};
-template <typename V, typename G>
-inline vertex_printer<V,G> print_vertex(V v, const G& g)
-{ return vertex_printer<V,G>(v, g); }
-template <typename V, typename G>
-inline ostream& operator << (ostream& os, const vertex_printer<V, G>& vp)
-{
- os << get(vertex_index, vp.graph, vp.vert);
- return os;
-}
-
-template <typename E, typename G>
-struct edge_printer
-{
- edge_printer(E e, const G& g) : edge(e), graph(g) { }
- E edge; const G& graph;
-};
-template <typename E, typename G>
-inline edge_printer<E,G> print_edge(E e, const G& g)
-{ return edge_printer<E,G>(e, g); }
-template <typename E, typename G>
-inline ostream& operator <<(ostream& os, const edge_printer<E,G>& ep)
-{
- os << "(" << print_vertex(source(ep.edge, ep.graph), ep.graph) << ","
- << print_vertex(target(ep.edge, ep.graph), ep.graph) << ")";
- return os;
-}
-
-template <typename P, typename G>
-struct path_printer
-{
- path_printer(const P& p, const G& g) : path(p), graph(g) { }
- P path; const G& graph;
-};
-template <typename P, typename G>
-inline path_printer<P,G> print_path(const P& p, const G& g)
-{ return path_printer<P,G>(p, g); }
-template <typename P, typename G>
-inline ostream& operator <<(ostream& os, const path_printer<P,G>& pp)
-{
- typename P::const_iterator i, end = pp.path.end();
- for(i = pp.path.begin(); i != end; ++i) {
- os << print_edge(*i, pp.graph) << " ";
- }
- return os;
-}
-
-
-
-template <typename Graph>
-void build_graph(Graph& g)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- static const unsigned N = 5;
- vector<Vertex> v(N);
- vector<Edge> e;
-
- // 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)
- e.push_back(add_edge(v[0], v[1], g).first);
- e.push_back(add_edge(v[1], v[2], g).first);
- e.push_back(add_edge(v[2], v[0], g).first);
- e.push_back(add_edge(v[3], v[4], g).first);
- e.push_back(add_edge(v[4], v[0], g).first);
-
- // allocate indices for the vertices
- for(size_t i = 0; i < N; ++i) {
- put(edge_index, g, e[i], i);
- }
-};
-
-// The tail(e,g) of a directed edge is its source vertex (the tail
-// of the arrow).
-template <typename Graph>
-inline typename graph_traits<Graph>::vertex_descriptor
-tail(typename graph_traits<Graph>::edge_descriptor e, const Graph& g)
-{ return source(e, g); }
-
-// The head(e,g) of a directed edge is its target vertex (the head
-// of the arrow).
-template <typename Graph>
-inline typename graph_traits<Graph>::vertex_descriptor
-head(typename graph_traits<Graph>::edge_descriptor e, const Graph& g)
-{ return target(e, g); }
-
-// Given a vertex v (in graph g), this returns the next vertex reached
-// after v on the path from v to /some other vertex/ in the shortest
-// path tree, T. Note that the other vertex is implicit in the parent
-// edge map - it's the root.
-template <typename Graph, typename ParentEdgeMap>
-inline typename graph_traits<Graph>::vertex_descriptor
-next_in_path(typename graph_traits<Graph>::vertex_descriptor v,
- const Graph& g,
- ParentEdgeMap pm)
-{
- return source(pm[v], g);
-}
-
-
-template <typename Graph,
- typename DistanceMap,
- typename WeightMap>
-typename property_traits<WeightMap>::value_type
-lost_distance(const Graph& g,
- typename graph_traits<Graph>::edge_descriptor e,
- DistanceMap dm,
- WeightMap wm)
-{
- typedef typename property_traits<WeightMap>::value_type Value;
- Value dhead = dm[head(e, g)];
- Value dtail = dm[tail(e, g)];
- return wm[e] + dhead - dtail;
-}
-
-
-template <typename Graph,
- typename DistanceMap,
- typename ParentEdgeMap>
-void
-shortest_paths_tree(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor v,
- DistanceMap dm,
- ParentEdgeMap pm)
-{
- // This function needs to be genericized to work with arbitrary shortest
- // paths algorithms.
- breadth_first_search(g, v,
- visitor(make_bfs_visitor(make_pair(
- record_distances(dm, on_tree_edge()),
- record_edge_predecessors(pm, on_tree_edge()))))
- );
-}
-
-template <typename Graph,
- typename ParentEdgeMap,
- typename Path>
-void
-extract_path(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor dst,
- ParentEdgeMap pm,
- Path& path)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- // This function walks the sp-tree from src, an arbitrary vertex
- // in g to dst - the initial target of a shortest path search.
- while(src != dst) {
- Edge e = pm[src];
- path.push_front(e); // guarntee a correct ordering in the path
- src = next_in_path(src, g, pm);
- }
-}
-
-
-template <typename Graph,
- typename Vertex,
- typename EdgeIndexMap,
- typename WeightMap>
-void
-eppstein_k_shortest_paths(const Graph& g, Vertex src, Vertex dst, size_t k,
- EdgeIndexMap eim, WeightMap wm)
-{
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
- typedef typename graph_traits<Graph>::edge_iterator EdgeIterator;
- typedef list<Edge> Path;
- typedef list<Path> PathList;
-
- typedef exterior_vertex_property<Graph, size_t> DistanceProperty;
- typedef typename DistanceProperty::container_type DistanceVector;
- typedef typename DistanceProperty::map_type DistanceMap;
-
- typedef exterior_vertex_property<Graph, Edge> ParentEdgeProperty;
- typedef typename ParentEdgeProperty::container_type ParentEdgeVector;
- typedef typename ParentEdgeProperty::map_type ParentEdgeMap;
-
- typedef exterior_edge_property<Graph, int> EdgeLossProperty;
- typedef typename EdgeLossProperty::container_type EdgeLossContainer;
- typedef typename EdgeLossProperty::map_type EdgeLossMap;
-
- PathList paths;
-
- // make sure that these vertices are (at least) connected to
- // something else - and that they aren't the same vertex.
- if((out_degree(src, g) == 0) ||
- (out_degree(dst, g) == 0) ||
- (src == dst))
- {
- return;
- }
-
- // This is kind of dirty, but the computation proceeds a little
- // bit "backwardsly" if we leave src and dst the way they are.
- // Swapping them makes the output a little more coherent given
- // the input.
- std::swap(src, dst);
-
- // start by computing the shortest paths from t. this forms our
- // "root" shortest path. Everything else is a "sidetrack".
- DistanceVector distances(num_vertices(g));
- DistanceMap dm(distances, g);
- ParentEdgeVector parents(num_vertices(g));
- ParentEdgeMap pm(parents, g);
-
- // this is the big "preprocessing" stage. We establish a baseline
- // of all shortest paths to the destination (target)
- shortest_paths_tree(g, dst, dm ,pm);
-
- // compute the sidetracks for the resultant "tree". the lost vector
- // stores the lost distance for each edge
- EdgeLossContainer loss(num_edges(g));
- EdgeLossMap elm(loss, g);
- EdgeIterator i, end;
- for(tie(i, end) = edges(g); i != end; ++i) {
- elm[*i] = lost_distance(g, *i, dm, wm);
- }
-
- // this becomes one of the shortest paths...
- typename PathList::iterator pi = paths.insert(paths.end(), Path());
- extract_path(g, src, dst, pm, *pi);
- std::cout << print_path(*pi, g) << "\n";
-}
-
-
-template <typename Graph>
-void test()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
- typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
-
- typedef constant_property_map<Edge, unsigned> WeightMap;
- typedef typename property_map<Graph, edge_index_t>::type EdgeIndexMap;
-
- Graph g;
- build_graph(g);
- VertexIterator i, j;
- tie(i, j) = vertices(g);
-
- // See the labels for correct ordering of flow
- Vertex s = *i; // Vertex s
- Vertex t = *prior(j, 2); // Vertex t
-
- WeightMap wm(1);
- EdgeIndexMap eim(get(edge_index, g));
- eppstein_k_shortest_paths(g, s, t, 3, eim, wm);
-}
-
-int
-main()
-{
- typedef undirected_graph<no_property, EdgeIndex > Graph;
-
- test<Graph>();
-
- return 0;
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,143 +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 <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/exterior_property.hpp>
-#include <boost/graph/constant_property_map.hpp>
-
-#include <boost/graph/floyd_warshall_shortest.hpp>
-#include <boost/graph/geodesic_distance.hpp>
-
-using namespace std;
-using namespace boost;
-
-// useful types
-// number of vertices in the graph
-static const unsigned N = 5;
-
-template <typename Graph>
-struct vertex_vector
-{
- typedef graph_traits<Graph> traits;
- typedef vector<typename traits::vertex_descriptor> type;
-};
-
-template <typename Graph>
-void build_graph(Graph& g,
- typename vertex_vector<Graph>::type& v)
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
- // add vertices
- for(size_t i = 0; i < N; ++i) {
- v[i] = add_vertex(g);
- }
-
- // add edges
- add_edge(v[0], v[1], g);
- add_edge(v[1], v[2], g);
- add_edge(v[2], v[0], g);
- add_edge(v[3], v[4], g);
- add_edge(v[4], v[0], g);
-};
-
-
-template <typename Graph>
-void test_undirected()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- typedef exterior_vertex_property<Graph, float> CentralityProperty;
- typedef typename CentralityProperty::container_type CentralityContainer;
- typedef typename CentralityProperty::map_type CentralityMap;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
- typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
-
- typedef constant_property_map<Edge, int> WeightMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- CentralityContainer centralities(num_vertices(g));
- DistanceMatrix distances(num_vertices(g));
-
- CentralityMap cm(centralities, g);
- DistanceMatrixMap dm(distances, g);
-
- WeightMap wm(1);
-
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- float geo1 = all_mean_geodesics(g, dm, cm);
- float geo2 = small_world_distance(g, cm);
-
- BOOST_ASSERT(cm[v[0]] == float(5)/4);
- BOOST_ASSERT(cm[v[1]] == float(7)/4);
- BOOST_ASSERT(cm[v[2]] == float(7)/4);
- BOOST_ASSERT(cm[v[3]] == float(9)/4);
- BOOST_ASSERT(cm[v[4]] == float(6)/4);
- BOOST_ASSERT(geo1 == float(34)/20);
- BOOST_ASSERT(geo1 == geo2);
-}
-
-template <typename Graph>
-void test_directed()
-{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
- typedef exterior_vertex_property<Graph, float> CentralityProperty;
- typedef typename CentralityProperty::container_type CentralityContainer;
- typedef typename CentralityProperty::map_type CentralityMap;
-
- typedef exterior_vertex_property<Graph, int> DistanceProperty;
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
- typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
-
- typedef constant_property_map<Edge, int> WeightMap;
-
- Graph g;
- vector<Vertex> v(N);
- build_graph(g, v);
-
- CentralityContainer centralities(num_vertices(g));
- DistanceMatrix distances(num_vertices(g));
-
- CentralityMap cm(centralities, g);
- DistanceMatrixMap dm(distances, g);
-
- WeightMap wm(1);
-
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- float geo1 = all_mean_geodesics(g, dm, cm);
- float geo2 = small_world_distance(g, cm);
-
- float inf = numeric_values<float>::infinity();
- BOOST_ASSERT(cm[v[0]] == inf);
- BOOST_ASSERT(cm[v[1]] == inf);
- BOOST_ASSERT(cm[v[2]] == inf);
- BOOST_ASSERT(cm[v[3]] == float(10)/4);
- BOOST_ASSERT(cm[v[4]] == inf);
- BOOST_ASSERT(geo1 == inf);
- BOOST_ASSERT(geo1 == geo2);
-}
-
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> Digraph;
-
- test_undirected<Graph>();
- test_directed<Digraph>();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/misc.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/misc.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,93 +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 <vector>
-#include <tr1/unordered_map>
-#include <boost/utility.hpp>
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/connected_components.hpp>
-#include <boost/graph/strong_components.hpp>
-
-using namespace std;
-using namespace boost;
-
-namespace std
-{
- namespace tr1
- {
- template <>
- struct hash<boost::detail::edge_desc_impl<undirected_tag, void*> >
- : public std::unary_function<
- boost::detail::edge_desc_impl<undirected_tag, void*>,
- std::size_t>
- {
- typedef boost::detail::edge_desc_impl<undirected_tag, void*> Edge;
- std::size_t operator ()(Edge e)
- {
- std::tr1::hash<Edge::property_type*> hasher;
- return hasher(e.get_property());
- }
- };
- }
-}
-
-static void undirected_test()
-{
- typedef undirected_graph<> Graph;
- typedef Graph::vertex_descriptor Vertex;
- typedef Graph::edge_descriptor Edge;
- typedef tr1::unordered_map<Vertex, int> component_map_type;
- typedef associative_property_map<component_map_type> component_map;
-
- const size_t N = 5;
- undirected_graph<> g;
-
- vector<Vertex> verts(N);
- for(size_t i = 0; i < N; ++i) {
- verts[i] = add_vertex(g);
- }
- add_edge(verts[0], verts[1], g);
- add_edge(verts[1], verts[2], g);
- add_edge(verts[3], verts[4], g);
-
- component_map_type mapping(num_vertices(g));
- component_map comps(mapping);
- size_t c = connected_components(g, comps);
-
- cout << c << "\n";
-
- Graph::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- cout << *i << "\t" << comps[*i] << "\n";
- }
-}
-
-static void directed_test()
-{
- typedef directed_graph<> Graph;
- typedef Graph::vertex_descriptor Vertex;
- typedef Graph::edge_descriptor Edge;
- typedef tr1::unordered_map<Vertex, int> component_map_type;
- typedef associative_property_map<component_map_type> component_map;
-
- Graph g;
- Vertex u = add_vertex(g);
- Vertex v = add_vertex(g);
- add_edge(u, v, g);
-
- component_map_type mapping(num_vertices(g));
- component_map comps(mapping);
- strong_components(g, comps);
-}
-
-int
-main()
-{
- undirected_test();
- directed_test();
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/mutable.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,81 +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 <boost/test/minimal.hpp>
-#include <boost/graph/undirected_graph.hpp>
-
-using namespace std;
-using namespace boost;
-
-struct Foo
-{
- int foo;
-};
-
-typedef undirected_graph<Foo> Graph;
-typedef Graph::vertex_descriptor Vertex;
-typedef Graph::edge_descriptor Edge;
-
-typedef adjacency_list<listS, listS, undirectedS> Test;
-
-int test_main(int, char*[])
-{
- Graph g;
- Vertex v[5];
- Edge e[5];
-
- // simple starting conditions...
- BOOST_CHECK(num_vertices(g) == 0);
- BOOST_CHECK(num_edges(g) == 0);
-
- // build a couple verts and remove them
- v[0] = add_vertex(g);
- v[1] = add_vertex(g);
- BOOST_CHECK(num_vertices(g) == 2);
-
- remove_vertex(v[0], g);
- BOOST_CHECK(num_vertices(g) == 1);
-
- remove_vertex(v[1], g);
- BOOST_CHECK(num_vertices(g) == 0);
-
- // rebuild the graph, but add some edges this time
- for(int i = 0; i < 5; ++i) v[i] = add_vertex(g);
-
- e[0] = add_edge(v[0], v[1], g).first;
- e[1] = add_edge(v[1], v[2], g).first;
- e[2] = add_edge(v[2], v[3], g).first;
- BOOST_CHECK(num_edges(g) == 3);
- BOOST_CHECK(*edges(g).first == e[0]);
-
- remove_edge(v[0], v[1], g); // removes e[0]
- BOOST_CHECK(num_edges(g) == 2);
- BOOST_CHECK(*edges(g).first == e[1]);
-
- remove_edge(e[1], g); // removes e[1]
- BOOST_CHECK(num_edges(g) == 1);
- BOOST_CHECK(*edges(g).first == e[2]);
-
- remove_edge(edges(g).first, g); // remove e[2]
- BOOST_CHECK(num_edges(g) == 0);
-
-
- // build a bunch of edges between two verts
- for(int i = 0; i < 3; ++i) e[i] = add_edge(v[0], v[1], g).first;
- BOOST_CHECK(num_edges(g) == 3);
-
- remove_edge(v[0], v[1], g);
- BOOST_CHECK(num_edges(g) == 0);
-
- Test f;
- v[0] = add_vertex(f);
- v[1] = add_vertex(f);
- add_edge(v[0], v[1], f);
-
- return 0;
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/properties.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/properties.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,46 +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 <boost/graph/undirected_graph.hpp>
-
-using namespace std;
-using namespace boost;
-
-struct Foo
-{
- int foo;
-};
-
-typedef undirected_graph<Foo> Graph;
-typedef Graph::vertex_descriptor Vertex;
-
-typedef property_map<Graph, vertex_index_t>::type IndexMap;
-typedef property_map<Graph, int Foo::*>::type FooMap;
-
-int main()
-{
- Graph g;
-
- Vertex u = add_vertex(g);
- Vertex v = add_vertex(g);
-
- IndexMap indices = get(vertex_index, g);
- FooMap foos = get(&Foo::foo, g);
-
- g[u].foo = 3;
- g[v].foo = 5;
-
- cout << indices[u] << " " << foos[u] << "\n";
- cout << indices[v] << " " << foos[v] << "\n";
-
- cout << "test: " << get(&Foo::foo, g, v) << "\n";
- put(&Foo::foo, g, v, 12);
- cout << "test: " << g[v].foo << "\n";
-
- return 0;
-}
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/range.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/range.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,87 +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 <vector>
-#include <boost/utility.hpp>
-#include <boost/test/minimal.hpp>
-#include <boost/graph/undirected_graph.hpp>
-#include <boost/graph/breadth_first_search.hpp>
-
-using namespace std;
-using namespace boost;
-
-typedef undirected_graph<> Graph;
-typedef Graph::vertex_descriptor Vertex;
-
-static const int N = 5;
-
-void build_n_clique(Graph& g, int n)
-{
- // build and tear down an N-clique
- for(int i = 0; i < N; ++i) {
- add_vertex(g);
- }
- Graph::vertex_iterator i, j, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- for(j = next(i); j != end; ++j) {
- add_edge(*i, *j, g);
- }
- }
-}
-
-void clear(Graph& g)
-{
- // apparently, the only way to safely clear the list of vertices
- // is to use a trailing iterator type of trick. it's not pretty,
- // but it works.
- Graph::vertex_iterator i, j, end;
- tie(i, end) = vertices(g);
- for(j = i; i != end; i = j) {
- ++j;
- clear_vertex(*i, g);
- remove_vertex(*i, g);
- }
-}
-
-int test_main(int, char *argv[])
-{
- Graph g;
-
- build_n_clique(g, N);
- clear(g);
- build_n_clique(g, N);
-
- cout << num_vertices(g) << "/" << num_edges(g) << "\n";
- cout << max_vertex_index(g) << "\n";
-
- // renumber_vertex_indices(g);
- //
- // WARNING: This will crash without the previous line of code.
- // Why? Deep in the guts of the BFS that gets called below,
- // the algorithm allocates a N-vector of colors that they plan
- // to access via vertex indices. The only problem is that the
- // vertex indices should now be in the range [N, 2*N), well
- // beyond the bounds of the vectors used in the queue.
- //
- // Obviously uncommenting the previous line of code will work
- // just fine, but a better approach might be to change the
- // algorithm to create a vector of size [0, max_vertex_index).
- // Despite the fact that there may gaps in the vector, correct
- // usage of indices will mean that you never actually access
- // non-vertex elements in your exterior property vectors.
-
- breadth_first_search(
- g, *vertices(g).first,
- visitor(
- make_bfs_visitor(null_visitor())
- )
- );
-
-
- return 0;
-}
Copied: sandbox/SOC/2007/graphs/libs/graph/test/runtime/Jamfile.v2 (from r38888, /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/runtime/Jamfile.v2 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
@@ -3,12 +3,10 @@
project
: requirements
- <include>../../../
+ <include>../../../../
<include>$BOOST_ROOT
;
-build-project concept ;
-
test-suite graph_test :
[ run constant_property_map.cpp ]
[ run degree_centrality.cpp ]
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/tiernan_all_cycles.cpp 2007-08-24 09:28:14 EDT (Fri, 24 Aug 2007)
+++ (empty file)
@@ -1,79 +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 <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/erdos_renyi_generator.hpp>
-
-#include <boost/random/linear_congruential.hpp>
-
-using namespace std;
-using namespace boost;
-
-struct cycle_validator
-{
- cycle_validator(size_t& c)
- : cycles(c)
- { }
-
- template <typename Path, typename Graph>
- void cycle(const Path& p, const Graph& g)
- {
- ++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);
- }
- BOOST_ASSERT(edge(p.back(), p.front(), g).second);
- }
-
- size_t& cycles;
-};
-
-template <typename Graph>
-void test()
-{
- typedef erdos_renyi_iterator<boost::minstd_rand, Graph> er;
-
- // 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[])
-{
- typedef undirected_graph<> Graph;
- typedef directed_graph<> DiGraph;
-
- std::cout << "*** undirected ***\n";
- test<Graph>();
-
- std::cout << "*** directed ***\n";
- test<DiGraph>();
-}