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

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

i have array of arrays holds parent-child relationships between nodes in graph. each of nested arrays of form

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

so in array:

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

the 2 nodes 1 , 3, , there parent-child relationship between node 1 , node 3 (the outer array index 0 irrelevant).

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

represents parent-child relationship between node 3 , node 5 (the 1 irrelevant).

here parent-child relationship array (note array index of outer array (0, 1, 2, 3, etc.) 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 pictorial representation of info construction encodes:

and in code format (although improve ideas array construction can generate html list later 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 info array, generate tree can utilize build menu in html page. how can using array of parent-child relationships?

i know there many similar algorithms available on stack overflow, none works multiple roots or particular array input construction using.

my contribution. there 3 kinds of elements in array:

elements parent elements parent , child elements child

based on 3 rules, can build menu:

loop elements , store parents , children number.

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

now need filter results:

2a: lonely kid element in children , not in parents

result **real children**: 5, 7, 9, , 15 have no kid of own

2b: parent/child combinations substracting lonly children children

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

2c: overall parent substracting parent/child parent

result: **real parent** 1

build menu, starting real children, adding them rightfull parents , add together 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 , store parents , children foreach($arr $k=>$v){ $p[$v[0]]=$v[0]; $pc[$v[1]]=$v[0]; } //2a: filter out real children $c = array_diff_key($pc,$p); //2b: parent_child combinations $pc=array_diff_key($pc,$c); //3: real parent $p=array_diff_key($p,$pc); //sorting arrays needed if starting array not ordered ksort($p); ksort($pc); ksort($c); //3: building menu // create lonely childs foreach($c $k=>$v){ if(!isset($mc[$v])){$mc[$v]=array();} $mc[$v][]='<li>'.$menu[$k].'</li>'; } // build parent-child menu adding children rightfull parents foreach($pc $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 real parent foreach($p $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 $k=>$v){ $menu[]=implode('',$v); } //$menu='<ul>'.implode('',$menu).'</ul>'; //(old) $menu=implode('',$menu); //**new** echo $menu;

the result of above:

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

edit changed 2 lines create valid html

and new fiddle

php arrays