1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/stdcpp/tsrc/Boost_test/graph/src/bfs.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,189 @@
1.4 +//=======================================================================
1.5 +// Copyright 2001 University of Notre Dame.
1.6 +// Author: Andrew Janiszewski, Jeremy G. Siek
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +
1.13 +#include <boost/test/minimal.hpp>
1.14 +#include <boost/graph/adjacency_list.hpp>
1.15 +#include <boost/graph/random.hpp>
1.16 +#include <boost/graph/graph_utility.hpp>
1.17 +#include <boost/graph/graph_archetypes.hpp>
1.18 +#include <boost/graph/breadth_first_search.hpp>
1.19 +
1.20 +#include <boost/random/mersenne_twister.hpp>
1.21 +#ifdef __SYMBIAN32__
1.22 +#include "std_log_result.h"
1.23 +#define LOG_FILENAME_LINE __FILE__, __LINE__
1.24 +#endif
1.25 +#ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
1.26 +using namespace boost;
1.27 +#endif
1.28 +
1.29 +template <typename DistanceMap, typename ParentMap,
1.30 + typename Graph, typename ColorMap>
1.31 +class bfs_testing_visitor
1.32 +{
1.33 + typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
1.34 + typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
1.35 + typedef typename boost::color_traits<
1.36 + typename boost::property_traits<ColorMap>::value_type
1.37 + > Color;
1.38 +public:
1.39 +
1.40 + bfs_testing_visitor(Vertex s, DistanceMap d, ParentMap p, ColorMap c)
1.41 + : current_distance(0), distance(d), parent(p), color(c), src(s) { }
1.42 +
1.43 + void initialize_vertex(const Vertex& u, const Graph& ) const {
1.44 + BOOST_CHECK(get(color, u) == Color::white());
1.45 + }
1.46 + void examine_vertex(const Vertex& u, const Graph& ) const {
1.47 + current_vertex = u;
1.48 + // Ensure that the distances monotonically increase.
1.49 + BOOST_CHECK( distance[u] == current_distance
1.50 + || distance[u] == current_distance + 1 );
1.51 + if (distance[u] == current_distance + 1) // new level
1.52 + ++current_distance;
1.53 + }
1.54 + void discover_vertex(const Vertex& u, const Graph& ) const {
1.55 + BOOST_CHECK( get(color, u) == Color::gray() );
1.56 + if (u == src) {
1.57 + current_vertex = src;
1.58 + } else {
1.59 + BOOST_CHECK( parent[u] == current_vertex );
1.60 + BOOST_CHECK( distance[u] == current_distance + 1 );
1.61 + BOOST_CHECK( distance[u] == distance[parent[u]] + 1 );
1.62 + }
1.63 + }
1.64 + void examine_edge(const Edge& e, const Graph& g) const {
1.65 + BOOST_CHECK( source(e, g) == current_vertex );
1.66 + }
1.67 + void tree_edge(const Edge& e, const Graph& g) const {
1.68 + BOOST_CHECK( get(color, target(e, g)) == Color::white() );
1.69 + Vertex u = source(e, g), v = target(e, g);
1.70 + BOOST_CHECK( distance[u] == current_distance );
1.71 + parent[v] = u;
1.72 + distance[v] = distance[u] + 1;
1.73 + }
1.74 + void non_tree_edge(const Edge& e, const Graph& g) const {
1.75 + BOOST_CHECK( color[target(e, g)] != Color::white() );
1.76 +
1.77 + if (boost::is_directed(g))
1.78 + // cross or back edge
1.79 + BOOST_CHECK(distance[target(e, g)] <= distance[source(e, g)] + 1);
1.80 + else {
1.81 + // cross edge (or going backwards on a tree edge)
1.82 + BOOST_CHECK(distance[target(e, g)] == distance[source(e, g)]
1.83 + || distance[target(e, g)] == distance[source(e, g)] + 1
1.84 + || distance[target(e, g)] == distance[source(e, g)] - 1
1.85 + );
1.86 + }
1.87 + }
1.88 +
1.89 + void gray_target(const Edge& e, const Graph& g) const {
1.90 + BOOST_CHECK( color[target(e, g)] == Color::gray() );
1.91 + }
1.92 +
1.93 + void black_target(const Edge& e, const Graph& g) const {
1.94 + BOOST_CHECK( color[target(e, g)] == Color::black() );
1.95 +
1.96 + // All vertices adjacent to a black vertex must already be discovered
1.97 + typename boost::graph_traits<Graph>::adjacency_iterator ai, ai_end;
1.98 + for (boost::tie(ai, ai_end) = adjacent_vertices(target(e, g), g);
1.99 + ai != ai_end; ++ai)
1.100 + BOOST_CHECK( color[*ai] != Color::white() );
1.101 + }
1.102 + void finish_vertex(const Vertex& u, const Graph& ) const {
1.103 + BOOST_CHECK( color[u] == Color::black() );
1.104 +
1.105 + }
1.106 +private:
1.107 + mutable Vertex current_vertex;
1.108 + mutable typename boost::property_traits<DistanceMap>::value_type
1.109 + current_distance;
1.110 + DistanceMap distance;
1.111 + ParentMap parent;
1.112 + ColorMap color;
1.113 + Vertex src;
1.114 +};
1.115 +
1.116 +
1.117 +template <class Graph>
1.118 +struct bfs_test
1.119 +{
1.120 + typedef boost::graph_traits<Graph> Traits;
1.121 + typedef typename Traits::vertices_size_type
1.122 + vertices_size_type;
1.123 + static void go(vertices_size_type max_V) {
1.124 + typedef typename Traits::vertex_descriptor vertex_descriptor;
1.125 + typedef boost::color_traits<boost::default_color_type> Color;
1.126 +
1.127 + vertices_size_type i;
1.128 + typename Traits::edges_size_type j;
1.129 + typename Traits::vertex_iterator ui, ui_end;
1.130 +
1.131 + boost::mt19937 gen;
1.132 +
1.133 + for (i = 0; i < max_V; ++i)
1.134 + for (j = 0; j < i*i; ++j) {
1.135 + Graph g;
1.136 + boost::generate_random_graph(g, i, j, gen);
1.137 +
1.138 + // declare the "start" variable
1.139 + vertex_descriptor start = boost::random_vertex(g, gen);
1.140 +
1.141 + // vertex properties
1.142 + std::vector<int> distance(i, (std::numeric_limits<int>::max)());
1.143 + distance[start] = 0;
1.144 + std::vector<vertex_descriptor> parent(i);
1.145 + for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
1.146 + parent[*ui] = *ui;
1.147 + std::vector<boost::default_color_type> color(i);
1.148 +
1.149 + // Create the testing visitor.
1.150 + bfs_testing_visitor<int*,vertex_descriptor*,Graph,
1.151 + boost::default_color_type*>
1.152 + vis(start, &distance[0], &parent[0], &color[0]);
1.153 +
1.154 + boost::breadth_first_search(g, start,
1.155 + visitor(vis).
1.156 + color_map(&color[0]));
1.157 +
1.158 + // All white vertices should be unreachable from the source.
1.159 + for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
1.160 + if (color[*ui] == Color::white()) {
1.161 + std::vector<boost::default_color_type> color2(i, Color::white());
1.162 + BOOST_CHECK(!boost::is_reachable(start, *ui, g, &color2[0]));
1.163 + }
1.164 +
1.165 + // The shortest path to a child should be one longer than
1.166 + // shortest path to the parent.
1.167 + for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
1.168 + if (parent[*ui] != *ui) // *ui not the root of the bfs tree
1.169 + BOOST_CHECK(distance[*ui] == distance[parent[*ui]] + 1);
1.170 + }
1.171 + }
1.172 +};
1.173 +
1.174 +
1.175 +int test_main(int argc, char* argv[])
1.176 +{
1.177 + using namespace boost;
1.178 + int max_V = 7;
1.179 + if (argc > 1)
1.180 + max_V = atoi(argv[1]);
1.181 +
1.182 + bfs_test< adjacency_list<vecS, vecS, directedS> >::go(max_V);
1.183 + bfs_test< adjacency_list<vecS, vecS, undirectedS> >::go(max_V);
1.184 +
1.185 + #ifdef __SYMBIAN32__
1.186 + std_log(LOG_FILENAME_LINE,"[End Test Case ]");
1.187 +
1.188 + testResultXml("bfs");
1.189 + close_log_file();
1.190 +#endif
1.191 + return 0;
1.192 +}