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

Revision 857, 8.9 KB checked in by igarcia, 18 years ago (diff)
Line 
1// Copyright (c) Jeremy Siek 2001
2// Copyright (c) Douglas Gregor 2004
3//
4// Distributed under the Boost Software License, Version 1.0. (See
5// accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7
8// NOTE: this final is generated by libs/graph/doc/biconnected_components.w
9
10#ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
11#define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP
12
13#include <stack>
14#include <vector>
15#include <algorithm> // for std::min and std::max
16#include <boost/config.hpp>
17#include <boost/limits.hpp>
18#include <boost/graph/graph_traits.hpp>
19#include <boost/graph/graph_concepts.hpp>
20#include <boost/property_map.hpp>
21#include <boost/graph/depth_first_search.hpp>
22#include <boost/graph/graph_utility.hpp>
23
24namespace boost
25{
26  namespace detail
27  {
28    template<typename ComponentMap, typename DiscoverTimeMap,
29             typename LowPointMap, typename PredecessorMap,
30             typename OutputIterator, typename Stack>
31    struct biconnected_components_visitor : public dfs_visitor<>
32    {
33      biconnected_components_visitor
34        (ComponentMap comp, std::size_t& c, DiscoverTimeMap dtm,
35         std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred,
36         OutputIterator out, Stack& S)
37          : comp(comp), c(c), dtm(dtm), dfs_time(dfs_time), lowpt(lowpt),
38            pred(pred), out(out), S(S) { }
39
40      template <typename Vertex, typename Graph>
41      void start_vertex(const Vertex& u, Graph&)
42      {
43        put(pred, u, u);
44      }
45
46      template <typename Vertex, typename Graph>
47      void discover_vertex(const Vertex& u, Graph&)
48      {
49        put(dtm, u, ++dfs_time);
50        put(lowpt, u, get(dtm, u));
51      }
52
53      template <typename Edge, typename Graph>
54      void tree_edge(const Edge& e, Graph& g)
55      {
56        S.push(e);
57        put(pred, target(e, g), source(e, g));
58      }
59
60      template <typename Edge, typename Graph>
61      void back_edge(const Edge& e, Graph& g)
62      {
63        BOOST_USING_STD_MIN();
64
65        if ( target(e, g) != get(pred, source(e, g)) ) {
66          S.push(e);
67          put(lowpt, source(e, g),
68              min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, source(e, g)),
69                                                   get(dtm, target(e, g))));
70        }
71      }
72
73      template <typename Vertex, typename Graph>
74      void finish_vertex(const Vertex& u, Graph& g)
75      {
76        BOOST_USING_STD_MIN();
77        Vertex parent = get(pred, u);
78        bool is_art_point = false;
79        if ( get(dtm, parent) > get(dtm, u) ) {
80          parent = get(pred, parent);
81          is_art_point = true;
82        }
83
84        if ( parent == u ) { // at top
85          if ( get(dtm, u) + 1 == get(dtm, get(pred, u)) )
86            is_art_point = false;
87        } else {
88          put(lowpt, parent,
89              min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent),
90                                                   get(lowpt, u)));
91
92          if (get(lowpt, u) >= get(dtm, parent)) {
93            if ( get(dtm, parent) > get(dtm, get(pred, parent)) ) {
94              put(pred, u, get(pred, parent));
95              put(pred, parent, u);
96            }
97
98            while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) {
99              put(comp, S.top(), c);
100              S.pop();
101            }
102            put(comp, S.top(), c);
103              S.pop();
104            ++c;
105            if ( S.empty() ) {
106              put(pred, u, parent);
107              put(pred, parent, u);
108            }
109          }
110        }
111        if ( is_art_point )
112          *out++ = u;
113      }
114
115      ComponentMap comp;
116      std::size_t& c;
117      DiscoverTimeMap dtm;
118      std::size_t& dfs_time;
119      LowPointMap lowpt;
120      PredecessorMap pred;
121      OutputIterator out;
122      Stack& S;
123    };
124  } // namespace detail
125
126  template<typename Graph, typename ComponentMap, typename OutputIterator,
127           typename DiscoverTimeMap, typename LowPointMap,
128           typename PredecessorMap, typename VertexIndexMap>
129  std::pair<std::size_t, OutputIterator>
130  biconnected_components(const Graph & g, ComponentMap comp,
131                         OutputIterator out, DiscoverTimeMap discover_time,
132                         LowPointMap lowpt, PredecessorMap pred,
133                         VertexIndexMap index_map)
134  {
135    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
136    typedef typename graph_traits<Graph>::edge_descriptor edge_t;
137    function_requires<VertexListGraphConcept<Graph> >();
138    function_requires<IncidenceGraphConcept<Graph> >();
139    function_requires<WritablePropertyMapConcept<ComponentMap, edge_t> >();
140    function_requires<ReadWritePropertyMapConcept<DiscoverTimeMap,
141                                                  vertex_t> >();
142    function_requires<ReadWritePropertyMapConcept<LowPointMap, vertex_t > >();
143    function_requires<ReadWritePropertyMapConcept<PredecessorMap,
144                                                  vertex_t> >();
145
146    std::size_t num_components = 0;
147    std::size_t dfs_time = 0;
148    std::stack < edge_t > S;
149
150    detail::biconnected_components_visitor<ComponentMap, DiscoverTimeMap,
151        LowPointMap, PredecessorMap, OutputIterator, std::stack<edge_t> >
152      vis(comp, num_components, discover_time, dfs_time, lowpt, pred, out, S);
153
154    depth_first_search(g, visitor(vis).vertex_index_map(index_map));
155
156    return std::pair<std::size_t, OutputIterator>(num_components, vis.out);
157  }
158
159  template<typename Graph, typename ComponentMap, typename OutputIterator,
160           typename DiscoverTimeMap, typename LowPointMap,
161           typename VertexIndexMap>
162  std::pair<std::size_t, OutputIterator>
163  biconnected_components(const Graph & g, ComponentMap comp,
164                         OutputIterator out, DiscoverTimeMap discover_time,
165                         LowPointMap lowpt, VertexIndexMap index_map)
166  {
167    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
168    std::vector<vertex_t> pred(num_vertices(g));
169    vertex_t vert = graph_traits<Graph>::null_vertex();
170    return biconnected_components
171             (g, comp, out, discover_time, lowpt,
172              make_iterator_property_map(pred.begin(), index_map, vert),
173              index_map);
174  }
175
176  template<typename Graph, typename ComponentMap, typename OutputIterator,
177           typename VertexIndexMap>
178  std::pair<std::size_t, OutputIterator>
179  biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out,
180                         VertexIndexMap index_map)
181  {
182    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
183    typedef typename graph_traits<Graph>::vertices_size_type
184      vertices_size_type;
185
186    std::vector<vertices_size_type> discover_time(num_vertices(g));
187    std::vector<vertices_size_type> lowpt(num_vertices(g));
188
189    vertices_size_type vst(0);
190
191    return biconnected_components
192             (g, comp, out,
193              make_iterator_property_map(discover_time.begin(), index_map, vst),
194              make_iterator_property_map(lowpt.begin(), index_map, vst),
195              index_map);
196  }
197
198  template < typename Graph, typename ComponentMap, typename OutputIterator>
199  std::pair<std::size_t, OutputIterator>
200  biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out)
201  {
202    return biconnected_components(g, comp, out, get(vertex_index, g));
203  }
204
205  namespace graph_detail {
206    struct dummy_output_iterator
207    {
208      typedef std::output_iterator_tag iterator_category;
209      typedef void value_type;
210      typedef void pointer;
211      typedef void difference_type;
212
213      struct reference {
214        template<typename T>
215        reference& operator=(const T&) { return *this; }
216      };
217
218      reference operator*() const { return reference(); }
219      dummy_output_iterator& operator++() { return *this; }
220      dummy_output_iterator operator++(int) { return *this; }
221    };
222  } // end namespace graph_detail
223
224  template <typename Graph, typename ComponentMap>
225  std::size_t
226  biconnected_components(const Graph& g, ComponentMap comp)
227  {
228    return biconnected_components(g, comp,
229                                  graph_detail::dummy_output_iterator()).first;
230  }
231
232  template<typename Graph, typename OutputIterator, typename VertexIndexMap>
233  OutputIterator
234  articulation_points(const Graph& g, OutputIterator out,
235                      VertexIndexMap index_map)
236  {
237    return biconnected_components(g, dummy_property_map(), out,
238                                  index_map).second;
239  }
240
241  template<typename Graph, typename OutputIterator>
242  OutputIterator
243  articulation_points(const Graph& g, OutputIterator out)
244  {
245    return biconnected_components(g, dummy_property_map(), out,
246                                  get(vertex_index, g)).second;
247  }
248
249}                               // namespace boost
250
251#endif  /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */
Note: See TracBrowser for help on using the repository browser.