← Back to branch summary

~ubuntu-branches/ubuntu/precise/deal.ii/precise

« back to all changes in this revision

Viewing changes to contrib/boost/include/boost/graph/detail/incremental_components.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam C. Powell, IV
  • Date: 2009-05-08 23:13:50 UTC
  • Revision ID: james.westby@ubuntu.com-20090508231350-rrh1ltgi0tifabwc
Tags: upstream-6.2.0
Import upstream version 6.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/boost/include/boost/graph/detail/incremental_components.hpp
 
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
 
 
16
namespace 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