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

Revision 857, 4.6 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]1//=======================================================================
2// Copyright 2002 Indiana University.
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
10#ifndef BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
11#define BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
12
13#include <boost/operators.hpp>
14#include <boost/pending/disjoint_sets.hpp>
15
16namespace boost {
17
18  namespace detail {
19
20    //=========================================================================
21    // Implementation detail of incremental_components
22
23
24    //-------------------------------------------------------------------------
25    // Helper functions for the component_index class
26   
27    // Record the representative vertices in the header array.
28    // Representative vertices now point to the component number.
29   
30    template <class Parent, class OutputIterator, class Integer>
31    inline void
32    build_components_header(Parent p,
33                            OutputIterator header,
34                            Integer num_nodes)
35    {
36      Parent component = p;
37      Integer component_num = 0;
38      for (Integer v = 0; v != num_nodes; ++v)
39        if (p[v] == v) {
40          *header++ = v;
41          component[v] = component_num++;
42        }
43    }
44   
45   
46    // Pushes x onto the front of the list. The list is represented in
47    // an array.
48    template <class Next, class T, class V>
49    inline void array_push_front(Next next, T& head, V x)
50    {
51      T tmp = head;
52      head = x;
53      next[x] = tmp;
54    }
55   
56   
57    // Create a linked list of the vertices in each component
58    // by reusing the representative array.
59    template <class Parent1, class Parent2,
60              class Integer>
61    void
62    link_components(Parent1 component, Parent2 header,
63                    Integer num_nodes, Integer num_components)
64    {
65      // Make the non-representative vertices point to their component
66      Parent1 representative = component;
67      for (Integer v = 0; v != num_nodes; ++v)
68        if (component[v] >= num_components
69            || header[component[v]] != v)
70          component[v] = component[representative[v]];
71     
72      // initialize the "head" of the lists to "NULL"
73      std::fill_n(header, num_components, num_nodes);
74     
75      // Add each vertex to the linked list for its component
76      Parent1 next = component;
77      for (Integer k = 0; k != num_nodes; ++k)
78        array_push_front(next, header[component[k]], k);
79    }
80   
81
82   
83    template <class IndexContainer, class HeaderContainer>
84    void
85    construct_component_index(IndexContainer& index, HeaderContainer& header)
86    {
87      typedef typename IndexContainer::value_type Integer;
88      build_components_header(index.begin(),
89                              std::back_inserter(header),
90                              Integer(index.end() - index.begin()));
91     
92      link_components(index.begin(), header.begin(),
93                      Integer(index.end() - index.begin()),
94                      Integer(header.end() - header.begin()));
95    }
96   
97   
98   
99    template <class IndexIterator, class Integer, class Distance>
100    class component_iterator
101      : boost::forward_iterator_helper<
102    component_iterator<IndexIterator,Integer,Distance>,
103              Integer, Distance,Integer*, Integer&>
104    {
105    public:
106      typedef component_iterator self;
107     
108      IndexIterator next;
109      Integer node;
110     
111      typedef std::forward_iterator_tag iterator_category;
112      typedef Integer value_type;
113      typedef Integer& reference;
114      typedef Integer* pointer;
115      typedef Distance difference_type;
116     
117      component_iterator() {}
118      component_iterator(IndexIterator x, Integer i)
119        : next(x), node(i) {}
120      Integer operator*() const {
121        return node;
122      }
123      self& operator++() {
124        node = next[node];
125        return *this;
126      }
127    };
128   
129    template <class IndexIterator, class Integer, class Distance>
130    inline bool
131    operator==(const component_iterator<IndexIterator, Integer, Distance>& x,
132               const component_iterator<IndexIterator, Integer, Distance>& y)
133    {
134      return x.node == y.node;
135    }
136 
137  } // namespace detail
138 
139} // namespace detail
140
141#endif // BOOST_GRAPH_DETAIL_INCREMENTAL_COMPONENTS_HPP
Note: See TracBrowser for help on using the repository browser.