← Back to branch summary

~ubuntu-branches/ubuntu/precise/openwalnut/precise

« back to all changes in this revision

Viewing changes to src/core/common/datastructures/WUnionFind.h

  • Committer: Bazaar Package Importer
  • Author(s): Sebastian Eichelbaum
  • Date: 2011-06-21 10:26:54 UTC
  • Revision ID: james.westby@ubuntu.com-20110621102654-rq0zf436q949biih
Tags: upstream-1.2.5
Import upstream version 1.2.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/common/datastructures/WUnionFind.h
 
1
//---------------------------------------------------------------------------
 
2
//
 
3
// Project: OpenWalnut ( http://www.openwalnut.org )
 
4
//
 
5
// Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
 
6
// For more information see http://www.openwalnut.org/copying
 
7
//
 
8
// This file is part of OpenWalnut.
 
9
//
 
10
// OpenWalnut is free software: you can redistribute it and/or modify
 
11
// it under the terms of the GNU Lesser General Public License as published by
 
12
// the Free Software Foundation, either version 3 of the License, or
 
13
// (at your option) any later version.
 
14
//
 
15
// OpenWalnut is distributed in the hope that it will be useful,
 
16
// but WITHOUT ANY WARRANTY; without even the implied warranty of
 
17
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
18
// GNU Lesser General Public License for more details.
 
19
//
 
20
// You should have received a copy of the GNU Lesser General Public License
 
21
// along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
 
22
//
 
23
//---------------------------------------------------------------------------
 
24
 
 
25
#ifndef WUNIONFIND_H
 
26
#define WUNIONFIND_H
 
27
 
 
28
#include <set>
 
29
#include <vector>
 
30
 
 
31
#include <boost/shared_ptr.hpp>
 
32
 
 
33
#include "../WExportCommon.h"
 
34
/**
 
35
 * Implements a very simple union-find datastructure aka disjoint_sets.
 
36
 * \note I know there is a boost solution on that, but I didn't get it to work and I don't know how fast it is:
 
37
 * http://www.boost.org/doc/libs/1_42_0/libs/disjoint_sets/disjoint_sets.html
 
38
 *
 
39
 * And you may use it like this:
 
40
   \verbatim
 
41
   typedef std::vector< SizeType >          RankVector;
 
42
   typedef RankVector::iterator             RankRAIter;
 
43
   typedef std::vector< VertexDescriptor >  ParentVector;
 
44
   typedef ParentVector::iterator           ParentRAIter;
 
45
 
 
46
   typedef boost::iterator_property_map< RankRAIter,
 
47
                                         IndexMap,
 
48
                                         std::iterator_traits< RankRAIter >::value_type,
 
49
                                         std::iterator_traits< RankRAIter >::reference > RankMap;
 
50
 
 
51
   typedef boost::iterator_property_map< ParentRAIter,
 
52
                                         IndexMap,
 
53
                                         std::iterator_traits< ParentRAIter >::value_type,
 
54
                                         std::iterator_traits< ParentRAIter >::reference > ParentMap;
 
55
 
 
56
   RankVector   ranks( d_numOfVertices );
 
57
   ParentVector parents( d_numOfVertices );
 
58
   boost::disjoint_sets< RankMap, ParentMap > dset( boost::make_iterator_property_map( ranks.begin(),
 
59
                                                                                       boost::get( boost::vertex_index, g ),
 
60
                                                                                       ranks[0] ),
 
61
                                                    boost::make_iterator_property_map( parents.begin(),
 
62
                                                                                       boost::get( boost::vertex_index, g ),
 
63
                                                                                       parents[0] )
 
64
                                                  );
 
65
 
 
66
   // After the disjoint set dset is construct, we can use
 
67
 
 
68
   dset.make_set( u ); // make u a set
 
69
   dset.link( u, v );  // u and v are belonging to the same set.
 
70
   dset.find_set( u ); // find the set owning u. A representative of the set is returned
 
71
   \endverbatim
 
72
 */
 
73
class OWCOMMON_EXPORT WUnionFind
 
74
{
 
75
friend class WUnionFindTest;
 
76
public:
 
77
    /**
 
78
     * Creates a new union find datastructure with size elements where each
 
79
     * element is initialized as a single set.
 
80
     *
 
81
     * \param size Number of elements
 
82
     */
 
83
    explicit WUnionFind( size_t size );
 
84
 
 
85
    /**
 
86
     * Find the canonical element of the given element and do path compression
 
87
     *
 
88
     * http://en.wikipedia.org/wiki/Disjoint-set_data_structure
 
89
     *
 
90
     * depth of recursion is said to be small, therefore, recursion
 
91
     * works fine for large dataset, too.
 
92
     *
 
93
     * \throw WOutOfBounds If x is bigger than the number of elements available
 
94
     *
 
95
     * \param x The x'th element
 
96
     * \return The canonical element of that component which x is also member of
 
97
     */
 
98
    size_t find( size_t x );
 
99
 
 
100
    /**
 
101
     * Computes the set with maximum number of elements. If there are more than one candidate one is
 
102
     * picked arbitrarily.
 
103
     *
 
104
     * \return Reference to the set of indices all beloning to a set of maximal size.
 
105
     */
 
106
    boost::shared_ptr< std::set< size_t > > getMaxSet();
 
107
 
 
108
    /**
 
109
     * Merges two components (iow: makes a union) where the given elements are
 
110
     * members of.
 
111
     *
 
112
     * \throw WOutOfBounds If i or j are bigger than the number of elements available
 
113
     *
 
114
     * \param i Element of some component
 
115
     * \param j Element of some (maybe other) component
 
116
     */
 
117
    void merge( size_t i, size_t j );
 
118
 
 
119
private:
 
120
    std::vector< size_t > m_component; //!< Stores for each index its ID
 
121
};
 
122
 
 
123
 
 
124
#endif  // WUNIONFIND_H