Making a uni-directional tree bi-directional

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Making a uni-directional tree bi-directional

Post 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
shawngoldw
Forum Contributor
Posts: 212
Joined: Mon Apr 05, 2010 3:38 pm

Re: Making a uni-directional tree bi-directional

Post 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
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Re: Making a uni-directional tree bi-directional

Post 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
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Re: Making a uni-directional tree bi-directional

Post 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
shawngoldw
Forum Contributor
Posts: 212
Joined: Mon Apr 05, 2010 3:38 pm

Re: Making a uni-directional tree bi-directional

Post 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
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Re: Making a uni-directional tree bi-directional

Post 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
shawngoldw
Forum Contributor
Posts: 212
Joined: Mon Apr 05, 2010 3:38 pm

Re: Making a uni-directional tree bi-directional

Post 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
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Re: Making a uni-directional tree bi-directional

Post 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
Post Reply