← Back to branch summary

~twpol/dcplusplus/trunk

« back to all changes in this revision

Viewing changes to boost/boost/graph/incremental_components.hpp

  • Committer: James Ross
  • Date: 2010-07-05 00:03:18 UTC
  • mfrom: (1524.1.650 dcplusplus)
  • Revision ID: silver@warwickcompsoc.co.uk-20100705000318-awwqm8ocpp5m47yz
Merged to trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
boost/boost/graph/incremental_components.hpp
1
 
//
2
 
//=======================================================================
3
 
// Copyright 1997-2001 University of Notre Dame.
4
 
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5
 
//
6
 
// Distributed under the Boost Software License, Version 1.0. (See
7
 
// accompanying file LICENSE_1_0.txt or copy at
8
 
// http://www.boost.org/LICENSE_1_0.txt)
9
 
//=======================================================================
10
 
//
11
 
 
12
 
#ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
13
 
#define BOOST_INCREMENTAL_COMPONENTS_HPP
14
 
 
15
 
#include <boost/detail/iterator.hpp>
16
 
#include <boost/graph/detail/incremental_components.hpp>
17
 
 
18
 
namespace boost {
19
 
 
20
 
  // A connected component algorithm for the case when dynamically
21
 
  // adding (but not removing) edges is common.  The
22
 
  // incremental_components() function is a preparing operation. Call
23
 
  // same_component to check whether two vertices are in the same
24
 
  // component, or use disjoint_set::find_set to determine the
25
 
  // representative for a vertex.
26
 
 
27
 
  // This version of connected components does not require a full
28
 
  // Graph. Instead, it just needs an edge list, where the vertices of
29
 
  // each edge need to be of integer type. The edges are assumed to
30
 
  // be undirected. The other difference is that the result is stored in
31
 
  // a container, instead of just a decorator.  The container should be
32
 
  // empty before the algorithm is called. It will grow during the
33
 
  // course of the algorithm. The container must be a model of
34
 
  // BackInsertionSequence and RandomAccessContainer
35
 
  // (std::vector is a good choice). After running the algorithm the
36
 
  // index container will map each vertex to the representative
37
 
  // vertex of the component to which it belongs.
38
 
  //
39
 
  // Adapted from an implementation by Alex Stepanov. The disjoint
40
 
  // sets data structure is from Tarjan's "Data Structures and Network
41
 
  // Algorithms", and the application to connected components is
42
 
  // similar to the algorithm described in Ch. 22 of "Intro to
43
 
  // Algorithms" by Cormen, et. all.
44
 
  //  
45
 
  // RankContainer is a random accessable container (operator[] is
46
 
  // defined) with a value type that can represent an integer part of
47
 
  // a binary log of the value type of the corresponding
48
 
  // ParentContainer (char is always enough) its size_type is no less
49
 
  // than the size_type of the corresponding ParentContainer
50
 
 
51
 
  // An implementation of disjoint sets can be found in
52
 
  // boost/pending/disjoint_sets.hpp
53
 
  
54
 
  template <class EdgeListGraph, class DisjointSets>
55
 
  void incremental_components(EdgeListGraph& g, DisjointSets& ds)
56
 
  {
57
 
    typename graph_traits<EdgeListGraph>::edge_iterator e, end;
58
 
    for (tie(e,end) = edges(g); e != end; ++e)
59
 
      ds.union_set(source(*e,g),target(*e,g));
60
 
  }
61
 
  
62
 
  template <class ParentIterator>
63
 
  void compress_components(ParentIterator first, ParentIterator last)
64
 
  {
65
 
    for (ParentIterator current = first; current != last; ++current) 
66
 
      detail::find_representative_with_full_compression(first, current-first);
67
 
  }
68
 
  
69
 
  template <class ParentIterator>
70
 
  typename boost::detail::iterator_traits<ParentIterator>::difference_type
71
 
  component_count(ParentIterator first, ParentIterator last)
72
 
  {
73
 
    std::ptrdiff_t count = 0;
74
 
    for (ParentIterator current = first; current != last; ++current) 
75
 
      if (*current == current - first) ++count; 
76
 
    return count;
77
 
  }
78
 
  
79
 
  // This algorithm can be applied to the result container of the
80
 
  // connected_components algorithm to normalize
81
 
  // the components.
82
 
  template <class ParentIterator>
83
 
  void normalize_components(ParentIterator first, ParentIterator last)
84
 
  {
85
 
    for (ParentIterator current = first; current != last; ++current) 
86
 
      detail::normalize_node(first, current - first);
87
 
  }
88
 
  
89
 
  template <class VertexListGraph, class DisjointSets> 
90
 
  void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
91
 
  {
92
 
    typename graph_traits<VertexListGraph>
93
 
      ::vertex_iterator v, vend;
94
 
    for (tie(v, vend) = vertices(G); v != vend; ++v)
95
 
      ds.make_set(*v);
96
 
  }
97
 
 
98
 
  template <class Vertex, class DisjointSet>
99
 
  inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
100
 
  {
101
 
    return ds.find_set(u) == ds.find_set(v);
102
 
  }
103
 
 
104
 
  // considering changing the so that it initializes with a pair of
105
 
  // vertex iterators and a parent PA.
106
 
  
107
 
  template <class IndexT>
108
 
  class component_index
109
 
  {
110
 
  public://protected: (avoid friends for now)
111
 
    typedef std::vector<IndexT> MyIndexContainer;
112
 
    MyIndexContainer header;
113
 
    MyIndexContainer index;
114
 
    typedef typename MyIndexContainer::size_type SizeT;
115
 
    typedef typename MyIndexContainer::const_iterator IndexIter;
116
 
  public:
117
 
    typedef detail::component_iterator<IndexIter, IndexT, SizeT> 
118
 
      component_iterator;
119
 
    class component {
120
 
      friend class component_index;
121
 
    protected:
122
 
      IndexT number;
123
 
      const component_index<IndexT>* comp_ind_ptr;
124
 
      component(IndexT i, const component_index<IndexT>* p) 
125
 
        : number(i), comp_ind_ptr(p) {}
126
 
    public:
127
 
      typedef component_iterator iterator;
128
 
      typedef component_iterator const_iterator;
129
 
      typedef IndexT value_type;
130
 
      iterator begin() const {
131
 
        return iterator( comp_ind_ptr->index.begin(),
132
 
                         (comp_ind_ptr->header)[number] );
133
 
      }
134
 
      iterator end() const {
135
 
        return iterator( comp_ind_ptr->index.begin(), 
136
 
                         comp_ind_ptr->index.size() );
137
 
      }
138
 
    };
139
 
    typedef SizeT size_type;
140
 
    typedef component value_type;
141
 
    
142
 
#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
143
 
    template <class Iterator>
144
 
    component_index(Iterator first, Iterator last) 
145
 
    : index(std::distance(first, last))
146
 
    { 
147
 
      std::copy(first, last, index.begin());
148
 
      detail::construct_component_index(index, header);
149
 
    }
150
 
#else
151
 
    template <class Iterator>
152
 
    component_index(Iterator first, Iterator last) 
153
 
      : index(first, last)
154
 
    { 
155
 
      detail::construct_component_index(index, header);
156
 
    }
157
 
#endif
158
 
 
159
 
    component operator[](IndexT i) const {
160
 
      return component(i, this);
161
 
    }
162
 
    SizeT size() const {
163
 
      return header.size();
164
 
    }
165
 
    
166
 
  };
167
 
 
168
 
} // namespace boost
169
 
 
170
 
#endif // BOOST_INCREMENTAL_COMPONENTS_HPP
 
1
//
 
2
//=======================================================================
 
3
// Copyright 1997-2001 University of Notre Dame.
 
4
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
 
5
//
 
6
// Distributed under the Boost Software License, Version 1.0. (See
 
7
// accompanying file LICENSE_1_0.txt or copy at
 
8
// http://www.boost.org/LICENSE_1_0.txt)
 
9
//=======================================================================
 
10
//
 
11
 
 
12
#ifndef BOOST_INCREMENTAL_COMPONENTS_HPP
 
13
#define BOOST_INCREMENTAL_COMPONENTS_HPP
 
14
 
 
15
#include <boost/detail/iterator.hpp>
 
16
#include <boost/graph/detail/incremental_components.hpp>
 
17
 
 
18
namespace boost {
 
19
 
 
20
  // A connected component algorithm for the case when dynamically
 
21
  // adding (but not removing) edges is common.  The
 
22
  // incremental_components() function is a preparing operation. Call
 
23
  // same_component to check whether two vertices are in the same
 
24
  // component, or use disjoint_set::find_set to determine the
 
25
  // representative for a vertex.
 
26
 
 
27
  // This version of connected components does not require a full
 
28
  // Graph. Instead, it just needs an edge list, where the vertices of
 
29
  // each edge need to be of integer type. The edges are assumed to
 
30
  // be undirected. The other difference is that the result is stored in
 
31
  // a container, instead of just a decorator.  The container should be
 
32
  // empty before the algorithm is called. It will grow during the
 
33
  // course of the algorithm. The container must be a model of
 
34
  // BackInsertionSequence and RandomAccessContainer
 
35
  // (std::vector is a good choice). After running the algorithm the
 
36
  // index container will map each vertex to the representative
 
37
  // vertex of the component to which it belongs.
 
38
  //
 
39
  // Adapted from an implementation by Alex Stepanov. The disjoint
 
40
  // sets data structure is from Tarjan's "Data Structures and Network
 
41
  // Algorithms", and the application to connected components is
 
42
  // similar to the algorithm described in Ch. 22 of "Intro to
 
43
  // Algorithms" by Cormen, et. all.
 
44
  //  
 
45
  // RankContainer is a random accessable container (operator[] is
 
46
  // defined) with a value type that can represent an integer part of
 
47
  // a binary log of the value type of the corresponding
 
48
  // ParentContainer (char is always enough) its size_type is no less
 
49
  // than the size_type of the corresponding ParentContainer
 
50
 
 
51
  // An implementation of disjoint sets can be found in
 
52
  // boost/pending/disjoint_sets.hpp
 
53
  
 
54
  template <class EdgeListGraph, class DisjointSets>
 
55
  void incremental_components(EdgeListGraph& g, DisjointSets& ds)
 
56
  {
 
57
    typename graph_traits<EdgeListGraph>::edge_iterator e, end;
 
58
    for (tie(e,end) = edges(g); e != end; ++e)
 
59
      ds.union_set(source(*e,g),target(*e,g));
 
60
  }
 
61
  
 
62
  template <class ParentIterator>
 
63
  void compress_components(ParentIterator first, ParentIterator last)
 
64
  {
 
65
    for (ParentIterator current = first; current != last; ++current) 
 
66
      detail::find_representative_with_full_compression(first, current-first);
 
67
  }
 
68
  
 
69
  template <class ParentIterator>
 
70
  typename boost::detail::iterator_traits<ParentIterator>::difference_type
 
71
  component_count(ParentIterator first, ParentIterator last)
 
72
  {
 
73
    std::ptrdiff_t count = 0;
 
74
    for (ParentIterator current = first; current != last; ++current) 
 
75
      if (*current == current - first) ++count; 
 
76
    return count;
 
77
  }
 
78
  
 
79
  // This algorithm can be applied to the result container of the
 
80
  // connected_components algorithm to normalize
 
81
  // the components.
 
82
  template <class ParentIterator>
 
83
  void normalize_components(ParentIterator first, ParentIterator last)
 
84
  {
 
85
    for (ParentIterator current = first; current != last; ++current) 
 
86
      detail::normalize_node(first, current - first);
 
87
  }
 
88
  
 
89
  template <class VertexListGraph, class DisjointSets> 
 
90
  void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)
 
91
  {
 
92
    typename graph_traits<VertexListGraph>
 
93
      ::vertex_iterator v, vend;
 
94
    for (tie(v, vend) = vertices(G); v != vend; ++v)
 
95
      ds.make_set(*v);
 
96
  }
 
97
 
 
98
  template <class Vertex, class DisjointSet>
 
99
  inline bool same_component(Vertex u, Vertex v, DisjointSet& ds)
 
100
  {
 
101
    return ds.find_set(u) == ds.find_set(v);
 
102
  }
 
103
 
 
104
  // considering changing the so that it initializes with a pair of
 
105
  // vertex iterators and a parent PA.
 
106
  
 
107
  template <class IndexT>
 
108
  class component_index
 
109
  {
 
110
  public://protected: (avoid friends for now)
 
111
    typedef std::vector<IndexT> MyIndexContainer;
 
112
    MyIndexContainer header;
 
113
    MyIndexContainer index;
 
114
    typedef typename MyIndexContainer::size_type SizeT;
 
115
    typedef typename MyIndexContainer::const_iterator IndexIter;
 
116
  public:
 
117
    typedef detail::component_iterator<IndexIter, IndexT, SizeT> 
 
118
      component_iterator;
 
119
    class component {
 
120
      friend class component_index;
 
121
    protected:
 
122
      IndexT number;
 
123
      const component_index<IndexT>* comp_ind_ptr;
 
124
      component(IndexT i, const component_index<IndexT>* p) 
 
125
        : number(i), comp_ind_ptr(p) {}
 
126
    public:
 
127
      typedef component_iterator iterator;
 
128
      typedef component_iterator const_iterator;
 
129
      typedef IndexT value_type;
 
130
      iterator begin() const {
 
131
        return iterator( comp_ind_ptr->index.begin(),
 
132
                         (comp_ind_ptr->header)[number] );
 
133
      }
 
134
      iterator end() const {
 
135
        return iterator( comp_ind_ptr->index.begin(), 
 
136
                         comp_ind_ptr->index.size() );
 
137
      }
 
138
    };
 
139
    typedef SizeT size_type;
 
140
    typedef component value_type;
 
141
    
 
142
#if defined(BOOST_NO_TEMPLATED_ITERATOR_CONSTRUCTORS)
 
143
    template <class Iterator>
 
144
    component_index(Iterator first, Iterator last) 
 
145
    : index(std::distance(first, last))
 
146
    { 
 
147
      std::copy(first, last, index.begin());
 
148
      detail::construct_component_index(index, header);
 
149
    }
 
150
#else
 
151
    template <class Iterator>
 
152
    component_index(Iterator first, Iterator last) 
 
153
      : index(first, last)
 
154
    { 
 
155
      detail::construct_component_index(index, header);
 
156
    }
 
157
#endif
 
158
 
 
159
    component operator[](IndexT i) const {
 
160
      return component(i, this);
 
161
    }
 
162
    SizeT size() const {
 
163
      return header.size();
 
164
    }
 
165
    
 
166
  };
 
167
 
 
168
} // namespace boost
 
169
 
 
170
#endif // BOOST_INCREMENTAL_COMPONENTS_HPP