123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115 |
- //=======================================================================
- // Copyright 2014 Alexander Lauser.
- // Authors: Alexander Lauser
- //
- // 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)
- //=======================================================================
- // This test is an adapted version of the MWE for Bug #10231 (showing
- // incorrect root_map computation).
- /* Output should be:
- The example graph:
- a --> b
- b --> a c
- c --> b
- Vertex a is in component 0 and has root 0
- Vertex b is in component 0 and has root 0
- Vertex c is in component 0 and has root 0
- */
- #include <boost/config.hpp>
- #include <iostream>
- #include <vector>
- #include <boost/graph/strong_components.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/graph_utility.hpp>
- int main(int, char*[])
- {
- using namespace boost;
- adjacency_list<vecS, vecS, directedS> G;
- typedef graph_traits<adjacency_list<vecS, vecS, directedS> >::vertex_descriptor Vertex;
- Vertex a = add_vertex(G);
- Vertex b = add_vertex(G);
- Vertex c = add_vertex(G);
-
- add_edge(a, b, G);
- add_edge(b, a, G);
- add_edge(c, b, G);
- add_edge(b, c, G);
- #if VERBOSE
- std::cout << "The example graph:" << std::endl;
- const char* name = "abc";
- print_graph(G, name);
- std::cout << std::endl;
- #endif
-
- std::vector<int> component(num_vertices(G)), discover_time(num_vertices(G));
- std::vector<default_color_type> color(num_vertices(G));
- std::vector<Vertex> root(num_vertices(G));
- strong_components(G, make_iterator_property_map(component.begin(), get(vertex_index, G)),
- root_map(make_iterator_property_map(root.begin(), get(vertex_index, G))).
- color_map(make_iterator_property_map(color.begin(), get(vertex_index, G))).
- discover_time_map(make_iterator_property_map(discover_time.begin(), get(vertex_index, G))));
-
- #if VERBOSE
- for (std::vector<int>::size_type i = 0; i != component.size(); ++i)
- std::cout << "Vertex " << name[i]
- << " is in component " << component[i]
- << " and has root " << root[i] << std::endl;
- #endif
-
- #if VERBOSE
- bool test_failed;
- #endif
- int ret = 0;
-
- //////////
- #if VERBOSE
- test_failed = false;
- std::cerr << "Testing component-computation of strong_components ..." << std::endl;
- #endif
- for (std::vector<int>::size_type i = 0; i != component.size(); ++i) {
- if(component[i] != 0) {
- #if VERBOSE
- test_failed = true;
- #endif
- ret = -1;
- break;
- }
- }
- #if VERBOSE
- std::cerr << (test_failed ? " **** Failed." : " Passed.") << std::endl;
- #endif
- //////////
-
- //////////
- #if VERBOSE
- test_failed = false;
- std::cerr << "Testing root_map-computation of strong_components ..." << std::endl;
- #endif
- for (std::vector<int>::size_type i = 0; i != component.size(); ++i) {
- if(root[i] != 0) {
- #if VERBOSE
- test_failed = true;
- #endif
- ret = -1;
- break;
- }
- }
- #if VERBOSE
- std::cerr << (test_failed ? " **** Failed." : " Passed.") << std::endl;
- #endif
- //////////
-
- if (ret == 0)
- std::cout << "tests passed" << std::endl;
- return ret;
- }
|