libs/graph/test/dfs.cpp

   1 //=======================================================================
   2 // Copyright 2001 University of Notre Dame.
   3 // Author: 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/config.hpp>
  11 #include <boost/test/minimal.hpp>
  12 #include <stdlib.h>
  13
  14 #include <boost/graph/depth_first_search.hpp>
  15 #include <boost/graph/adjacency_list.hpp>
  16 #include <boost/graph/graph_archetypes.hpp>
  17 #include <boost/graph/graph_utility.hpp>
  18 #include <boost/graph/random.hpp>
  19
  20 #include <boost/random/mersenne_twister.hpp>
  21
  22 template <typename ColorMap, typename ParentMap,
  23   typename DiscoverTimeMap, typename FinishTimeMap>
  24 class dfs_test_visitor {
  25   typedef typename boost::property_traits<ColorMap>::value_type ColorValue;
  26   typedef typename boost::color_traits<ColorValue> Color;
  27 public:
  28   dfs_test_visitor(ColorMap color, ParentMap p, DiscoverTimeMap d,
  29                    FinishTimeMap f)
  30     : m_color(color), m_parent(p),
  31     m_discover_time(d), m_finish_time(f), m_time(0) { }
  32
  33   template <class Vertex, class Graph>
  34   void initialize_vertex(Vertex u, Graph&) {
  35     BOOST_CHECK( boost::get(m_color, u) == Color::white() );
  36   }
  37   template <class Vertex, class Graph>
  38   void start_vertex(Vertex u, Graph&) {
  39     BOOST_CHECK( boost::get(m_color, u) == Color::white() );
  40   }
  41   template <class Vertex, class Graph>
  42   void discover_vertex(Vertex u, Graph&) {
  43     using namespace boost;
  44     BOOST_CHECK( get(m_color, u) == Color::gray() );
  45     BOOST_CHECK( get(m_color, get(m_parent, u)) == Color::gray() );
  46
  47     put(m_discover_time, u, m_time++);
  48   }
  49   template <class Edge, class Graph>
  50   void examine_edge(Edge e, Graph& g) {
  51     using namespace boost;
  52     BOOST_CHECK( get(m_color, source(e, g)) == Color::gray() );
  53   }
  54   template <class Edge, class Graph>
  55   void tree_edge(Edge e, Graph& g) {
  56     using namespace boost;
  57     BOOST_CHECK( get(m_color, target(e, g)) == Color::white() );
  58
  59     put(m_parent, target(e, g), source(e, g));
  60   }
  61   template <class Edge, class Graph>
  62   void back_edge(Edge e, Graph& g) {
  63     using namespace boost;
  64     BOOST_CHECK( get(m_color, target(e, g)) == Color::gray() );
  65   }
  66   template <class Edge, class Graph>
  67   void forward_or_cross_edge(Edge e, Graph& g) {
  68     using namespace boost;
  69     BOOST_CHECK( get(m_color, target(e, g)) == Color::black() );
  70   }
  71   template <class Edge, class Graph>
  72   void finish_edge(Edge e, Graph& g) {
  73     using namespace boost;
  74     BOOST_CHECK( get(m_color, target(e, g)) == Color::gray() ||
  75                  get(m_color, target(e, g)) == Color::black() );
  76   }
  77   template <class Vertex, class Graph>
  78   void finish_vertex(Vertex u, Graph&) {
  79     using namespace boost;
  80     BOOST_CHECK( get(m_color, u) == Color::black() );
  81
  82     put(m_finish_time, u, m_time++);
  83   }
  84 private:
  85   ColorMap m_color;
  86   ParentMap m_parent;
  87   DiscoverTimeMap m_discover_time;
  88   FinishTimeMap m_finish_time;
  89   typename boost::property_traits<DiscoverTimeMap>::value_type m_time;
  90 };
  91
  92 template <typename Graph>
  93 struct dfs_test
  94 {
  95   typedef boost::graph_traits<Graph> Traits;
  96   typedef typename Traits::vertices_size_type
  97     vertices_size_type;
  98
  99   static void go(vertices_size_type max_V) {
 100     using namespace boost;
 101     typedef typename Traits::vertex_descriptor vertex_descriptor;
 102     typedef typename boost::property_map<Graph,
 103       boost::vertex_color_t>::type ColorMap;
 104     typedef typename boost::property_traits<ColorMap>::value_type ColorValue;
 105     typedef typename boost::color_traits<ColorValue> Color;
 106
 107     vertices_size_type i, k;
 108     typename Traits::edges_size_type j;
 109     typename Traits::vertex_iterator vi, vi_end, ui, ui_end;
 110
 111     boost::mt19937 gen;
 112
 113     for (i = 0; i < max_V; ++i)
 114       for (j = 0; j < i*i; ++j) {
 115         Graph g;
 116         generate_random_graph(g, i, j, gen);
 117
 118         ColorMap color = get(boost::vertex_color, g);
 119         std::vector<vertex_descriptor> parent(num_vertices(g));
 120         for (k = 0; k < num_vertices(g); ++k)
 121           parent[k] = k;
 122         std::vector<int> discover_time(num_vertices(g)),
 123           finish_time(num_vertices(g));
 124
 125         // Get vertex index map
 126         typedef typename boost::property_map<Graph, boost::vertex_index_t>::const_type idx_type;
 127         idx_type idx = get(boost::vertex_index, g);
 128
 129         typedef
 130           boost::iterator_property_map<typename std::vector<vertex_descriptor>::iterator, idx_type>
 131           parent_pm_type;
 132         parent_pm_type parent_pm(parent.begin(), idx);
 133         typedef
 134           boost::iterator_property_map<std::vector<int>::iterator, idx_type>
 135           time_pm_type;
 136         time_pm_type discover_time_pm(discover_time.begin(), idx);
 137         time_pm_type finish_time_pm(finish_time.begin(), idx);
 138
 139         dfs_test_visitor<ColorMap, parent_pm_type,
 140           time_pm_type, time_pm_type>
 141           vis(color, parent_pm,
 142               discover_time_pm, finish_time_pm);
 143
 144         boost::depth_first_search(g, visitor(vis).color_map(color));
 145
 146         // all vertices should be black
 147         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 148           BOOST_CHECK(get(color, *vi) == Color::black());
 149
 150         // check parenthesis structure of discover/finish times
 151         // See CLR p.480
 152         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
 153           for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
 154             vertex_descriptor u = *ui, v = *vi;
 155             if (u != v) {
 156               BOOST_CHECK( finish_time[u] < discover_time[v]
 157                           || finish_time[v] < discover_time[u]
 158                           || (discover_time[v] < discover_time[u]
 159                                && finish_time[u] < finish_time[v]
 160                                && boost::is_descendant(u, v, parent_pm))
 161                           || (discover_time[u] < discover_time[v]
 162                                && finish_time[v] < finish_time[u]
 163                                && boost::is_descendant(v, u, parent_pm))
 164                         );
 165             }
 166           }
 167       }
 168
 169   }
 170 };
 171
 172
 173 // usage: dfs.exe [max-vertices=15]
 174
 175 int test_main(int argc, char* argv[])
 176 {
 177   int max_V = 7;
 178   if (argc > 1)
 179     max_V = atoi(argv[1]);
 180
 181   // Test directed graphs.
 182   dfs_test< boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
 183            boost::property<boost::vertex_color_t, boost::default_color_type> >
 184     >::go(max_V);
 185   // Test undirected graphs.
 186   dfs_test< boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
 187            boost::property<boost::vertex_color_t, boost::default_color_type> >
 188     >::go(max_V);
 189
 190   return 0;
 191 }
 192