/usr/include/ColPack/DisjointSets.h is in libcolpack-dev 1.0.9-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | /************************************************************************************
Copyright (C) 2005-2008 Assefaw H. Gebremedhin, Arijit Tarafdar, Duc Nguyen,
Alex Pothen
This file is part of ColPack.
ColPack is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published
by the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
ColPack is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with ColPack. If not, see <http://www.gnu.org/licenses/>.
************************************************************************************/
#ifndef DISJOINTSETS_H
#define DISJOINTSETS_H
using namespace std;
namespace ColPack
{
/** @ingroup group4
* @brief class DisjointSets in @link group4@endlink.
The disjoint set class is used by ColPack to store and operate on disjoint sets of edges identified by
integer numbers. A disjoint set class can be instantiated by specifying the maximum number of such sets to
be stored. The elements in a set are stored as a tree and the identifier of the set (SetID) is the identifier of the root.
The size of the tree is stored in the root and the parent of an element is stored in the element. The tree is
implemented simply as a vector of integers the indices being the identifiers of the elements.
*/
class DisjointSets
{
private:
vector<int> p_vi_Nodes;
public:
//Public Constructor 4251
DisjointSets();
//Public Constructor 4252
DisjointSets(int);
//Public Destructor 4253
~DisjointSets();
//Public Function 4254
/// Set the size of this DisjointSets object, i.e. resize the vector p_vi_Nodes
int SetSize(int);
//Public Function 4255
/// Count the number of sets contained by this DisjointSets object
int Count();
//Public Function 4256
/// Print out the elements' ID and their values (i.e., p_vi_Nodes's IDs and values)
int Print();
//Public Function 4257
/// Find the Set ID of this element
int Find(int);
//Public Function 4258
/// Find the Set ID of this element, also shorten the tree by updating all elements with its new SetID
int FindAndCompress(int);
//Public Function 4259
/// Union li_SetOne with li_SetTwo by seting li_SetOne to be the parent of li_SetTwo
/**
Return the SetID of the new set. In this case, SetID will be li_SetOne
*/
int Union(int li_SetOne, int li_SetTwo);
//Public Function 4260
/// Union li_SetOne with li_SetTwo by their ranks
/**
Rank: the upper bound on the height of the tree (or set)
The root of each set will hold its the negate of its set rank
i.e. rank of set 2 is (-p_vi_Nodes[2])
Note: UnionByRank() and UnionBySize() can not be used together to solve the same
problem due to the different meaning of the root's value
*/
int UnionByRank(int li_SetOne, int li_SetTwo);
//Public Function 4261
/// Union li_SetOne with li_SetTwo by their sizes
/**
The root of each set will hold its the negate of its set size
i.e. size of set 2 is (-p_vi_Nodes[2])
Note: UnionByRank() and UnionBySize() can not be used together to solve the same
problem due to the different meaning of the root's value
*/
int UnionBySize(int li_SetOne, int li_SetTwo);
};
}
#endif
|