sl@0: //=======================================================================
sl@0: // Copyright 2001 University of Notre Dame.
sl@0: // Author: Andrew Janiszewski, Jeremy G. Siek
sl@0: //
sl@0: // Distributed under the Boost Software License, Version 1.0. (See
sl@0: // accompanying file LICENSE_1_0.txt or copy at
sl@0: // http://www.boost.org/LICENSE_1_0.txt)
sl@0: //=======================================================================
sl@0: 
sl@0: #include <boost/test/minimal.hpp>
sl@0: #include <boost/graph/adjacency_list.hpp>
sl@0: #include <boost/graph/random.hpp>
sl@0: #include <boost/graph/graph_utility.hpp>
sl@0: #include <boost/graph/graph_archetypes.hpp>
sl@0: #include <boost/graph/breadth_first_search.hpp>
sl@0: 
sl@0: #include <boost/random/mersenne_twister.hpp>
sl@0: #ifdef __SYMBIAN32__
sl@0: #include "std_log_result.h"
sl@0: #define LOG_FILENAME_LINE __FILE__, __LINE__
sl@0: #endif
sl@0: #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
sl@0: using namespace boost;
sl@0: #endif
sl@0: 
sl@0: template <typename DistanceMap, typename ParentMap,
sl@0:           typename Graph, typename ColorMap>
sl@0: class bfs_testing_visitor
sl@0: {
sl@0:   typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
sl@0:   typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
sl@0:   typedef typename boost::color_traits<
sl@0:     typename boost::property_traits<ColorMap>::value_type
sl@0:   > Color;
sl@0: public:
sl@0: 
sl@0:   bfs_testing_visitor(Vertex s, DistanceMap d, ParentMap p, ColorMap c)
sl@0:     : current_distance(0), distance(d), parent(p), color(c), src(s) { }
sl@0: 
sl@0:   void initialize_vertex(const Vertex& u, const Graph& ) const {
sl@0:     BOOST_CHECK(get(color, u) == Color::white());
sl@0:   }
sl@0:   void examine_vertex(const Vertex& u, const Graph& ) const {
sl@0:     current_vertex = u;
sl@0:     // Ensure that the distances monotonically increase.
sl@0:     BOOST_CHECK( distance[u] == current_distance
sl@0:                        || distance[u] == current_distance + 1 );
sl@0:     if (distance[u] == current_distance + 1) // new level
sl@0:       ++current_distance;
sl@0:   }
sl@0:   void discover_vertex(const Vertex& u, const Graph& ) const {
sl@0:     BOOST_CHECK( get(color, u) == Color::gray() );
sl@0:     if (u == src) {
sl@0:       current_vertex = src;
sl@0:     } else {
sl@0:       BOOST_CHECK( parent[u] == current_vertex );
sl@0:       BOOST_CHECK( distance[u] == current_distance + 1 );
sl@0:       BOOST_CHECK( distance[u] == distance[parent[u]] + 1 );
sl@0:     }
sl@0:   }
sl@0:   void examine_edge(const Edge& e, const Graph& g) const {
sl@0:     BOOST_CHECK( source(e, g) == current_vertex );
sl@0:   }
sl@0:   void tree_edge(const Edge& e, const Graph& g) const {
sl@0:     BOOST_CHECK( get(color, target(e, g)) == Color::white() );
sl@0:     Vertex u = source(e, g), v = target(e, g);
sl@0:     BOOST_CHECK( distance[u] == current_distance );
sl@0:     parent[v] = u;
sl@0:     distance[v] = distance[u] + 1;
sl@0:   }
sl@0:   void non_tree_edge(const Edge& e, const Graph& g) const {
sl@0:     BOOST_CHECK( color[target(e, g)] != Color::white() );
sl@0: 
sl@0:     if (boost::is_directed(g))
sl@0:       // cross or back edge
sl@0:       BOOST_CHECK(distance[target(e, g)] <= distance[source(e, g)] + 1);
sl@0:     else {
sl@0:       // cross edge (or going backwards on a tree edge)
sl@0:       BOOST_CHECK(distance[target(e, g)] == distance[source(e, g)]
sl@0:                         || distance[target(e, g)] == distance[source(e, g)] + 1
sl@0:                         || distance[target(e, g)] == distance[source(e, g)] - 1
sl@0:                         );
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   void gray_target(const Edge& e, const Graph& g) const {
sl@0:     BOOST_CHECK( color[target(e, g)] == Color::gray() );
sl@0:   }
sl@0: 
sl@0:   void black_target(const Edge& e, const Graph& g) const {
sl@0:     BOOST_CHECK( color[target(e, g)] == Color::black() );
sl@0: 
sl@0:     // All vertices adjacent to a black vertex must already be discovered
sl@0:     typename boost::graph_traits<Graph>::adjacency_iterator ai, ai_end;
sl@0:     for (boost::tie(ai, ai_end) = adjacent_vertices(target(e, g), g);
sl@0:          ai != ai_end; ++ai)
sl@0:       BOOST_CHECK( color[*ai] != Color::white() );
sl@0:   }
sl@0:   void finish_vertex(const Vertex& u, const Graph& ) const {
sl@0:     BOOST_CHECK( color[u] == Color::black() );
sl@0: 
sl@0:   }
sl@0: private:
sl@0:   mutable Vertex current_vertex;
sl@0:   mutable typename boost::property_traits<DistanceMap>::value_type
sl@0:     current_distance;
sl@0:   DistanceMap distance;
sl@0:   ParentMap parent;
sl@0:   ColorMap color;
sl@0:   Vertex src;
sl@0: };
sl@0: 
sl@0: 
sl@0: template <class Graph>
sl@0: struct bfs_test
sl@0: {
sl@0:   typedef boost::graph_traits<Graph> Traits;
sl@0:   typedef typename Traits::vertices_size_type
sl@0:     vertices_size_type;
sl@0:   static void go(vertices_size_type max_V) {
sl@0:     typedef typename Traits::vertex_descriptor vertex_descriptor;
sl@0:     typedef boost::color_traits<boost::default_color_type> Color;
sl@0: 
sl@0:     vertices_size_type i;
sl@0:     typename Traits::edges_size_type j;
sl@0:     typename Traits::vertex_iterator ui, ui_end;
sl@0: 
sl@0:     boost::mt19937 gen;
sl@0: 
sl@0:     for (i = 0; i < max_V; ++i)
sl@0:       for (j = 0; j < i*i; ++j) {
sl@0:         Graph g;
sl@0:         boost::generate_random_graph(g, i, j, gen);
sl@0: 
sl@0:         // declare the "start" variable
sl@0:         vertex_descriptor start = boost::random_vertex(g, gen);
sl@0: 
sl@0:         // vertex properties
sl@0:         std::vector<int> distance(i, (std::numeric_limits<int>::max)());
sl@0:         distance[start] = 0;
sl@0:         std::vector<vertex_descriptor> parent(i);
sl@0:         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
sl@0:           parent[*ui] = *ui;
sl@0:         std::vector<boost::default_color_type> color(i);
sl@0: 
sl@0:         // Create the testing visitor.
sl@0:         bfs_testing_visitor<int*,vertex_descriptor*,Graph,
sl@0:           boost::default_color_type*>
sl@0:           vis(start, &distance[0], &parent[0], &color[0]);
sl@0: 
sl@0:         boost::breadth_first_search(g, start,
sl@0:                                     visitor(vis).
sl@0:                                     color_map(&color[0]));
sl@0: 
sl@0:         // All white vertices should be unreachable from the source.
sl@0:         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
sl@0:           if (color[*ui] == Color::white()) {
sl@0:             std::vector<boost::default_color_type> color2(i, Color::white());
sl@0:             BOOST_CHECK(!boost::is_reachable(start, *ui, g, &color2[0]));
sl@0:           }
sl@0: 
sl@0:         // The shortest path to a child should be one longer than
sl@0:         // shortest path to the parent.
sl@0:         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
sl@0:           if (parent[*ui] != *ui) // *ui not the root of the bfs tree
sl@0:             BOOST_CHECK(distance[*ui] == distance[parent[*ui]] + 1);
sl@0:       }
sl@0:   }
sl@0: };
sl@0: 
sl@0: 
sl@0: int test_main(int argc, char* argv[])
sl@0: {
sl@0:   using namespace boost;
sl@0:   int max_V = 7;
sl@0:   if (argc > 1)
sl@0:     max_V = atoi(argv[1]);
sl@0: 
sl@0:   bfs_test< adjacency_list<vecS, vecS, directedS> >::go(max_V);
sl@0:   bfs_test< adjacency_list<vecS, vecS, undirectedS> >::go(max_V);
sl@0:   
sl@0:   #ifdef __SYMBIAN32__
sl@0: 	std_log(LOG_FILENAME_LINE,"[End Test Case ]");
sl@0: 
sl@0: 	testResultXml("bfs");
sl@0: 	close_log_file();
sl@0: #endif
sl@0:   return 0;
sl@0: }