boost/graph/strong_components.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011
0012 #ifndef BOOST_GRAPH_STRONG_COMPONENTS_HPP
0013 #define BOOST_GRAPH_STRONG_COMPONENTS_HPP
0014
0015 #include <stack>
0016 #include <boost/config.hpp>
0017 #include <boost/graph/depth_first_search.hpp>
0018 #include <boost/type_traits/conversion_traits.hpp>
0019 #include <boost/static_assert.hpp>
0020 #include <boost/graph/overloading.hpp>
0021 #include <boost/graph/detail/mpi_include.hpp>
0022 #include <boost/concept/assert.hpp>
0023
0024 namespace boost
0025 {
0026
0027 //==========================================================================
0028 // This is Tarjan's algorithm for strongly connected components
0029 // from his paper "Depth first search and linear graph algorithms".
0030 // It calculates the components in a single application of DFS.
0031 // We implement the algorithm as a dfs-visitor.
0032
0033 namespace detail
0034 {
0035
0036     template < typename ComponentMap, typename RootMap, typename DiscoverTime,
0037         typename Stack >
0038     class tarjan_scc_visitor : public dfs_visitor<>
0039     {
0040         typedef typename property_traits< ComponentMap >::value_type comp_type;
0041         typedef typename property_traits< DiscoverTime >::value_type time_type;
0042
0043     public:
0044         tarjan_scc_visitor(ComponentMap comp_map, RootMap r, DiscoverTime d,
0045             comp_type& c_, Stack& s_)
0046         : c(c_)
0047         , comp(comp_map)
0048         , root(r)
0049         , discover_time(d)
0050         , dfs_time(time_type())
0051         , s(s_)
0052         {
0053         }
0054
0055         template < typename Graph >
0056         void discover_vertex(
0057             typename graph_traits< Graph >::vertex_descriptor v, const Graph&)
0058         {
0059             put(root, v, v);
0060             put(comp, v, (std::numeric_limits< comp_type >::max)());
0061             put(discover_time, v, dfs_time++);
0062             s.push(v);
0063         }
0064         template < typename Graph >
0065         void finish_vertex(
0066             typename graph_traits< Graph >::vertex_descriptor v, const Graph& g)
0067         {
0068             typename graph_traits< Graph >::vertex_descriptor w;
0069             typename graph_traits< Graph >::out_edge_iterator ei, ei_end;
0070             for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei)
0071             {
0072                 w = target(*ei, g);
0073                 if (get(comp, w) == (std::numeric_limits< comp_type >::max)())
0074                     put(root, v,
0075                         this->min_discover_time(get(root, v), get(root, w)));
0076             }
0077             if (get(root, v) == v)
0078             {
0079                 do
0080                 {
0081                     w = s.top();
0082                     s.pop();
0083                     put(comp, w, c);
0084                     put(root, w, v);
0085                 } while (w != v);
0086                 ++c;
0087             }
0088         }
0089
0090     private:
0091         template < typename Vertex >
0092         Vertex min_discover_time(Vertex u, Vertex v)
0093         {
0094             return get(discover_time, u) < get(discover_time, v) ? u : v;
0095         }
0096
0097         comp_type& c;
0098         ComponentMap comp;
0099         RootMap root;
0100         DiscoverTime discover_time;
0101         time_type dfs_time;
0102         Stack& s;
0103     };
0104
0105     template < class Graph, class ComponentMap, class RootMap,
0106         class DiscoverTime, class P, class T, class R >
0107     typename property_traits< ComponentMap >::value_type strong_components_impl(
0108         const Graph& g, // Input
0109         ComponentMap comp, // Output
0110         // Internal record keeping
0111         RootMap root, DiscoverTime discover_time,
0112         const bgl_named_params< P, T, R >& params)
0113     {
0114         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0115         BOOST_CONCEPT_ASSERT(
0116             (ReadWritePropertyMapConcept< ComponentMap, Vertex >));
0117         BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< RootMap, Vertex >));
0118         typedef typename property_traits< RootMap >::value_type RootV;
0119         BOOST_CONCEPT_ASSERT((ConvertibleConcept< RootV, Vertex >));
0120         BOOST_CONCEPT_ASSERT(
0121             (ReadWritePropertyMapConcept< DiscoverTime, Vertex >));
0122
0123         typename property_traits< ComponentMap >::value_type total = 0;
0124
0125         std::stack< Vertex > s;
0126         detail::tarjan_scc_visitor< ComponentMap, RootMap, DiscoverTime,
0127             std::stack< Vertex > >
0128             vis(comp, root, discover_time, total, s);
0129         depth_first_search(g, params.visitor(vis));
0130         return total;
0131     }
0132
0133     //-------------------------------------------------------------------------
0134     // The dispatch functions handle the defaults for the rank and discover
0135     // time property maps.
0136     // dispatch with class specialization to avoid VC++ bug
0137
0138     template < class DiscoverTimeMap > struct strong_comp_dispatch2
0139     {
0140         template < class Graph, class ComponentMap, class RootMap, class P,
0141             class T, class R >
0142         inline static typename property_traits< ComponentMap >::value_type
0143         apply(const Graph& g, ComponentMap comp, RootMap r_map,
0144             const bgl_named_params< P, T, R >& params, DiscoverTimeMap time_map)
0145         {
0146             return strong_components_impl(g, comp, r_map, time_map, params);
0147         }
0148     };
0149
0150     template <> struct strong_comp_dispatch2< param_not_found >
0151     {
0152         template < class Graph, class ComponentMap, class RootMap, class P,
0153             class T, class R >
0154         inline static typename property_traits< ComponentMap >::value_type
0155         apply(const Graph& g, ComponentMap comp, RootMap r_map,
0156             const bgl_named_params< P, T, R >& params, param_not_found)
0157         {
0158             typedef
0159                 typename graph_traits< Graph >::vertices_size_type size_type;
0160             size_type n = num_vertices(g) > 0 ? num_vertices(g) : 1;
0161             std::vector< size_type > time_vec(n);
0162             return strong_components_impl(g, comp, r_map,
0163                 make_iterator_property_map(time_vec.begin(),
0164                     choose_const_pmap(
0165                         get_param(params, vertex_index), g, vertex_index),
0166                     time_vec[0]),
0167                 params);
0168         }
0169     };
0170
0171     template < class Graph, class ComponentMap, class RootMap, class P, class T,
0172         class R, class DiscoverTimeMap >
0173     inline typename property_traits< ComponentMap >::value_type scc_helper2(
0174         const Graph& g, ComponentMap comp, RootMap r_map,
0175         const bgl_named_params< P, T, R >& params, DiscoverTimeMap time_map)
0176     {
0177         return strong_comp_dispatch2< DiscoverTimeMap >::apply(
0178             g, comp, r_map, params, time_map);
0179     }
0180
0181     template < class RootMap > struct strong_comp_dispatch1
0182     {
0183
0184         template < class Graph, class ComponentMap, class P, class T, class R >
0185         inline static typename property_traits< ComponentMap >::value_type
0186         apply(const Graph& g, ComponentMap comp,
0187             const bgl_named_params< P, T, R >& params, RootMap r_map)
0188         {
0189             return scc_helper2(g, comp, r_map, params,
0190                 get_param(params, vertex_discover_time));
0191         }
0192     };
0193     template <> struct strong_comp_dispatch1< param_not_found >
0194     {
0195
0196         template < class Graph, class ComponentMap, class P, class T, class R >
0197         inline static typename property_traits< ComponentMap >::value_type
0198         apply(const Graph& g, ComponentMap comp,
0199             const bgl_named_params< P, T, R >& params, param_not_found)
0200         {
0201             typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0202             typename std::vector< Vertex >::size_type n
0203                 = num_vertices(g) > 0 ? num_vertices(g) : 1;
0204             std::vector< Vertex > root_vec(n);
0205             return scc_helper2(g, comp,
0206                 make_iterator_property_map(root_vec.begin(),
0207                     choose_const_pmap(
0208                         get_param(params, vertex_index), g, vertex_index),
0209                     root_vec[0]),
0210                 params, get_param(params, vertex_discover_time));
0211         }
0212     };
0213
0214     template < class Graph, class ComponentMap, class RootMap, class P, class T,
0215         class R >
0216     inline typename property_traits< ComponentMap >::value_type scc_helper1(
0217         const Graph& g, ComponentMap comp,
0218         const bgl_named_params< P, T, R >& params, RootMap r_map)
0219     {
0220         return detail::strong_comp_dispatch1< RootMap >::apply(
0221             g, comp, params, r_map);
0222     }
0223
0224 } // namespace detail
0225
0226 template < class Graph, class ComponentMap, class P, class T, class R >
0227 inline typename property_traits< ComponentMap >::value_type strong_components(
0228     const Graph& g, ComponentMap comp,
0229     const bgl_named_params< P, T, R >& params BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0230         Graph, vertex_list_graph_tag))
0231 {
0232     typedef typename graph_traits< Graph >::directed_category DirCat;
0233     BOOST_STATIC_ASSERT(
0234         (is_convertible< DirCat*, directed_tag* >::value == true));
0235     return detail::scc_helper1(
0236         g, comp, params, get_param(params, vertex_root_t()));
0237 }
0238
0239 template < class Graph, class ComponentMap >
0240 inline typename property_traits< ComponentMap >::value_type strong_components(
0241     const Graph& g,
0242     ComponentMap comp BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0243         Graph, vertex_list_graph_tag))
0244 {
0245     typedef typename graph_traits< Graph >::directed_category DirCat;
0246     BOOST_STATIC_ASSERT(
0247         (is_convertible< DirCat*, directed_tag* >::value == true));
0248     bgl_named_params< int, int > params(0);
0249     return strong_components(g, comp, params);
0250 }
0251
0252 template < typename Graph, typename ComponentMap, typename ComponentLists >
0253 void build_component_lists(const Graph& g,
0254     typename graph_traits< Graph >::vertices_size_type num_scc,
0255     ComponentMap component_number, ComponentLists& components)
0256 {
0257     components.resize(num_scc);
0258     typename graph_traits< Graph >::vertex_iterator vi, vi_end;
0259     for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0260         components[component_number[*vi]].push_back(*vi);
0261 }
0262
0263 } // namespace boost
0264
0265 #include <queue>
0266 #include <vector>
0267 #include <boost/graph/transpose_graph.hpp>
0268 #include <boost/pending/indirect_cmp.hpp>
0269 #include <boost/graph/connected_components.hpp> // for components_recorder
0270
0271 namespace boost
0272 {
0273
0274 //==========================================================================
0275 // This is the version of strongly connected components from
0276 // "Intro. to Algorithms" by Cormen, Leiserson, Rivest, which was
0277 // adapted from "Data Structure and Algorithms" by Aho, Hopcroft,
0278 // and Ullman, who credit the algorithm to S.R. Kosaraju and M. Sharir.
0279 // The algorithm is based on computing DFS forests the graph
0280 // and its transpose.
0281
0282 // This algorithm is slower than Tarjan's by a constant factor, uses
0283 // more memory, and puts more requirements on the graph type.
0284
0285 template < class Graph, class DFSVisitor, class ComponentsMap,
0286     class DiscoverTime, class FinishTime, class ColorMap >
0287 typename property_traits< ComponentsMap >::value_type
0288 kosaraju_strong_components(
0289     Graph& G, ComponentsMap c, FinishTime finish_time, ColorMap color)
0290 {
0291     BOOST_CONCEPT_ASSERT((MutableGraphConcept< Graph >));
0292     // ...
0293
0294     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0295     typedef typename property_traits< ColorMap >::value_type ColorValue;
0296     typedef color_traits< ColorValue > Color;
0297     typename property_traits< FinishTime >::value_type time = 0;
0298     depth_first_search(G,
0299         make_dfs_visitor(stamp_times(finish_time, time, on_finish_vertex())),
0300         color);
0301
0302     Graph G_T(num_vertices(G));
0303     transpose_graph(G, G_T);
0304
0305     typedef typename property_traits< ComponentsMap >::value_type count_type;
0306
0307     count_type c_count(0);
0308     detail::components_recorder< ComponentsMap > vis(c, c_count);
0309
0310     // initialize G_T
0311     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
0312     for (boost::tie(ui, ui_end) = vertices(G_T); ui != ui_end; ++ui)
0313         put(color, *ui, Color::white());
0314
0315     typedef typename property_traits< FinishTime >::value_type D;
0316     typedef indirect_cmp< FinishTime, std::less< D > > Compare;
0317
0318     Compare fl(finish_time);
0319     std::priority_queue< Vertex, std::vector< Vertex >, Compare > Q(fl);
0320
0321     typename graph_traits< Graph >::vertex_iterator i, j, iend, jend;
0322     boost::tie(i, iend) = vertices(G_T);
0323     boost::tie(j, jend) = vertices(G);
0324     for (; i != iend; ++i, ++j)
0325     {
0326         put(finish_time, *i, get(finish_time, *j));
0327         Q.push(*i);
0328     }
0329
0330     while (!Q.empty())
0331     {
0332         Vertex u = Q.top();
0333         Q.pop();
0334         if (get(color, u) == Color::white())
0335         {
0336             depth_first_visit(G_T, u, vis, color);
0337             ++c_count;
0338         }
0339     }
0340     return c_count;
0341 }
0342
0343 } // namespace boost
0344
0345 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/strong_components.hpp>)
0346
0347 #endif // BOOST_GRAPH_STRONG_COMPONENTS_HPP