Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / detail / connected_components.hpp
1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9 #ifndef BOOST_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP
10 #define BOOST_GRAPH_DETAIL_CONNECTED_COMPONENTS_HPP
11
12 #if defined(__sgi) && !defined(__GNUC__)
13 #pragma set woff 1234
14 #endif
15
16 #include <boost/operators.hpp>
17
18 namespace boost {
19
20   namespace detail {
21
22     //=========================================================================
23     // Implementation details of connected_components
24
25     // This is used both in the connected_components algorithm and in
26     // the kosaraju strong components algorithm during the second DFS
27     // traversal.
28     template <class ComponentsPA, class DFSVisitor>
29     class components_recorder : public DFSVisitor
30     {
31       typedef typename property_traits<ComponentsPA>::value_type comp_type;
32     public:
33       components_recorder(ComponentsPA c, 
34                           comp_type& c_count, 
35                           DFSVisitor v)
36         : DFSVisitor(v), m_component(c), m_count(c_count) {}
37
38       template <class Vertex, class Graph>
39       void start_vertex(Vertex u, Graph& g) {
40         ++m_count;
41         DFSVisitor::start_vertex(u, g);
42       }
43       template <class Vertex, class Graph>
44       void discover_vertex(Vertex u, Graph& g) {
45         put(m_component, u, m_count);
46         DFSVisitor::discover_vertex(u, g);
47       }
48     protected:
49       ComponentsPA m_component;
50       comp_type& m_count;
51     };
52
53     template <class DiscoverTimeMap, class FinishTimeMap, class TimeT, 
54       class DFSVisitor>
55     class time_recorder : public DFSVisitor
56     {
57     public:
58       time_recorder(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor v)
59         : DFSVisitor(v), m_discover_time(d), m_finish_time(f), m_t(t) {}
60
61       template <class Vertex, class Graph>
62       void discover_vertex(Vertex u, Graph& g) {
63         put(m_discover_time, u, ++m_t);
64         DFSVisitor::discover_vertex(u, g);
65       }
66       template <class Vertex, class Graph>
67       void finish_vertex(Vertex u, Graph& g) {
68         put(m_finish_time, u, ++m_t);
69         DFSVisitor::discover_vertex(u, g);
70       }
71     protected:
72       DiscoverTimeMap m_discover_time;
73       FinishTimeMap m_finish_time;
74       TimeT m_t;
75     };
76     template <class DiscoverTimeMap, class FinishTimeMap, class TimeT, 
77       class DFSVisitor>
78     time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
79     record_times(DiscoverTimeMap d, FinishTimeMap f, TimeT& t, DFSVisitor vis)
80     {
81       return time_recorder<DiscoverTimeMap, FinishTimeMap, TimeT, DFSVisitor>
82         (d, f, t, vis);
83     }
84
85     //=========================================================================
86     // Implementation detail of dynamic_components
87
88
89     //-------------------------------------------------------------------------
90     // Helper functions for the component_index class
91     
92     // Record the representative vertices in the header array.
93     // Representative vertices now point to the component number.
94     
95     template <class Parent, class OutputIterator, class Integer>
96     inline void
97     build_components_header(Parent p, 
98                             OutputIterator header,
99                             Integer num_nodes)
100     {
101       Parent component = p;
102       Integer component_num = 0;
103       for (Integer v = 0; v != num_nodes; ++v) 
104         if (p[v] == v) {
105           *header++ = v;
106           component[v] = component_num++;
107         }
108     }
109     
110     
111     // Pushes x onto the front of the list. The list is represented in
112     // an array.
113     template <class Next, class T, class V>
114     inline void push_front(Next next, T& head, V x)
115     {
116       T tmp = head;
117       head = x;
118       next[x] = tmp;
119     }
120     
121     
122     // Create a linked list of the vertices in each component
123     // by reusing the representative array.
124     template <class Parent1, class Parent2, 
125               class Integer>
126     void
127     link_components(Parent1 component, Parent2 header, 
128                     Integer num_nodes, Integer num_components)
129     {
130       // Make the non-representative vertices point to their component
131       Parent1 representative = component;
132       for (Integer v = 0; v != num_nodes; ++v)
133         if (component[v] >= num_components || header[component[v]] != v)
134           component[v] = component[representative[v]];
135       
136       // initialize the "head" of the lists to "NULL"
137       std::fill_n(header, num_components, num_nodes);
138       
139       // Add each vertex to the linked list for its component
140       Parent1 next = component;
141       for (Integer k = 0; k != num_nodes; ++k)
142         push_front(next, header[component[k]], k);
143     }
144     
145
146     
147     template <class IndexContainer, class HeaderContainer>
148     void
149     construct_component_index(IndexContainer& index, HeaderContainer& header)
150     {
151       build_components_header(index.begin(), 
152                               std::back_inserter(header),
153                               index.end() - index.begin());
154       
155       link_components(index.begin(), header.begin(),
156                       index.end() - index.begin(), 
157                       header.end() - header.begin());
158     }
159     
160     
161     
162     template <class IndexIterator, class Integer, class Distance>
163     class component_iterator 
164       : boost::forward_iterator_helper< 
165     component_iterator<IndexIterator,Integer,Distance>,
166               Integer, Distance,Integer*, Integer&>
167     {
168     public:
169       typedef component_iterator self;
170       
171       IndexIterator next;
172       Integer node;
173       
174       typedef std::forward_iterator_tag iterator_category;
175       typedef Integer value_type;
176       typedef Integer& reference;
177       typedef Integer* pointer;
178       typedef Distance difference_type;
179       
180       component_iterator() {}
181       component_iterator(IndexIterator x, Integer i) 
182         : next(x), node(i) {}
183       Integer operator*() const {
184         return node;
185       }
186       self& operator++() {
187         node = next[node];
188         return *this;
189       }
190     };
191     
192     template <class IndexIterator, class Integer, class Distance>
193     inline bool 
194     operator==(const component_iterator<IndexIterator, Integer, Distance>& x,
195                const component_iterator<IndexIterator, Integer, Distance>& y)
196     {
197       return x.node == y.node;
198     }
199   
200   } // namespace detail
201   
202 } // namespace detail
203
204 #if defined(__sgi) && !defined(__GNUC__)
205 #pragma reset woff 1234
206 #endif
207
208 #endif