Page 1 of 1

Making a uni-directional tree bi-directional

Posted: Tue Sep 07, 2010 9:22 am
by alex.barylski
I am trying to implement a simple function to traverse an array while doing so applying a 'root' node, so wherever I am in the tree I can determine its parent node and reverse back up the tree if needed.

The following doesn't wortk and I have a hunch it's because $array should be a static or I am missing something with references because the resulting array is huge, and root should merely reference the parent node and the result (when dumped) shouold say something like **recurive**.

Code: Select all

function tree_make_bidirectional(&$elements)
{
  $array = array();

  foreach($elements as $index => $element){
    $array['root'] = &$elements;

    if(is_array($element)){
      $array[] = tree_make_bidirectional($element);
    }
    else{
      $array[] = $element;
    }
  }

  return $array;
}
Can anyone spot anything obvious that i could be missing on this Tuesday morning? :)

Cheers,
Alex

Re: Making a uni-directional tree bi-directional

Posted: Tue Sep 07, 2010 10:43 am
by shawngoldw
PCSpectra wrote:

Code: Select all

foreach($elements as $index => $element){
    $array['root'] = &$elements;

    if(is_array($element)){
      $array[] = tree_make_bidirectional($element);
    }
    else{
      $array[] = $element;
    }
  }
I am not entirely sure of what you are trying to change in the structure of the passed in array but there is a problem here.

Each iteration you append the entire list into the new array (redundant). Then you go and add the next element to the new array (more redundancy).
Maybe you can find the solution but If you could post a simple example of an input and output, I could try to be of more help.


Shawn

Re: Making a uni-directional tree bi-directional

Posted: Tue Sep 07, 2010 11:14 am
by alex.barylski
Input:

Code: Select all

Array
(
    [0] => TEST
    [1] => Array
        (
            [0] => TEST
            [1] => TEST
            [2] => 4321
        )

    [2] => Array
        (
            [0] => TEST
            [1] => Array
                (
                    [0] => TEST
                    [1] => Array
                        (
                            [0] => TEST
                            [1] => part
                            [2] => 
                        )

                    [2] => Array
                        (
                            [0] => TEST
                            [1] => TEST
                            [2] => 1234
                        )
                )
        )
)
Desired Output:

Code: Select all

Array
(
    ['root'] => **recursive**
    [0] => TEST
    [1] => Array
        (
            ['root'] => **recursive**
            [0] => TEST
            [1] => TEST
            [2] => 4321
        )

    [2] => Array
        (
            ['root'] => **recursive**
            [0] => TEST
            [1] => Array
                (
                    ['root'] => **recursive**
                    [0] => TEST
                    [1] => Array
                        (
                            ['root'] => **recursive**
                            [0] => TEST
                            [1] => part
                            [2] => 
                        )

                    [2] => Array
                        (
                            ['root'] => **recursive**
                            [0] => TEST
                            [1] => TEST
                            [2] => 1234
                        )
                )
        )
)
I have done this before, so I am certain the array nodes can 'reference' other nodes and when you print_r() the result all referenced nodes should say **recursive** or something that that affect.

Cheers,
Alex

Re: Making a uni-directional tree bi-directional

Posted: Tue Sep 07, 2010 12:16 pm
by alex.barylski
I'm just wondering now, if whether the $temp array being recreated upon each invocation of the method...cause references do not appear to be working at all. I effectively get a cloned snapshop of all the parent items instead of a reference to only the first level up.

Cheers,
Alex

Re: Making a uni-directional tree bi-directional

Posted: Tue Sep 07, 2010 3:17 pm
by shawngoldw
I think the problem is that you are pointing to the original array, not the new one. Also, I would move the root statement outside of the loop, as it is now it just keeps giving it the same value over and over.

Shawn

Re: Making a uni-directional tree bi-directional

Posted: Tue Sep 07, 2010 3:52 pm
by alex.barylski
I've modified the code several times resulting in this:

Code: Select all

  function tree_make_bidirectional(&$nodes, &$root = null)
  {
    foreach($nodes as &$node){
      if(is_array($node)){
        tree_make_bidirectional($node, $nodes);
      }
    }

    $nodes['ROOT'] = &$root;

    return $nodes;
  }
This results in a mild epxlosion of tree data being duplicated...

Code: Select all

  function tree_make_bidirectional(&$nodes, &$root = null)
  {
    static $depth = 0;

    $nodes['ROOT'] = $depth;

    foreach($nodes as &$node){
      if(is_array($node)){
        $depth++;
        tree_make_bidirectional($node);
        $depth--;
      }
    }

    if($nodes['ROOT'] === 0){
      $nodes['ROOT'] = null;
    }
    else{
      $nodes['ROOT'] = &$nodes;
    }

    return $nodes;
  }
This snippet almost works though the references are pointing at the original which results in endless loops. I need ROOT to point to one item above that.

Cheers,
Alex

Re: Making a uni-directional tree bi-directional

Posted: Tue Sep 07, 2010 11:05 pm
by shawngoldw
PCSpectra wrote:

Code: Select all

function tree_make_bidirectional(&$elements, &$root = null)
{
  $array = array();

  $array['root'] =& $root;
  foreach($elements as $index => $element){

    if(is_array($element)){
      $array[] = tree_make_bidirectional($element, $array);
    }
    else{
      $array[] = $element;
    }
  }

  return $array;
}
I just made a couple modifications to your original one. I have not tested this at all.

In your latest post, which of those 2 is the closest to working? In both you never do this else for if the element is not an array. Maybe adding that will help. You also really should not need the static depth, there must be a better solution.


Shawn

Re: Making a uni-directional tree bi-directional

Posted: Wed Sep 08, 2010 4:33 am
by Weirdan
Something like this should work:

Code: Select all

function make_tree_bidirectional(&$tree) {
    foreach ($tree as &$elt) { // iterate by reference - important
         if (is_array($elt)) {
              $elt['root'] =& $tree;
              make_tree_bidirectional($elt);
         }
         unset($elt); // unset the reference - otherwise next iteration will destroy current element
    }
}
make_tree_bidirectional($your_tree); // note that $your_tree is modified in place - no need to return anything