ColPack
Utilities/DisjointSets.cpp
Go to the documentation of this file.
00001 /************************************************************************************
00002     Copyright (C) 2005-2008 Assefaw H. Gebremedhin, Arijit Tarafdar, Duc Nguyen,
00003     Alex Pothen
00004 
00005     This file is part of ColPack.
00006 
00007     ColPack is free software: you can redistribute it and/or modify
00008     it under the terms of the GNU Lesser General Public License as published
00009     by the Free Software Foundation, either version 3 of the License, or
00010     (at your option) any later version.
00011 
00012     ColPack is distributed in the hope that it will be useful,
00013     but WITHOUT ANY WARRANTY; without even the implied warranty of
00014     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015     GNU Lesser General Public License for more details.
00016 
00017     You should have received a copy of the GNU Lesser General Public License
00018     along with ColPack.  If not, see <http://www.gnu.org/licenses/>.
00019 ************************************************************************************/
00020 
00021 #include <iostream>
00022 #include <vector>
00023 
00024 using namespace std;
00025 
00026 #include "Definitions.h"
00027 
00028 #include "DisjointSets.h"
00029 
00030 namespace ColPack
00031 {
00032         //Public Constructor 4251
00033         DisjointSets::DisjointSets()
00034         {
00035 
00036         }
00037 
00038         
00039         //Public Constructor 4252
00040         DisjointSets::DisjointSets(int li_SetSize)
00041         {
00042                 p_vi_Nodes.clear();
00043                 p_vi_Nodes.resize((unsigned) li_SetSize, _UNKNOWN);
00044         }
00045 
00046         
00047         //Public Destructor 4253
00048         DisjointSets::~DisjointSets()
00049         {
00050                 p_vi_Nodes.clear();
00051         }
00052 
00053         
00054         //Public Function 4254
00055         int DisjointSets::SetSize(int li_SetSize)
00056         { 
00057                 p_vi_Nodes.clear();
00058                 p_vi_Nodes.resize((unsigned) li_SetSize, _UNKNOWN);
00059 
00060                 return(_TRUE);
00061         }
00062 
00063         
00064         //Public Function 4255
00065         int DisjointSets::Count()
00066         {
00067                 int i;
00068 
00069                 int li_SetSize, li_HeadCount;
00070 
00071                 li_SetSize = (signed) p_vi_Nodes.size();
00072 
00073                 li_HeadCount = _FALSE;
00074 
00075                 for(i=0; i<li_SetSize; i++)
00076                 {
00077                         if(p_vi_Nodes[i] < _FALSE)
00078                         {
00079                                 li_HeadCount++;
00080                         }
00081                 }
00082 
00083                 return(li_HeadCount);
00084         }
00085 
00086         
00087         //Public Function 4256
00088         int DisjointSets::Print()
00089         {
00090                 int i;
00091 
00092                 int li_SetSize;
00093 
00094                 cout<<endl;
00095                 cout<<"Disjoint Sets | Tree Structure | Present State"<<endl;
00096                 cout<<endl;
00097 
00098                 li_SetSize = (signed) p_vi_Nodes.size();
00099 
00100                 for(i=0; i<li_SetSize; i++)
00101                 {
00102                         if(i == STEP_DOWN(li_SetSize))
00103                         {
00104                                 cout<<p_vi_Nodes[i]<<" ("<<li_SetSize<<")"<<endl;
00105                         }
00106                         else
00107                         {
00108                                 cout<<p_vi_Nodes[i]<<", ";
00109                         }
00110                 }
00111 
00112                 return(_TRUE);
00113         }
00114 
00115         
00116         //Public Function 4257
00117         int DisjointSets::Find(int li_Node)
00118         {
00119                 if(p_vi_Nodes[li_Node] < _FALSE)
00120                 {
00121                         return(li_Node);
00122                 }
00123                 else
00124                 {
00125                         return(Find(p_vi_Nodes[li_Node]));
00126                 }
00127         }
00128 
00129 
00130         
00131         //Public Function 4258
00132         int DisjointSets::FindAndCompress(int li_Node)
00133         {
00134                 if(p_vi_Nodes[li_Node] < _FALSE)
00135                 {
00136                         return(li_Node);
00137                 }
00138                 else
00139                 {
00140                         return(p_vi_Nodes[li_Node] = FindAndCompress(p_vi_Nodes[li_Node]));
00141                 }
00142         }
00143 
00144         /* Written by Duc Nguyen
00145         int DisjointSets::Union(int li_SetOne, int li_SetTwo)
00146         {
00147                 if(li_SetOne == li_SetTwo)
00148                 {
00149                         return(_TRUE);
00150                 }
00151 
00152                 p_vi_Nodes[li_SetTwo] = li_SetOne;
00153 
00154                 return(li_SetOne);
00155         }*/
00156 
00157         //* Written by Arijit but seem to be incorrect
00158         //Public Function 4259
00159         int DisjointSets::Union(int li_SetOne, int li_SetTwo)
00160         {
00161                 if(li_SetOne == li_SetTwo)
00162                 {
00163                         return(_TRUE);
00164                 }
00165 
00166                 p_vi_Nodes[li_SetOne] = p_vi_Nodes[li_SetTwo];
00167 
00168                 return(_TRUE);
00169         }
00170         //*/
00171 
00172         
00173         //Public Function 4260
00174         int DisjointSets::UnionByRank(int li_SetOne, int li_SetTwo)
00175         {  
00176                 if(li_SetOne == li_SetTwo)
00177                 {
00178                 return(_TRUE);
00179                 }
00180             
00181                 if(p_vi_Nodes[li_SetOne] == p_vi_Nodes[li_SetTwo])
00182                 {
00183                         p_vi_Nodes[li_SetOne]--;
00184 
00185                         p_vi_Nodes[li_SetTwo] = li_SetOne;
00186                 }
00187                 if(p_vi_Nodes[li_SetOne] < p_vi_Nodes[li_SetTwo])
00188                 {
00189                         p_vi_Nodes[li_SetTwo] = li_SetOne;
00190                 }
00191                 else
00192                 {
00193                         p_vi_Nodes[li_SetTwo] = p_vi_Nodes[li_SetOne];
00194 
00195                         p_vi_Nodes[li_SetOne] = li_SetTwo;
00196                 }
00197             
00198                 return(_TRUE);
00199         }
00200 
00201 
00202         
00203         //Public Function 4261
00204         int DisjointSets::UnionBySize(int li_SetOne, int li_SetTwo)
00205         {
00206                 if(li_SetOne == li_SetTwo)
00207                 {
00208                         return(_TRUE);
00209                 }
00210 
00211                 if(p_vi_Nodes[li_SetOne] < p_vi_Nodes[li_SetTwo])
00212                 {
00213                         p_vi_Nodes[li_SetOne] += p_vi_Nodes[li_SetTwo];
00214 
00215                         p_vi_Nodes[li_SetTwo] = li_SetOne;
00216                 }
00217                 else
00218                 {
00219                         p_vi_Nodes[li_SetTwo] += p_vi_Nodes[li_SetOne];
00220 
00221                         p_vi_Nodes[li_SetOne] = li_SetTwo;
00222 
00223                 }
00224             
00225                 return(_TRUE);
00226         }
00227 
00228 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines