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