ceph/src/boost/libs/graph/include/boost/graph/strong_components.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11
  12 #ifndef BOOST_GRAPH_STRONG_COMPONENTS_HPP
  13 #define BOOST_GRAPH_STRONG_COMPONENTS_HPP
  14
  15 #include <stack>
  16 #include <boost/config.hpp>
  17 #include <boost/graph/depth_first_search.hpp>
  18 #include <boost/type_traits/conversion_traits.hpp>
  19 #include <boost/static_assert.hpp>
  20 #include <boost/graph/overloading.hpp>
  21 #include <boost/concept/assert.hpp>
  22
  23 namespace boost {
  24
  25   //==========================================================================
  26   // This is Tarjan's algorithm for strongly connected components
  27   // from his paper "Depth first search and linear graph algorithms".
  28   // It calculates the components in a single application of DFS.
  29   // We implement the algorithm as a dfs-visitor.
  30
  31   namespace detail {
  32
  33     template <typename ComponentMap, typename RootMap, typename DiscoverTime,
  34               typename Stack>
  35     class tarjan_scc_visitor : public dfs_visitor<>
  36     {
  37       typedef typename property_traits<ComponentMap>::value_type comp_type;
  38       typedef typename property_traits<DiscoverTime>::value_type time_type;
  39     public:
  40       tarjan_scc_visitor(ComponentMap comp_map, RootMap r, DiscoverTime d,
  41                          comp_type& c_, Stack& s_)
  42         : c(c_), comp(comp_map), root(r), discover_time(d),
  43           dfs_time(time_type()), s(s_) { }
  44
  45       template <typename Graph>
  46       void discover_vertex(typename graph_traits<Graph>::vertex_descriptor v,
  47                            const Graph&) {
  48         put(root, v, v);
  49         put(comp, v, (std::numeric_limits<comp_type>::max)());
  50         put(discover_time, v, dfs_time++);
  51         s.push(v);
  52       }
  53       template <typename Graph>
  54       void finish_vertex(typename graph_traits<Graph>::vertex_descriptor v,
  55                          const Graph& g) {
  56         typename graph_traits<Graph>::vertex_descriptor w;
  57         typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
  58         for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
  59           w = target(*ei, g);
  60           if (get(comp, w) == (std::numeric_limits<comp_type>::max)())
  61             put(root, v, this->min_discover_time(get(root,v), get(root,w)));
  62         }
  63         if (get(root, v) == v) {
  64           do {
  65             w = s.top(); s.pop();
  66             put(comp, w, c);
  67             put(root, w, v);
  68           } while (w != v);
  69           ++c;
  70         }
  71       }
  72     private:
  73       template <typename Vertex>
  74       Vertex min_discover_time(Vertex u, Vertex v) {
  75         return get(discover_time, u) < get(discover_time,v) ? u : v;
  76       }
  77
  78       comp_type& c;
  79       ComponentMap comp;
  80       RootMap root;
  81       DiscoverTime discover_time;
  82       time_type dfs_time;
  83       Stack& s;
  84     };
  85
  86     template <class Graph, class ComponentMap, class RootMap,
  87               class DiscoverTime, class P, class T, class R>
  88     typename property_traits<ComponentMap>::value_type
  89     strong_components_impl
  90       (const Graph& g,    // Input
  91        ComponentMap comp, // Output
  92        // Internal record keeping
  93        RootMap root,
  94        DiscoverTime discover_time,
  95        const bgl_named_params<P, T, R>& params)
  96     {
  97       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  98       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ComponentMap, Vertex> ));
  99       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<RootMap, Vertex> ));
 100       typedef typename property_traits<RootMap>::value_type RootV;
 101       BOOST_CONCEPT_ASSERT(( ConvertibleConcept<RootV, Vertex> ));
 102       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DiscoverTime, Vertex> ));
 103
 104       typename property_traits<ComponentMap>::value_type total = 0;
 105
 106       std::stack<Vertex> s;
 107       detail::tarjan_scc_visitor<ComponentMap, RootMap, DiscoverTime,
 108         std::stack<Vertex> >
 109         vis(comp, root, discover_time, total, s);
 110       depth_first_search(g, params.visitor(vis));
 111       return total;
 112     }
 113
 114     //-------------------------------------------------------------------------
 115     // The dispatch functions handle the defaults for the rank and discover
 116     // time property maps.
 117     // dispatch with class specialization to avoid VC++ bug
 118
 119     template <class DiscoverTimeMap>
 120     struct strong_comp_dispatch2 {
 121       template <class Graph, class ComponentMap, class RootMap, class P, class T, class R>
 122       inline static typename property_traits<ComponentMap>::value_type
 123       apply(const Graph& g,
 124             ComponentMap comp,
 125             RootMap r_map,
 126             const bgl_named_params<P, T, R>& params,
 127             DiscoverTimeMap time_map)
 128       {
 129         return strong_components_impl(g, comp, r_map, time_map, params);
 130       }
 131     };
 132
 133
 134     template <>
 135     struct strong_comp_dispatch2<param_not_found> {
 136       template <class Graph, class ComponentMap, class RootMap,
 137                 class P, class T, class R>
 138       inline static typename property_traits<ComponentMap>::value_type
 139       apply(const Graph& g,
 140             ComponentMap comp,
 141             RootMap r_map,
 142             const bgl_named_params<P, T, R>& params,
 143             param_not_found)
 144       {
 145         typedef typename graph_traits<Graph>::vertices_size_type size_type;
 146         size_type       n = num_vertices(g) > 0 ? num_vertices(g) : 1;
 147         std::vector<size_type> time_vec(n);
 148         return strong_components_impl
 149           (g, comp, r_map,
 150            make_iterator_property_map(time_vec.begin(), choose_const_pmap
 151                                       (get_param(params, vertex_index),
 152                                        g, vertex_index), time_vec[0]),
 153            params);
 154       }
 155     };
 156
 157     template <class Graph, class ComponentMap, class RootMap,
 158               class P, class T, class R, class DiscoverTimeMap>
 159     inline typename property_traits<ComponentMap>::value_type
 160     scc_helper2(const Graph& g,
 161                 ComponentMap comp,
 162                 RootMap r_map,
 163                 const bgl_named_params<P, T, R>& params,
 164                 DiscoverTimeMap time_map)
 165     {
 166       return strong_comp_dispatch2<DiscoverTimeMap>::apply(g, comp, r_map, params, time_map);
 167     }
 168
 169     template <class RootMap>
 170     struct strong_comp_dispatch1 {
 171
 172       template <class Graph, class ComponentMap, class P, class T, class R>
 173       inline static typename property_traits<ComponentMap>::value_type
 174       apply(const Graph& g,
 175             ComponentMap comp,
 176             const bgl_named_params<P, T, R>& params,
 177             RootMap r_map)
 178       {
 179         return scc_helper2(g, comp, r_map, params, get_param(params, vertex_discover_time));
 180       }
 181     };
 182     template <>
 183     struct strong_comp_dispatch1<param_not_found> {
 184
 185       template <class Graph, class ComponentMap,
 186                 class P, class T, class R>
 187       inline static typename property_traits<ComponentMap>::value_type
 188       apply(const Graph& g,
 189             ComponentMap comp,
 190             const bgl_named_params<P, T, R>& params,
 191             param_not_found)
 192       {
 193         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 194         typename std::vector<Vertex>::size_type
 195           n = num_vertices(g) > 0 ? num_vertices(g) : 1;
 196         std::vector<Vertex> root_vec(n);
 197         return scc_helper2
 198           (g, comp,
 199            make_iterator_property_map(root_vec.begin(), choose_const_pmap
 200                                       (get_param(params, vertex_index),
 201                                        g, vertex_index), root_vec[0]),
 202            params,
 203            get_param(params, vertex_discover_time));
 204       }
 205     };
 206
 207     template <class Graph, class ComponentMap, class RootMap,
 208               class P, class T, class R>
 209     inline typename property_traits<ComponentMap>::value_type
 210     scc_helper1(const Graph& g,
 211                ComponentMap comp,
 212                const bgl_named_params<P, T, R>& params,
 213                RootMap r_map)
 214     {
 215       return detail::strong_comp_dispatch1<RootMap>::apply(g, comp, params,
 216                                                            r_map);
 217     }
 218
 219   } // namespace detail
 220
 221   template <class Graph, class ComponentMap,
 222             class P, class T, class R>
 223   inline typename property_traits<ComponentMap>::value_type
 224   strong_components(const Graph& g, ComponentMap comp,
 225                     const bgl_named_params<P, T, R>& params
 226                     BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
 227   {
 228     typedef typename graph_traits<Graph>::directed_category DirCat;
 229     BOOST_STATIC_ASSERT((is_convertible<DirCat*, directed_tag*>::value == true));
 230     return detail::scc_helper1(g, comp, params,
 231                                get_param(params, vertex_root_t()));
 232   }
 233
 234   template <class Graph, class ComponentMap>
 235   inline typename property_traits<ComponentMap>::value_type
 236   strong_components(const Graph& g, ComponentMap comp
 237                     BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
 238   {
 239     typedef typename graph_traits<Graph>::directed_category DirCat;
 240     BOOST_STATIC_ASSERT((is_convertible<DirCat*, directed_tag*>::value == true));
 241     bgl_named_params<int, int> params(0);
 242     return strong_components(g, comp, params);
 243   }
 244
 245   template <typename Graph, typename ComponentMap, typename ComponentLists>
 246   void build_component_lists
 247     (const Graph& g,
 248      typename graph_traits<Graph>::vertices_size_type num_scc,
 249      ComponentMap component_number,
 250      ComponentLists& components)
 251   {
 252     components.resize(num_scc);
 253     typename graph_traits<Graph>::vertex_iterator vi, vi_end;
 254     for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 255       components[component_number[*vi]].push_back(*vi);
 256   }
 257
 258
 259 } // namespace boost
 260
 261 #include <queue>
 262 #include <vector>
 263 #include <boost/graph/transpose_graph.hpp>
 264 #include <boost/pending/indirect_cmp.hpp>
 265 #include <boost/graph/connected_components.hpp> // for components_recorder
 266
 267 namespace boost {
 268
 269   //==========================================================================
 270   // This is the version of strongly connected components from
 271   // "Intro. to Algorithms" by Cormen, Leiserson, Rivest, which was
 272   // adapted from "Data Structure and Algorithms" by Aho, Hopcroft,
 273   // and Ullman, who credit the algorithm to S.R. Kosaraju and M. Sharir.
 274   // The algorithm is based on computing DFS forests the graph
 275   // and its transpose.
 276
 277   // This algorithm is slower than Tarjan's by a constant factor, uses
 278   // more memory, and puts more requirements on the graph type.
 279
 280   template <class Graph, class DFSVisitor, class ComponentsMap,
 281             class DiscoverTime, class FinishTime,
 282             class ColorMap>
 283   typename property_traits<ComponentsMap>::value_type
 284   kosaraju_strong_components(Graph& G, ComponentsMap c,
 285                              FinishTime finish_time, ColorMap color)
 286   {
 287     BOOST_CONCEPT_ASSERT(( MutableGraphConcept<Graph> ));
 288     // ...
 289
 290     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 291     typedef typename property_traits<ColorMap>::value_type ColorValue;
 292     typedef color_traits<ColorValue> Color;
 293     typename property_traits<FinishTime>::value_type time = 0;
 294     depth_first_search
 295      (G, make_dfs_visitor(stamp_times(finish_time, time, on_finish_vertex())),
 296       color);
 297
 298     Graph G_T(num_vertices(G));
 299     transpose_graph(G, G_T);
 300
 301     typedef typename property_traits<ComponentsMap>::value_type count_type;
 302
 303     count_type c_count(0);
 304     detail::components_recorder<ComponentsMap>
 305       vis(c, c_count);
 306
 307     // initialize G_T
 308     typename graph_traits<Graph>::vertex_iterator ui, ui_end;
 309     for (boost::tie(ui, ui_end) = vertices(G_T); ui != ui_end; ++ui)
 310       put(color, *ui, Color::white());
 311
 312     typedef typename property_traits<FinishTime>::value_type D;
 313     typedef indirect_cmp< FinishTime, std::less<D> > Compare;
 314
 315     Compare fl(finish_time);
 316     std::priority_queue<Vertex, std::vector<Vertex>, Compare > Q(fl);
 317
 318     typename graph_traits<Graph>::vertex_iterator i, j, iend, jend;
 319     boost::tie(i, iend) = vertices(G_T);
 320     boost::tie(j, jend) = vertices(G);
 321     for ( ; i != iend; ++i, ++j) {
 322       put(finish_time, *i, get(finish_time, *j));
 323        Q.push(*i);
 324     }
 325
 326     while ( !Q.empty() ) {
 327       Vertex u = Q.top();
 328       Q.pop();
 329       if  (get(color, u) == Color::white()) {
 330         depth_first_visit(G_T, u, vis, color);
 331         ++c_count;
 332       }
 333     }
 334     return c_count;
 335   }
 336
 337 } // namespace boost
 338
 339 #ifdef BOOST_GRAPH_USE_MPI
 340 #  include <boost/graph/distributed/strong_components.hpp>
 341 #endif
 342
 343 #endif // BOOST_GRAPH_STRONG_COMPONENTS_HPP