source: NonGTP/Boost/boost/graph/detail/connected_components.hpp @ 857

Revision 857, 6.8 KB checked in by igarcia, 19 years ago (diff)
Line 
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
18namespace 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
Note: See TracBrowser for help on using the repository browser.