source: NonGTP/Boost/boost/graph/strong_components.hpp @ 857

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