#include <boost/lexical_cast.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/random.hpp>
-#include <boost/test/minimal.hpp>
+#include <boost/core/lightweight_test.hpp>
using namespace boost;
-typedef adjacency_list<vecS, vecS, undirectedS> VectorGraph;
+typedef adjacency_list< vecS, vecS, undirectedS > VectorGraph;
-typedef adjacency_list<listS, listS, undirectedS,
- property<vertex_index_t, unsigned int> > ListGraph;
+typedef adjacency_list< listS, listS, undirectedS,
+ property< vertex_index_t, unsigned int > >
+ ListGraph;
-template <typename Graph>
-void test_graph(const Graph& graph) {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+template < typename Graph > void test_graph(const Graph& graph)
+{
+ typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
+ typedef
+ typename graph_traits< Graph >::vertices_size_type vertices_size_type;
+
+ typedef
+ typename property_map< Graph, vertex_index_t >::type IndexPropertyMap;
- typedef typename property_map<Graph, vertex_index_t>::type IndexPropertyMap;
+ typedef std::map< vertex_descriptor, vertices_size_type > RankMap;
+ typedef associative_property_map< RankMap > RankPropertyMap;
- typedef std::map<vertex_descriptor, vertices_size_type> RankMap;
- typedef associative_property_map<RankMap> RankPropertyMap;
+ typedef std::vector< vertex_descriptor > ParentMap;
+ typedef iterator_property_map< typename ParentMap::iterator,
+ IndexPropertyMap, vertex_descriptor, vertex_descriptor& >
+ IndexParentMap;
- typedef std::vector<vertex_descriptor> ParentMap;
- typedef iterator_property_map<typename ParentMap::iterator,
- IndexPropertyMap, vertex_descriptor, vertex_descriptor&> IndexParentMap;
+ RankMap rank_map;
+ RankPropertyMap rank_property_map(rank_map);
- RankMap rank_map;
- RankPropertyMap rank_property_map(rank_map);
+ ParentMap parent_map(num_vertices(graph));
+ IndexParentMap index_parent_map(parent_map.begin());
- ParentMap parent_map(num_vertices(graph));
- IndexParentMap index_parent_map(parent_map.begin());
+ // Create disjoint sets of vertices from the graph
+ disjoint_sets< RankPropertyMap, IndexParentMap > vertex_sets(
+ rank_property_map, index_parent_map);
- // Create disjoint sets of vertices from the graph
- disjoint_sets<RankPropertyMap, IndexParentMap>
- vertex_sets(rank_property_map, index_parent_map);
+ initialize_incremental_components(graph, vertex_sets);
+ incremental_components(graph, vertex_sets);
- initialize_incremental_components(graph, vertex_sets);
- incremental_components(graph, vertex_sets);
+ // Build component index from the graph's vertices, its index map,
+ // and the disjoint sets.
+ typedef component_index< vertices_size_type > Components;
+ Components vertex_components(
+ parent_map.begin(), parent_map.end(), get(boost::vertex_index, graph));
- // Build component index from the graph's vertices, its index map,
- // and the disjoint sets.
- typedef component_index<vertices_size_type> Components;
- Components vertex_components(parent_map.begin(),
- parent_map.end(),
- get(boost::vertex_index, graph));
+ // Create a reverse-lookup map for vertex indices
+ std::vector< vertex_descriptor > reverse_index_map(num_vertices(graph));
- // Create a reverse-lookup map for vertex indices
- std::vector<vertex_descriptor> reverse_index_map(num_vertices(graph));
+ BOOST_FOREACH (vertex_descriptor vertex, vertices(graph))
+ {
+ reverse_index_map[get(get(boost::vertex_index, graph), vertex)]
+ = vertex;
+ }
- BOOST_FOREACH(vertex_descriptor vertex, vertices(graph)) {
- reverse_index_map[get(get(boost::vertex_index, graph), vertex)] = vertex;
- }
+ // Verify that components are really connected
+ BOOST_FOREACH (vertices_size_type component_index, vertex_components)
+ {
- // Verify that components are really connected
- BOOST_FOREACH(vertices_size_type component_index,
- vertex_components) {
+ std::set< vertex_descriptor > component_vertices;
- std::set<vertex_descriptor> component_vertices;
+ BOOST_FOREACH (
+ vertices_size_type child_index, vertex_components[component_index])
+ {
- BOOST_FOREACH(vertices_size_type child_index,
- vertex_components[component_index]) {
+ vertex_descriptor child_vertex = reverse_index_map[child_index];
+ component_vertices.insert(child_vertex);
- vertex_descriptor child_vertex = reverse_index_map[child_index];
- component_vertices.insert(child_vertex);
-
- } // foreach child_index
+ } // foreach child_index
- // Verify that children are connected to each other in some
- // manner, but not to vertices outside their component.
- BOOST_FOREACH(vertex_descriptor child_vertex,
- component_vertices) {
+ // Verify that children are connected to each other in some
+ // manner, but not to vertices outside their component.
+ BOOST_FOREACH (vertex_descriptor child_vertex, component_vertices)
+ {
- // Skip orphan vertices
- if (out_degree(child_vertex, graph) == 0) {
- continue;
- }
+ // Skip orphan vertices
+ if (out_degree(child_vertex, graph) == 0)
+ {
+ continue;
+ }
- // Make sure at least one edge exists between [child_vertex] and
- // another vertex in the component.
- bool edge_exists = false;
+ // Make sure at least one edge exists between [child_vertex] and
+ // another vertex in the component.
+ bool edge_exists = false;
- BOOST_FOREACH(edge_descriptor child_edge,
- out_edges(child_vertex, graph)) {
+ BOOST_FOREACH (
+ edge_descriptor child_edge, out_edges(child_vertex, graph))
+ {
- if (component_vertices.count(target(child_edge, graph)) > 0) {
- edge_exists = true;
- break;
- }
+ if (component_vertices.count(target(child_edge, graph)) > 0)
+ {
+ edge_exists = true;
+ break;
+ }
- } // foreach child_edge
+ } // foreach child_edge
- BOOST_REQUIRE(edge_exists);
+ BOOST_TEST(edge_exists);
- } // foreach child_vertex
+ } // foreach child_vertex
- } // foreach component_index
+ } // foreach component_index
} // test_graph
-int test_main(int argc, char* argv[])
+int main(int argc, char* argv[])
{
- std::size_t vertices_to_generate = 100,
- edges_to_generate = 50,
- random_seed = time(0);
-
- // Parse command-line arguments
+ std::size_t vertices_to_generate = 100, edges_to_generate = 50,
+ random_seed = time(0);
- if (argc > 1) {
- vertices_to_generate = lexical_cast<std::size_t>(argv[1]);
- }
+ // Parse command-line arguments
- if (argc > 2) {
- edges_to_generate = lexical_cast<std::size_t>(argv[2]);
- }
+ if (argc > 1)
+ {
+ vertices_to_generate = lexical_cast< std::size_t >(argv[1]);
+ }
- if (argc > 3) {
- random_seed = lexical_cast<std::size_t>(argv[3]);
- }
+ if (argc > 2)
+ {
+ edges_to_generate = lexical_cast< std::size_t >(argv[2]);
+ }
- minstd_rand generator(random_seed);
+ if (argc > 3)
+ {
+ random_seed = lexical_cast< std::size_t >(argv[3]);
+ }
- // Generate random vector and list graphs
- VectorGraph vector_graph;
- generate_random_graph(vector_graph, vertices_to_generate,
- edges_to_generate, generator, false);
+ minstd_rand generator(random_seed);
- test_graph(vector_graph);
+ // Generate random vector and list graphs
+ VectorGraph vector_graph;
+ generate_random_graph(vector_graph, vertices_to_generate, edges_to_generate,
+ generator, false);
- ListGraph list_graph;
- generate_random_graph(list_graph, vertices_to_generate,
- edges_to_generate, generator, false);
+ test_graph(vector_graph);
- // Assign indices to list_graph's vertices
- graph_traits<ListGraph>::vertices_size_type index = 0;
- BOOST_FOREACH(graph_traits<ListGraph>::vertex_descriptor vertex,
- vertices(list_graph)) {
- put(get(boost::vertex_index, list_graph), vertex, index++);
- }
+ ListGraph list_graph;
+ generate_random_graph(
+ list_graph, vertices_to_generate, edges_to_generate, generator, false);
- test_graph(list_graph);
+ // Assign indices to list_graph's vertices
+ graph_traits< ListGraph >::vertices_size_type index = 0;
+ BOOST_FOREACH (graph_traits< ListGraph >::vertex_descriptor vertex,
+ vertices(list_graph))
+ {
+ put(get(boost::vertex_index, list_graph), vertex, index++);
+ }
- return 0;
+ test_graph(list_graph);
+ return boost::report_errors();
}
projects / ceph.git / blobdiff