Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

disjoint-set.cpp

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2006 Pedro Felzenszwalb
00003  * 
00004  * This program is free software; you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation; either version 2 of the License, or
00007  * (at your option) any later version.
00008  * 
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  * 
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
00017 */
00018 
00019 /*
00020  * 05/27/2007
00021  * Edited by pthoren@cs.uml.edu:
00022  * This code is from the original disjoint-set.h file.
00023  * Formating to my own crazy standards.
00024  */
00025 
00026 #include <disjoint-set.h>
00027 
00028 /* ------------------------------------------------------------------------ */
00029 int universe::size(int x) const 
00030 { 
00031     return elts[x].size; 
00032 }
00033 
00034 /* ------------------------------------------------------------------------ */
00035 int universe::num_sets() const 
00036 { 
00037     return num; 
00038 }
00039 
00040 /* ------------------------------------------------------------------------ */
00041 universe::universe( int elements ) 
00042 {
00043     elts = new uni_elt[elements];
00044     num = elements;
00045     for (int i = 0; i < elements; i++) 
00046     {
00047         elts[i].rank = 0;
00048         elts[i].size = 1;
00049         elts[i].p = i;
00050     }
00051 }
00052 
00053 /* ------------------------------------------------------------------------ */
00054 universe::~universe() 
00055 {
00056     delete [] elts;
00057 }
00058 
00059 /* ------------------------------------------------------------------------ */
00060 int universe::find(int x) 
00061 {
00062     int y = x;
00063     while (y != elts[y].p)
00064         y = elts[y].p;
00065     elts[x].p = y;
00066     return y;
00067 }
00068 
00069 /* ------------------------------------------------------------------------ */
00070 void universe::join(int x, int y) 
00071 {
00072     if (elts[x].rank > elts[y].rank) 
00073     {
00074         elts[y].p = x;
00075         elts[x].size += elts[y].size;
00076     }
00077     else 
00078     {
00079         elts[x].p = y;
00080         elts[y].size += elts[x].size;
00081         if (elts[x].rank == elts[y].rank)
00082             elts[y].rank++;
00083     }
00084     num--;
00085 }
00086 




Copyright (C) 2002 - 2007 Philip D.S. Thoren ( pthoren@users.sourceforge.net )
University Of Massachusetts at Lowell
Robotics Lab
SourceForge.net Logo

Generated on Sat Jun 16 02:44:05 2007 for phission by  doxygen 1.4.4