rearrange a php array into a nested hierarchical array

Question

How can I transform array#1 into the array#2 structure using php ?

The first Array is the results of a database query on a list of Organisms, each organism is classified with it's Order, Family, Genus, Species. Hierarchically Species are the child classifications of various Genus, and Genus classifications are child classifications of various Families etc .

In namespace terms you could read it like so:

item at index[ 0] ---> Hemiptera.Miridae.Kanakamiris
item at index[ 1] ---> Hemiptera.Miridae.Neophloeobia.incisa

There is a kind of parent/child relationship between the keys of array#1 which is as follows:

'Rank_Order' value is the parent of the 'Rank_Family' value
'Rank_Family' value is the parent of the 'Rank_Genus' value
'Rank_Genus' value is the parent of the 'Rank_Species' value

array#1:

Array
(
    [0] => Array
        (
            ['Rank_Order'] => 'Hemiptera'
            ['Rank_Family'] => 'Miridae'
            ['Rank_Genus'] => 'Kanakamiris'
            ['Rank_Species'] => ''
        )   
    [1] => Array
        (
            ['Rank_Order'] => 'Hemiptera'
            ['Rank_Family'] => 'Miridae'
            ['Rank_Genus'] => 'Neophloeobia'
            ['Rank_Species'] => 'incisa'
        )
    [2] => Array
        (
            ['Rank_Order'] => 'Hemiptera'
            ['Rank_Family'] => 'Noridae'
            ['Rank_Genus'] => 'Canelbia'
            ['Rank_Species'] => 'Arissa'
        )
)

The following array is the array structure i need: array#2:

Array(
    [name]     => 'Hemiptera'
    [children] => Array(

        [0] => Array(
            [name]     => 'Miridae'
            [children] => Array(

                [0] => Array(
                    [name]     => 'Kanakamiris'
                    [children] => Array(
                    )
                )
                [1] => Array(
                    [name]     => 'Neophloeobia'
                    [children] => Array(

                        [0] => Array(
                            [name] => 'incisa'
                            [children] => Array(
                            )
                        )
                    )
                )
            )
        )
        [1] => Array(
            [name]     => 'Noridae'
            [children] => Array(

                [0] => Array(
                    [name]     => 'Canelbia'
                    [children] => Array(

                        [0] => Array(
                            [name] => 'Arissa'
                            [children] => Array(
                            )
                        )
                    )
                )
            )
        )
    )
)

I see similar questions asked in stack overflow, though have not been able to use them in my case. eg. php-reorder-array-to-reflect-parent-id-hierarchy

You say that similar questions aren't usable in your case, but don't provide us *any* details about your specific array structure... **what is you question??** — orourkek, Aug 16 '12 at 05:36
I want to take the first array and create the second array from it. I will edit the statement between the two code blocks to be a question, apologies — johowie, Aug 16 '12 at 05:40
The motivation for this is that the second array is the structure i require before i encode the array into JSON and use it for another purpose — johowie, Aug 16 '12 at 05:45
it's not clear how does the first array translates into the second since the key-names are different. Also, why not convert it into json directly, why do you have to go through another phase of a nested array ? — Nir Alfasi, Aug 16 '12 at 05:49
Please describe in an algorithmic way what was going on in your head when you transformed array1 to array2 while writing this question. — Adi, Aug 16 '12 at 05:57
This whole thing is about the tree of life. level1 = Order, level2 = Family, level3 = genus, level4 = species. I think my use of A,B,C and levels may not be useful. Shall i rewrite the arrays with the real data ? — johowie, Aug 16 '12 at 06:04
Question has been substantially rewritten. If you could all have a look again I will be so appreciative. Thanks — johowie, Aug 16 '12 at 06:16
@Adnan tell me if you still need me to describe this algorithmically after see my rewrite with the actual data I am using — johowie, Aug 16 '12 at 06:17
@johowie, **now** it makes more sense. First time you were reusing `A` in `level4` which was very confusing. — Adi, Aug 16 '12 at 06:23
@alfasin in biological classification there are classification levels, which are kind of like namespaces. in the first array we have three items with the namespaced names: 'Hemiptera.Miridae.Kanakamiris.Rank_Species' 'Hemiptera.Miridae.Neophloeobia.incisa' 'Hemiptera.Noridae.Canelbia.Arissa' I want to express this hierarchical structure in a parent child structure. the final array structure is the structure needed for encoding to JSON which will be consumed by another application expecting this structure — johowie, Aug 16 '12 at 06:27
@Adnan yes , sorry about that i thought i was simplifying things ... i was sooo wrong — johowie, Aug 16 '12 at 06:28
@johowie I think you are missing the point, there is no explicit set of rules that translates the first array into the second. If there is such, you're not describing it. — Nir Alfasi, Aug 16 '12 at 06:35
@alfasin I can see that this was not explicitly clear, I have amended the question to hopefully make this more clear. basically the implicit parent child relationship in the first array was like a namespace that followed this structure: Rank_Order.Rank_Family.Rank_Genus.Rank_Species — johowie, Aug 16 '12 at 07:11

Mark Elliot · Answer 1 · 2012-08-20T05:47:17.323

2

I don't think this will be super-efficient for really large arrays, but it works for your scenario (here's a sample).

 $array = ...
 $levels = array('Rank_Order', 'Rank_Family', 'Rank_Genus', 'Rank_Species');

 function get_children($parent, $lev, $orig, $levels){
     if($lev + 1 > count($levels)){
          return array();
     }

     $seen = array();
     $children = array();
     foreach($orig as $node){
         if($node[$levels[$lev]] == $parent && !in_array($node[$levels[$lev+1]], $seen)){
             $seen[] = $node[$levels[$lev+1]];
             $children[] = get_children($node[$levels[$lev+1]], $lev+1, $orig, $levels);
         }
     }
     return array('name' => $parent, 'children' => $children);
 }

 function hier($orig, $levels){
     $seen = array();
     $result = array();
     foreach($orig as $node){
         if(!in_array($node[$levels[0]], $seen)){
              $seen[] = $node[$levels[0]];
              $result[] = get_children($node[$levels[0]], 0, $orig, $levels);
         }
     }
     return $result;
 }

 print_r($array);
 print_r(hier($array, $levels));

edited Aug 20 '12 at 05:47

answered Aug 16 '12 at 23:21

Mark Elliot

75,278
22
140
160

it seems `$result` needs to be pushed in somewhere. i'm trying to understand where – johowie Aug 17 '12 at 05:49
@johowie: ah, I missed the initialization in the second function, but it's not actually required. You just need to capture the output of a call to hier – Mark Elliot Aug 17 '12 at 12:04
that is indeed working as required, though computation time does seem to be a problem. – johowie Aug 18 '12 at 23:42
1

@johowie, it's not clear to me that one can do better. This will take at most O(MN) time for depth M and N distinct root elements, and should do much better for complete hierarchies. Here, M is constant, so the algorithm's complexity, believe it or not, is linear. – Mark Elliot Aug 19 '12 at 03:49
in `hier()` it seems the `return $seen;` should be `return $result;`, is that correct ?. when I run this php script it takes ages on my local host (MAMP) and with arrays larger than a handful of nodes it simply times out with a server error. Your example @Mark on ideone.com works considerably faster. I cant work out why my localhost doesn't like this ! – johowie Aug 20 '12 at 05:44
Yep, you're right. I corrected these errors on ideone but obviously failed to copy everything back. – Mark Elliot Aug 20 '12 at 05:48

rearrange a php array into a nested hierarchical array

1 Answers1

Linked