disjoint-set.h
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 #ifndef DISJOINT_SET
00020 #define DISJOINT_SET
00021 
00022 // disjoint-set forests using union-by-rank and path compression (sort of).
00023 
00024 typedef struct {
00025   int rank;
00026   int p;
00027   int size;
00028 } uni_elt;
00029 
00030 class universe {
00031 public:
00032   universe(int elements);
00033   ~universe();
00034   int find(int x);  
00035   void join(int x, int y);
00036   int size(int x) const { return elts[x].size; }
00037   int num_sets() const { return num; }
00038 
00039 private:
00040   uni_elt *elts;
00041   int num;
00042 };
00043 
00044 universe::universe(int elements) {
00045   elts = new uni_elt[elements];
00046   num = elements;
00047   for (int i = 0; i < elements; i++) {
00048     elts[i].rank = 0;
00049     elts[i].size = 1;
00050     elts[i].p = i;
00051   }
00052 }
00053   
00054 universe::~universe() {
00055   delete [] elts;
00056 }
00057 
00058 int universe::find(int x) {
00059   int y = x;
00060   while (y != elts[y].p)
00061     y = elts[y].p;
00062   elts[x].p = y;
00063   return y;
00064 }
00065 
00066 void universe::join(int x, int y) {
00067   if (elts[x].rank > elts[y].rank) {
00068     elts[y].p = x;
00069     elts[x].size += elts[y].size;
00070   } else {
00071     elts[x].p = y;
00072     elts[y].size += elts[x].size;
00073     if (elts[x].rank == elts[y].rank)
00074       elts[y].rank++;
00075   }
00076   num--;
00077 }
00078 
00079 #endif


iri_leaf_segmentation
Author(s): Sergi Foix
autogenerated on Fri Dec 6 2013 20:27:23