[mlpack-git] master, mlpack-1.0.x: added code for accessing immediate child nodes (need to think of a way to rename this to be less confusing). Some more quasi-code to split nodes and insert points. (cc3671b)

gitdub at big.cc.gt.atl.ga.us gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:48:17 EST 2015


Repository : https://github.com/mlpack/mlpack

On branches: master,mlpack-1.0.x
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

>---------------------------------------------------------------

commit cc3671bdd46e689badb6968ad87e4f9ca7d7b8bf
Author: andrewmw94 <andrewmw94 at gmail.com>
Date:   Fri May 30 22:42:36 2014 +0000

    added code for accessing immediate child nodes (need to think of a way to rename this to be less confusing).  Some more quasi-code to split nodes and insert points.


>---------------------------------------------------------------

cc3671bdd46e689badb6968ad87e4f9ca7d7b8bf
 .../core/tree/rectangle_tree/r_tree_split_impl.hpp | 43 ++++++++++++++++------
 .../core/tree/rectangle_tree/rectangle_tree.hpp    | 12 ++++++
 2 files changed, 44 insertions(+), 11 deletions(-)

diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
index babd973..252080f 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
@@ -13,7 +13,7 @@ namespace mlpack {
 namespace tree {
 
 template<typename MatType>
-bool RTreeSplit<MatType>::SplitLeafNode(const RectangleTree& tree)
+void RTreeSplit<MatType>::SplitLeafNode(const RectangleTree& tree)
 {
   // Use the quadratic split method from: Guttman "R-Trees: A Dynamic Index Structure for
   // Spatial Searching"  It is simplified since we don't handle rectangles, only points.
@@ -28,7 +28,28 @@ bool RTreeSplit<MatType>::SplitLeafNode(const RectangleTree& tree)
   treeTwo.insertPoint(tree.dataset[j]);
 
   AssignPointDestNode(tree, treeOne, treeTwo, i, j);
-  return true;
+  
+  RectangleTree* par = tree.parent();
+  int index = 0;
+  for(int i = 0; i < par.numOfChildren(); i++) {
+    if(par.getChildren()[i] == this) {
+      index = i;
+      break;
+    }
+  }
+  par.getChildren()[i] = treeOne;
+  par.getChildren()[par.end++] = treeTwo;
+
+  delete tree;
+
+  // we only add one at a time, so should only need to test for equality
+  // just in case, we use an assert.
+  boost::assert(numChildren <= maxNumChildren);
+
+  if(par.numOfChildren() == par.maxNumChildren) {
+    SplitNonLeafNode(par);
+  }
+  return;
 }
 
 bool RTreeSplit<MatType>::SplitNonLeafNode(const RectangleTree& tree)
@@ -103,6 +124,7 @@ void RTreeSplit<MatType>::GetBoundSeeds(const RectangleTree& tree, int* iRet, in
   return;
 }
 
+
 void RTreeSplit<MatType>::AssignPointDestNode(
     const RectangleTree& oldTree,
     RectangleTree& treeOne,
@@ -110,13 +132,16 @@ void RTreeSplit<MatType>::AssignPointDestNode(
     const int intI,
     const int intJ)
 {
+  Log::assert(end > 1); // If this isn't true, the tree is really weird.
   int end = oldTree.count;
-  oldTree.data
-
-
-
+  oldTree.dataset.col(intI) = oldTree.dataset.col(--end); // decrement end
+  oldTree.dataset.col(intJ) = oldTree.dataset.col(--end); // decrement end
     
   int index = 0;
+
+  // In each iteration, we go through all points and find the one that causes the least
+  // increase of volume when added to one of the rectangles.  We then add it to that
+  // rectangle.  
   while() {
     int bestIndex = 0;
     double bestScore = 0;
@@ -163,11 +188,7 @@ void RTreeSplit<MatType>::AssignPointDestNode(
     else
       treeTwo.insertPoint(oldTree.dataset(bestIndex);
 
-    // I have the imaginary removePoint here.  I need to find out more about how fast doing 
-    // various things with arma::mat is before I decide how to "remove" the points from the
-    // dataset.  Make sure this is not accidentally made the function for deleting points.
-    oldTree.removePoint(index);
-    end--;
+    oldTree.dataset.col(bestIndex) = oldTree.dataset.col(--end); // decrement end.
   }
 
 
diff --git a/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp b/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
index 5f89aac..bdde1d4 100644
--- a/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
@@ -159,9 +159,21 @@ class RectangleTree
   //! Get the centroid of the node and store it in the given vector.
   void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
 
+  // TODO.  Think of a better name that makes the difference here obvious.
+
   //! Return the number of children in this node.
   size_t NumChildren() const;
 
+  //! Return the number of child nodes.  (One level beneath this one only.)
+  size_t getNumOfChildren() const { return numOfChildren; }
+  //! Modify the number of child nodes.  Be careful.
+  size_t& getNumOfChildren() { return numOfChildren; }
+
+  //! Get the children of this node.
+  const std::vector<RectangleTree*>& getChildren() const { return children; }
+  //! Modify the children of this node.
+  std::vector<RectangleTree*>& getChildren() { return children; }
+
   /**
    * Return the furthest distance to a point held in this node.  If this is not
    * a leaf node, then the distance is 0 because the node holds no points.



More information about the mlpack-git mailing list