Finding adjacent nodes in a tree

Question

I'm developing a structure that is like a binary tree but generalized across dimensions so you can set whether it is a binary tree, quadtree, octree, etc by setting the dimension parameter during initialization.

Here is the definition of it:

template <uint Dimension, typename StateType>
class NDTree {
public:
    std::array<NDTree*, cexp::pow(2, Dimension)> * nodes;
    NDTree * parent;
    StateType state;
    char position; //position in parents node list
    bool leaf;

    NDTree const &operator[](const int i) const
    {
        return (*(*nodes)[i]);
    }

    NDTree &operator[](const int i)
    {
        return (*(*nodes)[i]);
    }
}

So, to initialize it- I set a dimension and then subdivide. I am going for a quadtree of depth 2 for illustration here:

const uint Dimension = 2;
NDTree<Dimension, char> tree;
tree.subdivide();

for(int i=0; i<tree.size(); i++)
    tree[i].subdivide();

for(int y=0; y<cexp::pow(2, Dimension); y++) {
    for(int x=0; x<cexp::pow(2, Dimension); x++) {
        tree[y][x].state = ((y)*10)+(x);
    }
}
std::cout << tree << std::endl;

This will result in a quadtree, the state of each of the values are initialized to [0-4][0-4].

([{0}{1}{2}{3}][{10}{11}{12}{13}][{20}{21}{22}{23}][{30}{31}{32}{33}])

I am having trouble finding adjacent nodes from any piece. What it needs to do is take a direction and then (if necessary) traverse up the tree if the direction goes off of the edge of the nodes parent (e.g. if we were on the bottom right of the quadtree square and we needed to get the piece to the right of it). My algorithm returns bogus values.

Here is how the arrays are laid out:

And here are the structures necessary to know for it:

This just holds the direction for items.

enum orientation : signed int {LEFT = -1, CENTER = 0, RIGHT = 1};

This holds a direction and whether or not to go deeper.

template <uint Dimension>
struct TraversalHelper {
    std::array<orientation, Dimension> way;
    bool deeper;
};

node_orientation_table holds the orientations in the structure. So in 2d, 0 0 refers to the top left square (or left left square). [[LEFT, LEFT], [RIGHT, LEFT], [LEFT, RIGHT], [RIGHT, RIGHT]]

And the function getPositionFromOrientation would take LEFT, LEFT and return 0. It is just basically the opposite of the node_orientation_table above.

TraversalHelper<Dimension> traverse(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
    TraversalHelper<Dimension> depth;

    for(uint d=0; d < Dimension; ++d) {
        switch(dir[d]) {
            case CENTER:
                depth.way[d] = CENTER;
                goto cont;

            case LEFT:
                if(cmp[d] == RIGHT) {
                    depth.way[d] = LEFT;
                } else {
                    depth.way[d] = RIGHT;
                    depth.deeper = true;
                }
                break;

            case RIGHT:
                if(cmp[d] == LEFT) {
                    depth.way[d] = RIGHT;
                } else {
                    depth.way[d] = LEFT;
                    depth.deeper = true;
                }
                break;
        }

        cont:
            continue;
    }

    return depth;
}

std::array<orientation, Dimension> uncenter(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
    std::array<orientation, Dimension> way;

    for(uint d=0; d < Dimension; ++d)
        way[d] = (dir[d] == CENTER) ? cmp[d] : dir[d];

    return way;
}

NDTree * getAdjacentNode(const std::array<orientation, Dimension> direction) const
{
    //our first traversal pass
    TraversalHelper<Dimension> pass = traverse(direction, node_orientation_table[position]);

    //if we are lucky the direction results in one of our siblings
    if(!pass.deeper)
        return (*(*parent).nodes)[getPositionFromOrientation<Dimension>(pass.way)];


    std::vector<std::array<orientation, Dimension>> up;   //holds our directions for going up the tree
    std::vector<std::array<orientation, Dimension>> down; //holds our directions for going down
    NDTree<Dimension, StateType> * tp = parent;           //tp is our tree pointer
    up.push_back(pass.way); //initialize with our first pass we did above

    while(true) {
        //continue going up as long as it takes, baby
        pass = traverse(up.back(), node_orientation_table[tp->position]);
        std::cout << pass.way << " :: " << uncenter(pass.way, node_orientation_table[tp->position]) << std::endl;

        if(!pass.deeper) //we've reached necessary top
            break;
        up.push_back(pass.way);

        //if we don't have any parent we must explode upwards
        if(tp->parent == nullptr)
            tp->reverseBirth(tp->position);

        tp = tp->parent;
    }

    //line break ups and downs
    std::cout << std::endl;

    //traverse upwards combining the matrices to get our actual position in cube
    tp = const_cast<NDTree *>(this);
    for(int i=1; i<up.size(); i++) {
        std::cout << up[i] << " :: " << uncenter(up[i], node_orientation_table[tp->position]) << std::endl;
        down.push_back(uncenter(up[i], node_orientation_table[tp->parent->position]));
        tp = tp->parent;
    }

    //make our way back down (tp is still set to upmost parent from above)
    for(const auto & i : down) {
        int pos = 0; //we need to get the position from an orientation list

        for(int d=0; d<i.size(); d++)
            if(i[d] == RIGHT)
                pos += cexp::pow(2, d); //consider left as 0 and right as 1 << dimension

        //grab the child of treepointer via position we just calculated
        tp = (*(*tp).nodes)[pos];
    }

    return tp;
}

For an example of this:

std::array<orientation, Dimension> direction;
direction[0] = LEFT; //x
direction[1] = CENTER; //y

NDTree<Dimension> * result = tree[3][0]->getAdjacentNode(direction);

This should grab the top right square within bottom left square, e.g. tree[2][1] which would have a value of 21 if we read its state. Which works since my last edit (algorithm is modified). Still, however, many queries do not return correct results.

//Should return tree[3][1], instead it gives back tree[2][3]
NDTree<Dimension, char> * result = tree[1][2].getAdjacentNode({ RIGHT, RIGHT });

//Should return tree[1][3], instead it gives back tree[0][3]
NDTree<Dimension, char> * result = tree[3][0].getAdjacentNode({ RIGHT, LEFT });

There are more examples of incorrect behavior such as tree[0][0](LEFT, LEFT), but many others work correctly.

Here is the folder of the git repo I am working from with this. Just run g++ -std=c++11 main.cpp from that directory if it is necessary.

Answer 1

here is one property you can try to exploit: consider just the 4 nodes:

 00  01
 10  11

Any node can have up to 4 neighbor nodes; two will exist in the same structure (larger square) and you have to look for the other two in neighboring structures. Let's focus on identifying the neighbors which are in the same structure: the neighbors for 00 are 01 and 10; the neighbors for 11 are 01 and 10. Notice that only one bit differs between neighbor nodes and that neighbors can be classified in horizontal and vertical. SO

     00 - 01    00 - 01    //horizontal neighbors
     |               |
     10              11    //vertical neighbors

Notice how flipping the MSB gets the vertical neighbor and flipping the LSB gets the horizontal node? Let's have a close look:

   MSB:  0 -> 1 gets the node directly below
         1 -> 0 sets the node directly above

   LSB:  0 -> 1 gets the node to the right
         1 -> 0 gets the node to the left

So now we can determine the node's in each direction assuming they exist in the same substructure. What about the node to the left of 00 or above 10?? According to the logic so far if you want a horizontal neighbor you should flip the LSB; but flipping it would retrieve 10 ( the node to the right). So let's add a new rule, for impossible operations:

   you can't go left for  x0 , 
   you can't go right for x1,
   you can't go up for    0x,
   you can't go down for  1x

*impossible operations refers to operations within the same structure. Let's look at the bigger picture which are the up and left neighbors for 00? if we go left for 00 of strucutre 0 (S0), we should end up with 01 of(S1), and if we go up we end up with node 10 of S(2). Notice that they are basically the same horizontal/ veritical neighbor values form S(0) only they are in different structures. So basically if we figure out how to jump from one structure to another we have an algorithm. Let's go back to our example: going up from node 00 (S0). We should end up in S2; so again 00->10 flipping the MSB. So if we apply the same algorithm we use within the structure we should be fine.

Bottom line: valid transition within a strucutres

MSB 0, go down
  1, go up
LSB 0, go right
  1, go left

for invalid transitions (like MSB 0, go up)
determine the neighbor structure by flipping the MSB for vertical and LSB for vertical
and get the neighbor you are looking for by transforming a illegal move in structure A
into a legal one in strucutre B-> S0: MSB 0 up, becomes S2:MSB 0 down.   

I hope this idea is explicit enough

Answer 2

Check out this answer for neighbor search in octrees: https://stackoverflow.com/a/21513573/3146587. Basically, you need to record in the nodes the traversal from the root to the node and manipulate this information to generate the required traversal to reach the adjacent nodes.

Answer 3

The simplest answer I can think of is to get back your node from the root of your tree.

Each cell can be assigned a coordinate mapping to the deepest nodes of your tree. In your example, the (x,y) coordinates would range from 0 to 2^dimension-1 i.e. 0 to 3.

First, compute the coordinate of the neighbour with whatever algorithm you like (for instance, decide if a right move off the edge should wrap to the 1st cell of the same row, go down to the next row or stay in place).

Then, feed the new coordinates to your regular search function. It will return the neighbour cell in dimension steps.

You can optimize that by looking at the binary value of the coordinates. Basically, the rank of the most significant bit of difference tells you how many levels up you should go.

For instance, let's take a quadtree of depth 4. Coordinates range from 0 to 15.

Assume we go left from cell number 5 (0101b). The new coordinate is 4 (0100b). The most significant bit changed is bit 0, which means you can find the neighbour in the current block.

Now if you go right, the new coordinate is 6 (0110b), so the change is affecting bit 1, which means you have to go up one level to access your cell.

All this being said, the computation time and volume of code needed to use such tricks seems hardly worth the effort to me.