create a tree structure from a set of parent-child relationships

Question

I have an array of arrays which holds parent-child relationships between nodes in a graph. Each of the nested arrays is of the form

array( 0 => parent_node_id, 1 => child_node_id )

So in this array:

0 => array(
   0 => 1
   1 => 3
)

the two nodes are 1 and 3, and there is a parent-child relationship between node 1 and node 3 (the outer array index 0 is irrelevant).

1 => array(
   0 => 3
   1 => 5
),

represents a parent-child relationship between node 3 and node 5 (the 1 is irrelevant).

Here is the parent-child relationship array (note that the array index of the outer array (0, 1, 2, 3, etc.) does not represent anything):

0 => array(
   0 => 1
   1 => 3
),
1 => array(
   0 => 3
   1 => 5
),
2 => array(
   0 => 3
   1 => 7
),
3 => array(
   0 => 3
   1 => 9
),
4 => array(
   0 => 1
   1 => 10
),
5 => array(
   0 => 10
   1 => 15
)

Here is a pictorial representation of the data structure that it encodes:

And in code format (although any better ideas for an array structure that I can generate an HTML list from later would be appreciated!):

0 => array
   0 => 1
   1 => array
      0 => 3
      1 => array
         0 => 5
      2 => array
         0 => 7
      3 => array
         0 => 9
   2 => array
      0 => 10
      1 => array
         0 => 15

Using the information from this array, I would like to generate a tree that I can then use to build a menu in an html page. How can I do this using just my array of parent-child relationships?

I know there are many similar algorithms available on stack overflow, but none that works with multiple roots or the particular array input structure that I am using.

Answer 1

My contribution. There are only three kinds of elements in the array:

1. elements that are PARENT
2. elements that are PARENT and CHILD
3. elements that are CHILD

Based on those three rules, you can build a menu:

1. Loop all elements and store parents and children by number.

   result: 3 parents: 1, 3 and 10.
           6 children: 3, 5, 7, 9, 10 and 15.
   

2. Now we need to filter those results:

   2a: A LONELY CHILD is an element in children and not in parents

          result **real children**: 5, 7, 9, and 15 have no child of their own
   

   2b: Get PARENT/CHILD combinations by substracting LONLY CHILDREN from all children

          result **parent/child**: 3 and 10 have a parent and child(ren)
   

   2c: Get the OVERALL PARENT by substracting PARENT/CHILD from PARENT

          result: **real parent** is 1
   

3. Build a menu, starting with the real children, adding them to their rightfull parents and add those to the overall parent.

And in code...

$arr=array(array(1,3),array(3,5),array(3,7),array(3,9),array(1,10),array(10,15));
$menu=array(1=>'menu 1',3=>'menu 3',5=>'menu 5',7=>'menu 7',9=>'menu 9',10=>'menu 10',15=>'menu 15');


  //1. loop array and store parents and children
foreach($arr as $k=>$v){
    $P[$v[0]]=$v[0];
    $PC[$v[1]]=$v[0];
    }
  //2a: filter out the real children
$C = array_diff_key($PC,$P);
  //2b: get the parent_child combinations 
$PC=array_diff_key($PC,$C);
  //3: Get the real parent 
$P=array_diff_key($P,$PC);

 //Sorting the arrays is only needed if the starting array is not ordered
ksort($P);
ksort($PC);
ksort($C);

  //3: Building a menu
  // Create LONELY CHILDS
foreach($C as $k=>$v){
    if(!isset($MC[$v])){$MC[$v]=array();}
    $MC[$v][]='<li>'.$menu[$k].'</li>';
    }

  // Build the PARENT-CHILD menu by adding the CHILDREN to their rightfull parents
foreach($PC as $k=>$v){
    if(!isset($MPC[$v])){$MPC[$v]=array();}
    // $MPC[$v][]='<ul><li>'.$menu[$k].'</li><ul>'.implode('',$MC[$k]).'</ul></ul>'; //(OLD) 
$MPC[$v][]='<ul><li>'.$menu[$k].'<ul>'.implode('',$MC[$k]).'</ul></li></ul>';  //**NEW**
}

  // Create the REAL PARENT
foreach($P as $k=>$v){
    if(!isset($MP[$v])){$MP[$v]=array();}
    $MP[$v][]='<ul><li>'.$menu[$k].implode('',$MPC[$k]).'</li></ul>';
    }

  //CREATE FINAL MENU
$menu=array();
foreach($MP as $k=>$v){
    $menu[]=implode('',$v);
    }
//$menu='<ul>'.implode('',$menu).'</ul>'; //(OLD)
$menu=implode('',$menu);  //**NEW**

echo $menu;

The result of the above:

• menu 1
  • menu 3
    • menu 5
    • menu 7
    • menu 9
  • menu 10
    • menu 15

EDIT changed two lines to create valid HTML

And a new fiddle

Answer 2

The OP stated in a comment that this would be used to build a menu system, so I have written some code that converts the array of arrays into a more comprehensible data structure, builds a nested list (suitable for using as a menu), and populates the list items with data from a second array of $content. For the real thing, the data in $content can be a set of links or whatever is desired.

# input array
$array = array(
0 => array(
   0 => 1,
   1 => 3
),
1 => array(
   0 => 3,
   1 => 5
),
2 => array(
   0 => 3,
   1 => 7
),
3 => array(
   0 => 3,
   1 => 9
),
4 => array(
   0 => 1,
   1 => 10
),
5 => array(
   0 => 10,
   1 => 15
));

# associative array of node IDs and the node contents
# obviously for a menu, the node contents will probably be links
$content = array(
  1 => 'ape',
  3 => 'bear',
  5 => 'cow',
  7 => 'dog',
  9 => 'elephant',
  10 => 'frog',
  15 => 'giraffe'
);

$tree = [];

# simplify the parent-child 
foreach (array_values($array) as $a) {
  $tree[ $a[0] ][ $a[1] ] = 'value';
}

$roots = get_root($array);

# start our initial list...    
$str = '<ul>';
foreach (array_keys($roots) as $r) {
  $str .= build_tree( $tree, $content, $r );
}
$str .= "</ul>";
echo $str;

/**
 * build_tree($tree, $content, $n)
 * 
 * builds an html representation of a tree using $tree, a data structure
 * containing parent-child relationships, $content, the content of each
 * node of the tree, and $n, the current node in the tree. Calls itself
 * recursively when it encounters a subtree to be built
 *
 * @param array $tree 
 * @param array $content - assoc array of 
 * @param string $n - current node in the tree
 * @return string $html representing the tree
 */
function build_tree($tree, $content, $n) {
  $html = "<li>node id: $n; ".$content[$n]."</li>";
  # does $n exist in $tree -- i.e. does it have a child?
  if ( isset($tree[$n]) ) {
    # if so, start a new nested list
    $html .= '<li><ul>';
    # for each of the children of $n, our parent node,
    # run the build_tree code to create the html
    foreach (array_keys($tree[$n]) as $node) {
      $html .= build_tree($tree, $content, $node);
    }
    $html .= '</ul></li>';
  }
  return $html;
}

/**
 * get_root ( $input )
 *
 * input array format:
 * 0 => [ 0 => parent_node_id, 1 => child_node_id ],
 * 1 => [ 0 => parent_node_id2, 1 => child_node_id2 ],;
 *
 * takes an associative array of parent-child relationships
 * and makes two arrays, one containing all the parent nodes,
 * and one containing the child nodes. The root nodes are
 * those that appear in the parent node array but not the
 * child node array.
 *
 * @param array $input 
 * @return array $r - assoc arr. with root nodes as keys
 */
function get_root ($input) {
  $p = [];
  $c = [];
  $r = [];
  foreach ($input as $k => $v) {
    $p[ $v[0] ] = 1; # parent node
    $c[ $v[1] ] = 1; # child node
  }
  # find the array items in $p that aren't in $c
  foreach ($p as $k => $v) {
    if (! isset($c[$k]) ) {
      $r[$k] = 1;
    }
  }
  return $r;
}

Results of the above code (test it using this online demo):

• Node ID: 1; content: ape
• • Node ID: 3; content: bear
  • • Node ID: 5; content: cow
    • Node ID: 7; content: dog
    • Node ID: 9; content: elephant
  • Node ID: 10; content: frog
  • • Node ID: 15; content: giraffe

The raw HTML (run through HTML tidy):

<ul>
    <li>Node ID: 1; content: ape</li>
    <li>
      <ul>
        <li>Node ID: 3; content: bear</li>
        <li>
          <ul>
            <li>Node ID: 5; content: cow</li>
            <li>Node ID: 7; content: dog</li>
            <li>Node ID: 9; content: elephant</li>
          </ul>
        </li>
        <li>Node ID: 10; content: frog</li>
        <li>
          <ul>
            <li>Node ID: 15; content: giraffe</li>
          </ul>
        </li>
      </ul>
    </li>
</ul>