1 //=======================================================================

     2 // Copyright 2001 University of Notre Dame.

     3 // Author: Andrew Janiszewski, Jeremy G. Siek

     4 //

     5 // Distributed under the Boost Software License, Version 1.0. (See

     6 // accompanying file LICENSE_1_0.txt or copy at

     7 // http://www.boost.org/LICENSE_1_0.txt)

     8 //=======================================================================

     9 

    10 #include <boost/test/minimal.hpp>

    11 #include <boost/graph/adjacency_list.hpp>

    12 #include <boost/graph/random.hpp>

    13 #include <boost/graph/graph_utility.hpp>

    14 #include <boost/graph/graph_archetypes.hpp>

    15 #include <boost/graph/breadth_first_search.hpp>

    16 

    17 #include <boost/random/mersenne_twister.hpp>

    18 #ifdef __SYMBIAN32__

    19 #include "std_log_result.h"

    20 #define LOG_FILENAME_LINE __FILE__, __LINE__

    21 #endif

    22 #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP

    23 using namespace boost;

    24 #endif

    25 

    26 template <typename DistanceMap, typename ParentMap,

    27           typename Graph, typename ColorMap>

    28 class bfs_testing_visitor

    29 {

    30   typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;

    31   typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;

    32   typedef typename boost::color_traits<

    33     typename boost::property_traits<ColorMap>::value_type

    34   > Color;

    35 public:

    36 

    37   bfs_testing_visitor(Vertex s, DistanceMap d, ParentMap p, ColorMap c)

    38     : current_distance(0), distance(d), parent(p), color(c), src(s) { }

    39 

    40   void initialize_vertex(const Vertex& u, const Graph& ) const {

    41     BOOST_CHECK(get(color, u) == Color::white());

    42   }

    43   void examine_vertex(const Vertex& u, const Graph& ) const {

    44     current_vertex = u;

    45     // Ensure that the distances monotonically increase.

    46     BOOST_CHECK( distance[u] == current_distance

    47                        || distance[u] == current_distance + 1 );

    48     if (distance[u] == current_distance + 1) // new level

    49       ++current_distance;

    50   }

    51   void discover_vertex(const Vertex& u, const Graph& ) const {

    52     BOOST_CHECK( get(color, u) == Color::gray() );

    53     if (u == src) {

    54       current_vertex = src;

    55     } else {

    56       BOOST_CHECK( parent[u] == current_vertex );

    57       BOOST_CHECK( distance[u] == current_distance + 1 );

    58       BOOST_CHECK( distance[u] == distance[parent[u]] + 1 );

    59     }

    60   }

    61   void examine_edge(const Edge& e, const Graph& g) const {

    62     BOOST_CHECK( source(e, g) == current_vertex );

    63   }

    64   void tree_edge(const Edge& e, const Graph& g) const {

    65     BOOST_CHECK( get(color, target(e, g)) == Color::white() );

    66     Vertex u = source(e, g), v = target(e, g);

    67     BOOST_CHECK( distance[u] == current_distance );

    68     parent[v] = u;

    69     distance[v] = distance[u] + 1;

    70   }

    71   void non_tree_edge(const Edge& e, const Graph& g) const {

    72     BOOST_CHECK( color[target(e, g)] != Color::white() );

    73 

    74     if (boost::is_directed(g))

    75       // cross or back edge

    76       BOOST_CHECK(distance[target(e, g)] <= distance[source(e, g)] + 1);

    77     else {

    78       // cross edge (or going backwards on a tree edge)

    79       BOOST_CHECK(distance[target(e, g)] == distance[source(e, g)]

    80                         || distance[target(e, g)] == distance[source(e, g)] + 1

    81                         || distance[target(e, g)] == distance[source(e, g)] - 1

    82                         );

    83     }

    84   }

    85 

    86   void gray_target(const Edge& e, const Graph& g) const {

    87     BOOST_CHECK( color[target(e, g)] == Color::gray() );

    88   }

    89 

    90   void black_target(const Edge& e, const Graph& g) const {

    91     BOOST_CHECK( color[target(e, g)] == Color::black() );

    92 

    93     // All vertices adjacent to a black vertex must already be discovered

    94     typename boost::graph_traits<Graph>::adjacency_iterator ai, ai_end;

    95     for (boost::tie(ai, ai_end) = adjacent_vertices(target(e, g), g);

    96          ai != ai_end; ++ai)

    97       BOOST_CHECK( color[*ai] != Color::white() );

    98   }

    99   void finish_vertex(const Vertex& u, const Graph& ) const {

   100     BOOST_CHECK( color[u] == Color::black() );

   101 

   102   }

   103 private:

   104   mutable Vertex current_vertex;

   105   mutable typename boost::property_traits<DistanceMap>::value_type

   106     current_distance;

   107   DistanceMap distance;

   108   ParentMap parent;

   109   ColorMap color;

   110   Vertex src;

   111 };

   112 

   113 

   114 template <class Graph>

   115 struct bfs_test

   116 {

   117   typedef boost::graph_traits<Graph> Traits;

   118   typedef typename Traits::vertices_size_type

   119     vertices_size_type;

   120   static void go(vertices_size_type max_V) {

   121     typedef typename Traits::vertex_descriptor vertex_descriptor;

   122     typedef boost::color_traits<boost::default_color_type> Color;

   123 

   124     vertices_size_type i;

   125     typename Traits::edges_size_type j;

   126     typename Traits::vertex_iterator ui, ui_end;

   127 

   128     boost::mt19937 gen;

   129 

   130     for (i = 0; i < max_V; ++i)

   131       for (j = 0; j < i*i; ++j) {

   132         Graph g;

   133         boost::generate_random_graph(g, i, j, gen);

   134 

   135         // declare the "start" variable

   136         vertex_descriptor start = boost::random_vertex(g, gen);

   137 

   138         // vertex properties

   139         std::vector<int> distance(i, (std::numeric_limits<int>::max)());

   140         distance[start] = 0;

   141         std::vector<vertex_descriptor> parent(i);

   142         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)

   143           parent[*ui] = *ui;

   144         std::vector<boost::default_color_type> color(i);

   145 

   146         // Create the testing visitor.

   147         bfs_testing_visitor<int*,vertex_descriptor*,Graph,

   148           boost::default_color_type*>

   149           vis(start, &distance[0], &parent[0], &color[0]);

   150 

   151         boost::breadth_first_search(g, start,

   152                                     visitor(vis).

   153                                     color_map(&color[0]));

   154 

   155         // All white vertices should be unreachable from the source.

   156         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)

   157           if (color[*ui] == Color::white()) {

   158             std::vector<boost::default_color_type> color2(i, Color::white());

   159             BOOST_CHECK(!boost::is_reachable(start, *ui, g, &color2[0]));

   160           }

   161 

   162         // The shortest path to a child should be one longer than

   163         // shortest path to the parent.

   164         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)

   165           if (parent[*ui] != *ui) // *ui not the root of the bfs tree

   166             BOOST_CHECK(distance[*ui] == distance[parent[*ui]] + 1);

   167       }

   168   }

   169 };

   170 

   171 

   172 int test_main(int argc, char* argv[])

   173 {

   174   using namespace boost;

   175   int max_V = 7;

   176   if (argc > 1)

   177     max_V = atoi(argv[1]);

   178 

   179   bfs_test< adjacency_list<vecS, vecS, directedS> >::go(max_V);

   180   bfs_test< adjacency_list<vecS, vecS, undirectedS> >::go(max_V);

   181   

   182   #ifdef __SYMBIAN32__

   183 	std_log(LOG_FILENAME_LINE,"[End Test Case ]");

   184 

   185 	testResultXml("bfs");

   186 	close_log_file();

   187 #endif

   188   return 0;

   189 }