123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162 |
- //=======================================================================
- // Copyright 2009 Trustees of Indiana University.
- // Authors: Michael Hansen, Andrew Lumsdaine
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <iostream>
- #include <map>
- #include <set>
- #include <boost/foreach.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/incremental_components.hpp>
- #include <boost/graph/random.hpp>
- #include <boost/lexical_cast.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <boost/random.hpp>
- #include <boost/test/minimal.hpp>
- using namespace boost;
- typedef adjacency_list<vecS, vecS, undirectedS> VectorGraph;
- 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;
- 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::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);
- 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);
- 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));
- // 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;
- }
- // Verify that components are really connected
- BOOST_FOREACH(vertices_size_type component_index,
- vertex_components) {
- std::set<vertex_descriptor> component_vertices;
- 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);
-
- } // 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) {
- // 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;
- BOOST_FOREACH(edge_descriptor child_edge,
- out_edges(child_vertex, graph)) {
- if (component_vertices.count(target(child_edge, graph)) > 0) {
- edge_exists = true;
- break;
- }
- } // foreach child_edge
- BOOST_REQUIRE(edge_exists);
- } // foreach child_vertex
- } // foreach component_index
- } // test_graph
- int test_main(int argc, char* argv[])
- {
- std::size_t vertices_to_generate = 100,
- edges_to_generate = 50,
- random_seed = time(0);
- // Parse command-line arguments
- if (argc > 1) {
- vertices_to_generate = lexical_cast<std::size_t>(argv[1]);
- }
- if (argc > 2) {
- edges_to_generate = lexical_cast<std::size_t>(argv[2]);
- }
- if (argc > 3) {
- random_seed = lexical_cast<std::size_t>(argv[3]);
- }
- minstd_rand generator(random_seed);
- // Generate random vector and list graphs
- VectorGraph vector_graph;
- generate_random_graph(vector_graph, vertices_to_generate,
- edges_to_generate, generator, false);
- test_graph(vector_graph);
- ListGraph list_graph;
- generate_random_graph(list_graph, vertices_to_generate,
- edges_to_generate, generator, false);
- // 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++);
- }
- test_graph(list_graph);
- return 0;
- }
|