Create hierarchy from ordered list in PHP

Issue

I have a list of nodes and their requirements (i.e., ancestors). The good news is, the list is guaranteed to be in "order" (where order means that no node will be on the list until its requirements are also on the list), but I’d like to put it into a "hierarchy", so I can handle nodes at the same level in parallel.

For example, I have

+------+----------------+
| Node | Requires       |
+------+----------------+
|  A   |                |
+------+----------------+
|  B   |                |
+------+----------------+
|  C   |  A,B           |
+------+----------------+
|  D   |  C             |
+------+----------------+
|  E   |                |
+------+----------------+
|  F   |  E             |
+------+----------------+
...

and what I want is

+---+----------+
| 0 | A,B,E    |
+---+----------+
| 1 | C,F      |
+---+----------+
| 2 | D        |
+---+----------+
...

I’m getting the data from a 3rd-party library, and the way it comes in is the ordered list of nodes is an array of strings ($nodes), and the dependencies are stored in another object as an array with a key of the node name ($foreign_obj->reqs[ <node> ]->reqs).

EDIT: inserted based on comment:

Here’s a var_export of those two items:

nodes:

array ( 0 => 'A', 1 => 'B', 2 => 'C', 3 => 'D', 4 => 'E', 5 => 'F', 6 => 'G', 7 => 'H', )

the first few entries from foreign_obj->reqs:

array ( 'A' => _Requirement::__set_state((array( 'name' => 'A', 'src' => '/path/to/A.js', deps => array ( ), )), 'B' => _Requirement::__set_state((array( 'name' => 'B', 'src' => '/path/to/B.js', deps => array ( ), )), 'C' => _Requirement::__set_state((array( 'name' => 'C', 'src' => '/path/to/C.js', deps => array ( 0 => 'A', 1 => 'B', ), )),
...

All of the other questions I can find on here that are similar deal with the situation where you have a known, singular parent (e.g., Flat PHP Array to Hierarchy Tree), or you at least already know the parents (e.g., PHP hierarchical array – Parents and childs). The challenge I have here is that the data is the other direction (i.e., I have the given leafs and their ancestors).

I could use something like graphp/graph, but that seems like overkill. In particular, given that the list is already in order, I’m hoping there’s a fairly simple iteration I can do here, and it may not even need to be recursive.

I think something as simple as this would work:

$hierarchy = array();

foreach ( $nodes as $node ) {
        $requirements = $foreign_obj->reqs[ $node ]->reqs;
        if ( ! is_array( $requirements ) || empty( $requirements ) ) {
                array_push($hierarchy[0], $node);
                continue;
        }       

        $index = 0;
        foreach ($requirements as $req) {
                <find req in $hierarchy>
                if (<index of heirarchy where found> > $index) {
                        $index = <index of heirarchy where found>
                }       
        }
        array_push( $hierarchy[ $index + 1], $node);
}

The two questions, then, are:

  1. Does the above look like it would work, logically, or am I missing some edge case?
  2. What’s the most efficient/elegant PHP way to do the <find req in $hierarchy> bit?

Solution

  1. The good news is, the list is guaranteed to be in "order" (where order
    means that no node will be on the list until its requirements are also
    on the list),

Ok great, so this simplifies this requirement a lot. As you rightly said, there is no need of recursion here.

  1. Does the above look like it would work, logically, or am I missing some edge case?

Although it is not clearly evident to me since some variables seems to be missing with declarations, assignments etc, but yes, logically you are on the right track in terms of algorithmic steps.

  1. What’s the most efficient/elegant PHP way to do the <find req in $hierarchy> bit?

It is easy. When you completely process a node with it’s dependencies, store it’s rank/level in another associative array(more formally like a HashMap). So, now you can reuse this map to quickly decide on dependency node levels.

Snippet:

<?php

$hierarchy = [];
$p_rank = [];

foreach ( $nodes as $node => $dependencies ) {
    $level = 0; //$foreign_obj->reqs[ $node ]->reqs;
    foreach($dependencies as $parent_node){
        $level = max($level, $p_rank[ $parent_node ] + 1);
    } 
    
    $hierarchy[ $level ] = $hierarchy[ $level ] ?? [];
    $hierarchy[ $level ][] = $node;
    $p_rank[ $node ] = $level; // record the rank for use( if in case this is a dependency for some other future node)
}

print_r($hierarchy);
 

Online Demo

Note: Unfortunately, I can’t reproduce your var_export of sample input since I don’t have Requirement class definition with me(and would require extra work if I wish to do so). The sample input I have used suffices to replicate what you have on your machine.

Answered By – nice_dev

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply

(*) Required, Your email will not be published