Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / biconnected_components.hpp
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
24 namespace 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 */