Create hierarchy from ordered list in PHP

Question

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?

Answer 1

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.

2. 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.

3. 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.

Answer 2

I don't know if this is the most efficient/elegant way to do this, so I'll not mark my own answer as correct, yet, and see if anyone has any improvements on the below, but this seems to work:

$hierarchy = array();

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

        $index = 0;
        foreach ($requirements as $req) {
                $i = array_key_last( array_filter($hierarchy, 
                    fn($arr)=> in_array($req, $arr, true));
                if ($i > $index) {
                        $index = $I;
                }       
        }
        $hierarchy[ $index + 1] = $node;
}

Answer 3

The idea here is to push nodes to an array that have no requirements then delete those new pushed elements from the values of each key of the dict. Reapeat until the dict becomes empty.

1. Push nodes that have no requirements to an array1 ( This array will hold the nodes of a specific level ).

2. Once you pushed all nodes that have no requirements, push that array to a global array ( This array will hold the array of each level ).

3. Delete those recently pushed nodes from the values of each entry in the dict.

4. Empty array1.

5. Repeat.

    $arr = array();
    foreach ( $nodes as $node ) {
        $requirements = $foreign_obj->reqs[ $node ]->reqs;
        $arr[$node] = $requirements;
    }
   
    $hierarchy = array();
    $level = 0;
    $iterations = count($arr);
    for($i=0; $i < $iterations; $i++){
        $pushed_nodes = push_nodes($arr);
        $hierarchy[$level] = $pushed_nodes;
        $level = $level + 1;
        $arr = delete_nodes($arr, $pushed_nodes);
        if (count($arr) == 0){
            break;
        }
    }
    print_r($hierarchy);
    function push_nodes($arr){
        $arr1 = array();
        foreach ( $arr as $node => $requirements ){
            if (count($requirements) == 0){
                array_push($arr1, $node);
            }
        }
        return $arr1;
    }
   
    function delete_nodes($arr, $nodes_to_delete){
        $arr1 = array();
        foreach ( $arr as $node => $requirements ){
            $new_requirements = array();
            foreach ($requirements as $r ){
                if ( ! in_array($r, $nodes_to_delete) ){
                    array_push($new_requirements, $r);
                }
            }
            if (count($requirements) != 0){
                $arr1[$node] = $new_requirements;
            }
        }
        return $arr1;
    }
   

Tested on this :

    $arr = array(
        'A' => array(),
        'B' => array('A'),
        'C' => array('B', 'A'),
        'D' => array('B', 'A')
    );

Output :

    Array ( [0] => Array ( [0] => A ) [1] => Array ( [0] => B ) [2] => Array ( [0] => C [1] => D ) )