Tekkotsu Homepage
Demos
Overview
Downloads
Dev. Resources
Reference
Credits

UnionFindSimple.cc

Go to the documentation of this file.
00001 #include "UnionFindSimple.h"
00002 #include <iostream>
00003 
00004 namespace AprilTags {
00005 
00006 int UnionFindSimple::getRepresentative(int thisId) {
00007   // terminal case: a node is its own parent
00008   if (data[thisId].id == thisId)
00009     return thisId;
00010 
00011   // otherwise, recurse...
00012   int root = getRepresentative(data[thisId].id);
00013 
00014   // short circuit the path
00015   data[thisId].id = root;
00016 
00017   return root;
00018 }
00019 
00020 void UnionFindSimple::printDataVector() const {
00021   for (unsigned int i = 0; i < data.size(); i++)
00022     std::cout << "data[" << i << "]: " << " id:" << data[i].id << " size:" << data[i].size << std::endl;
00023 }
00024 
00025 int UnionFindSimple::connectNodes(int aId, int bId) {
00026   int aRoot = getRepresentative(aId);
00027   int bRoot = getRepresentative(bId);
00028 
00029   if (aRoot == bRoot)
00030     return aRoot;
00031 
00032   int asz = data[aRoot].size;
00033   int bsz = data[bRoot].size;
00034 
00035   if (asz > bsz) {
00036     data[bRoot].id = aRoot;
00037     data[aRoot].size += bsz;
00038     return aRoot;
00039   } else {
00040     data[aRoot].id = bRoot;
00041     data[bRoot].size += asz;
00042     return bRoot;
00043   }
00044 }
00045 
00046 void UnionFindSimple::init() {
00047   for (unsigned int i = 0; i < data.size(); i++) {
00048     // everyone is their own cluster of size 1
00049     data[i].id = i;
00050     data[i].size = 1;
00051   }
00052 }
00053 
00054 } // namespace

Tekkotsu v5.1CVS
Generated Mon May 9 04:58:52 2016 by Doxygen 1.6.3