MeshKit  1.0
BinaryTree.hpp
Go to the documentation of this file.
00001 
00002 //  Description: Builds a binary tree from a dual graph of triangualated mesh.
00003 //  Chaman Singh Verma
00004 //  University of Wisconsin Madison, USA
00005 //  Date 15th Jan 2010
00006 //
00007 //  License: Free to distribute and modify.
00008 //
00010 
00011 #ifndef BTREE_H
00012 #define BTREE_H
00013 
00014 #include "meshkit/Mesh.hpp"
00015 #include "meshkit/DualGraph.hpp"
00016 #include "meshkit/ObjectPool.hpp"
00017 
00018 #ifdef USE_HASHMAP
00019 #include <tr1/unordered_map>
00020 #endif
00021 
00022 //#include <ext/slist>
00023 //typedef __gnu_cxx::slist<BinaryNode*> BNodeList;
00024 
00025 namespace Jaal {
00026 
00027 class BinaryNode;
00028 
00029 typedef std::list<BinaryNode*> BNodeList;
00030 
00031 class BinaryNode {
00032 public:
00033      BinaryNode()
00034      {}
00035 
00036      BinaryNode(PNode n) {
00037           dualNode = n;
00038           levelID = -1;
00039           parent = NULL;
00040      }
00041 
00042      void setLevelID(int l) {
00043           levelID = l;
00044      }
00045 
00046      int getLevelID() const {
00047           return levelID;
00048      }
00049 
00050      bool isMatched() const {
00051           return dualNode->isRemoved();
00052      }
00053 
00054      void setMatchMark(char r) {
00055           dualNode->setStatus(r);
00056      }
00057 
00058      bool isRoot() const {
00059           if (parent == NULL)
00060                return 1;
00061           return 0;
00062      }
00063 
00064      bool isLeaf() const {
00065           if (getNumChildren() == 0)
00066                return 1;
00067           return 0;
00068      }
00069 
00070      int getDegree() const {
00071           int ncount = 0;
00072           if (parent)
00073                ncount = 1;
00074           ncount += getNumChildren();
00075           return ncount;
00076      }
00077 
00078      BinaryNode * getSibling() const {
00079           if (parent) {
00080                for (int i = 0; i < parent->getNumChildren(); i++) {
00081                     BinaryNode *child = parent->getChild(i);
00082                     if (child != this)
00083                          return child;
00084                }
00085           }
00086           return NULL;
00087      }
00088 
00089      void setParent(BinaryNode * p) {
00090           parent = p;
00091      }
00092 
00093      BinaryNode * getParent() const {
00094           return parent;
00095      }
00096 
00097      int getNumChildren() const {
00098           int ncount = 0;
00099           for (size_t i = 0; i < children.size(); i++)
00100                if (children[i].active)
00101                     ncount++;
00102           return ncount;
00103      }
00104 
00105      void addChild(BinaryNode * c) {
00106           ActiveNode activenode(c);
00107           if (find(children.begin(), children.end(), activenode) == children.end())
00108                children.push_back(activenode);
00109      }
00110 
00111      void removeChild(BinaryNode * child) {
00112           ActiveNode activenode(child);
00113           vector<ActiveNode>::iterator it;
00114           it = remove(children.begin(), children.end(), activenode);
00115           children.erase(it, children.end());
00116      }
00117 
00118      void unlinkChild(BinaryNode * child) {
00119           for (size_t i = 0; i < children.size(); i++) {
00120                if (children[i].node == child) {
00121                     children[i].active = 0;
00122                     return;
00123                }
00124           }
00125      }
00126 
00127      void relinkChild(BinaryNode * child) {
00128           for (size_t i = 0; i < children.size(); i++) {
00129                if (children[i].node == child) {
00130                     children[i].active = 1;
00131                     return;
00132                }
00133           }
00134      }
00135 
00136      void relinkAll() {
00137           for (size_t i = 0; i < children.size(); i++)
00138                children[i].active = 1;
00139      }
00140 
00141      BinaryNode * getChild(int cid) const {
00142           int index = -1;
00143           for (size_t i = 0; i < children.size(); i++) {
00144                if (children[i].active) {
00145                     index++;
00146                     if (index == cid)
00147                          return children[i].node;
00148                }
00149           }
00150           return NULL;
00151      }
00152 
00153      int getID() const {
00154           return dualNode->getID();
00155      }
00156 
00157      Vertex * getDualNode() const {
00158           return dualNode;
00159      }
00160 
00161 private:
00162      struct ActiveNode {
00163           ActiveNode(BinaryNode *n) {
00164                active = 1;
00165                node = n;
00166           }
00167           bool active;
00168           bool operator ==(const ActiveNode &rhs) const {
00169                return node == rhs.node;
00170           }
00171           BinaryNode *node;
00172      };
00173      int levelID;
00174      PNode dualNode;
00175      BinaryNode* parent;
00176 
00177      vector<ActiveNode> children;
00178 };
00179 
00180 class BinaryTree {
00181 public:
00182 
00183      const static int BREADTH_FIRST_TREE = 0;
00184      const static int DEPTH_FIRST_TREE   = 1;
00185 
00186      BinaryTree(DualGraph *g) {
00187           dgraph = g;
00188           treetype = BREADTH_FIRST_TREE;
00189      }
00190 
00191      ~BinaryTree() {
00192           clear();
00193      }
00194 
00195      void setTreeType(int t) {
00196           treetype = t;
00197      }
00198 
00199      void build(BinaryNode *r = NULL);
00200 
00201      BinaryNode* getRoot() const {
00202           return root;
00203      }
00204 
00205      // Remove a given node from the tree. Unlink child and parents.
00206      //
00207      void removeNode(BinaryNode *node) {
00208           if (node) {
00209                BinaryNode *parv = node->getParent();
00210                if (parv)
00211                     parv->removeChild(node);
00212           }
00213      }
00214 
00215      void addNode(BinaryNode *tnode) {
00216           tnodemap[tnode->getDualNode()] = tnode;
00217      }
00218 
00219      void unlinkNode(BinaryNode *node) {
00220           if (node) {
00221                BinaryNode *parv = node->getParent();
00222                if (parv)
00223                     parv->unlinkChild(node);
00224           }
00225      }
00226 
00227      bool isMatched(const BinaryNode *u, const BinaryNode *v) const {
00228           Vertex *du = u->getDualNode();
00229           Vertex *dv = v->getDualNode();
00230           Vertex *umate = NULL;
00231           Vertex *vmate = NULL;
00232           du->getAttribute("DualMate", umate);
00233           dv->getAttribute("DualMate", vmate);
00234           if (umate == dv && vmate == du) return 1;
00235 /*
00236           if (du->getDualMate() == dv && dv->getDualMate() == du)
00237                return 1;
00238 */
00239           return 0;
00240      }
00241 
00242      // Give nodes at a given level. Root is at level = 0,
00243      const BNodeList &getLevelNodes(int l) const;
00244 
00245      // Total Height of the tree...
00246      int getHeight() const;
00247 
00248      // How many nodes in the tree.
00249      size_t getSize() const;
00250 
00251      // Clear all the nodes created in the tree.
00252      void clear();
00253 
00254      void deleteAll();
00255 
00256      void relinkAll();
00257 
00258      // Save the tree in GraphViz data format...
00259      void saveAs(const string &s);
00260 
00261 private:
00262      DualGraph *dgraph;
00263      BinaryNode *root;
00264      BNodeList emptylist;
00265      ObjectPool<BinaryNode> pool;
00266 
00267      int treetype;
00268 
00269 #ifdef USE_HASHMAP
00270      typedef std::tr1::unordered_map<Vertex*, BinaryNode*>  TNodeMap;
00271 #else
00272      typedef std::map<Vertex*, BinaryNode*> TNodeMap;
00273 #endif
00274      TNodeMap  tnodemap;
00275 
00276      std::map<int, BNodeList> levelnodes;
00277 
00278      void bfs_traverse(BinaryNode *parent, BNodeList &nextnodes);
00279      void bfs_traverse(BinaryNode *parent);
00280 
00281      void dfs_traverse(BinaryNode *parent);
00282      void dfs_traverse(BinaryNode *parent, BNodeList &nextnodes);
00283 };
00284 
00285 } // namespace Jaal
00286 
00287 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines