Sort array values based on parent/child relationship

Question

I am trying to sort an array to ensure that the parent of any item always exists before it in the array. For example:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [2] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )

    [3] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )

    [4] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [5] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

In the above array this "fails" as [1][2] (Sam) does not yet exist and nor does [4][2] (Tom).

The correct output would be as, in this case, as both Sam and Tom's parents already exist before they appear in the array:

Array
(
    [0] => Array
        (
            [0] => 207306
            [1] => Bob
            [2] => 
        )

    [1] => Array
        (
            [0] => 199714
            [1] => John
            [2] => 207306
        )


    [2] => Array
        (
            [0] => 199730
            [1] => Sam
            [2] => 199714
        )

    [3] => Array
        (
            [0] => 199728
            [1] => Simon
            [2] => 207306
        )


    [4] => Array
        (
            [0] => 199718
            [1] => Phillip
            [2] => 207306
        )


    [5] => Array
        (
            [0] => 199716
            [1] => Tom
            [2] => 199718
        )

    [6] => Array
        (
            [0] => 199720
            [1] => James
            [2] => 207306
        )

)

I found an answer https://stackoverflow.com/a/12961400/1278201 which was very close but it only seems to go one level deep (i.e. there is only ever one parent) whereas in my case there could be 1 or 10 levels deep in the hierarchy.

How do I sort the array so no value can appear unless its parent already exists before it?

Please explain your problem more clearly. It's not clear what the integer values refer to in each array at indexes 0 and 2, because they're too large to refer to any existing index. — Sayed, Sep 04 '16 at 08:35
Index 0 is the ID of each employee and Index 2 is the ID of the manager for that employee which is a lookup of the managers ID so, in the example above, John has an ID of 199714 and his manager is 207306 which is Bob as Bob has an ID of 207306 (index0) — bhttoan, Sep 04 '16 at 11:01
I was considering to vote this question for closing as this is more of a coding challenge than a real question. You did not post any personal attempt to solve the problem, just simply posted some data and a link to some already given solution that realy works. By sticking to the strict standards of SO this is a not a good question. Consider rereading http://stackoverflow.com/help/how-to-ask for your next question(s). — maxhb, Sep 05 '16 at 08:19
This particular way of storing relationships is called an [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list) and there are [well-defined ways of traversing them](http://salman-w.blogspot.com/2012/08/php-adjacency-list-hierarchy-tree-traversal.html). — bishop, Sep 06 '16 at 20:00

bwoebi · Answer 1 · 2016-09-11T23:01:39.827

5

This will trivially order the array (in O(n)) putting first all those with no parent, then these whose parent is already in the array, iteratively, until there's no children having the current element as parent.

# map the children by parent
$parents = ['' => []];
foreach ($array as $val) {
    $parents[$val[2]][] = $val;
}
# start with those with no parent
$sorted = $parents[''];
# add the children the current nodes are parent of until the array is empty
foreach ($sorted as &$val) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

This code requires PHP 7, it may not work in some cases under PHP 5. - for PHP 5 compatibility you will have to swap the foreach ($sorted as &$val) with for ($val = reset($sorted); $val; $val = next($sorted)):

# a bit slower loop which works in all versions
for ($val = reset($sorted); $val; $val = next($sorted)) {
    if (isset($parents[$val[0]])) {
        foreach ($parents[$val[0]] as $next) {
            $sorted[] = $next;
        }
    }
}

Live demo: https://3v4l.org/Uk6Gs

edited Sep 11 '16 at 23:01

answered Sep 04 '16 at 21:01

bwoebi

23,637
5
58
79

Am using PHP 5.6 - can you highlight any bits you are aware of which won't work? – bhttoan Sep 05 '16 at 05:48
When the loop is at the last element and a new element is inserted, the loop will terminate immediately instead of continuing. The workaround would be changing the foreach to a `for ($val = reset($sorted); $val; $val = next($sorted))`. – bwoebi Sep 05 '16 at 12:08
I am getting an out of memory error on the line $sorted[]=$next – bhttoan Sep 11 '16 at 22:46
@bhttoan sorry, I used the wrong index when testing my data. replaced 2 with 0; does it work now? – bwoebi Sep 11 '16 at 22:53
Memory error has gone but the output / sorted array is empty – bhttoan Sep 11 '16 at 23:01
@bhttoan I'm sorry … try again… :-( Now replaced one 2 too much – bwoebi Sep 11 '16 at 23:01
@bhttoan Included a live demo (https://3v4l.org/Uk6Gs) to be really sure that it works :-/ Sorry for giving you a bit wrong code in the first place. – bwoebi Sep 11 '16 at 23:05
Yes this seems to work fine - have come across an edge case scenario whereby there are a few entries whose parents are not in the array at all and they are being excluded completely so I need to try to get my head around that – bhttoan Sep 11 '16 at 23:19
@bhttoan Well, that was not specified in the question (i.e. the question suggested that `''` is the root) - then you need a map with the children array and check whether any node has no parent and prime the array with it; i.e. instead of `$sorted = $parents[''];` do `$sorted = $children = []; foreach ($array as $val) { $children[$val[0]] = $val; } foreach ($array as $val) { if (!isset($children[$val[2]])) { $sorted[] = $val; } }`. – bwoebi Sep 11 '16 at 23:32
Seems not working: live demo (3v4l.org/Uk6Gs) does not give desired result as asked in question. – Azghanvi Feb 16 '20 at 09:08

maxhb · Answer 2 · 2016-09-09T10:52:42.667

I have two different version for you.

a) Using a "walk the tree" approach with recursion and references to minimize memory consumption

$data = [
    [207306,'Bob',''], [199730,'Sam',199714],
    [199728,'Simon',207306], [199714,'John',207306],
    [199716, 'Tom',199718], [199718,'Phillip',207306],
    [199720,'James',207306]
];

$list = [];
generateList($data, '', $list);

var_dump($list);

function generateList($data, $id, &$list) {
    foreach($data as $d) {
        if($d[2] == $id) {          
            $list[] = $d; // Child found, add it to list            
            generateList($data, $d[0], $list); // Now search for childs of this child
        }
    }
}

b) Using phps built in uusort()function (seems only to work up to php 5.x and not with php7+)

$data = [
    [207306,'Bob',''], [199730,'Sam',199714],
    [199728,'Simon',207306], [199714,'John',207306],
    [199716, 'Tom',199718], [199718,'Phillip',207306],
    [199720,'James',207306]
];

usort($data, 'cmp');

var_dump($data);

function cmp($a, $b) {  
    if($a[2] == '' || $a[0] == $b[2]) return -1; //$a is root element or $b is child of $a
    if($b[2] == '' || $b[0] == $a[2]) return 1; //$b is root element or $a is child of $b
    return 0; // both elements have no direct relation
}

Try running the usort() example with PHP 7, it will not give the expected results [due to algorithm change]. usort() is just meant for a total ordering (i.e. every element has a well defined relation to each other showing a well defined order). Let's take $a, $b and $c; then if $a == $b and $b == $c, $a == $c is assumed. Your code works for this input with PHP 5, but with different inputs it also fails on PHP 5. — bwoebi, Sep 05 '16 at 19:44
Thank you for your feedback. Can you provide an example of input data where the `usort()` approach does not work (with php5)? — maxhb, Sep 06 '16 at 07:01
Thank you for your feedback, did not recognize that the behavior of `usort()` changed from php5 to php7. — maxhb, Sep 09 '16 at 10:52

score 1 · Answer 3 · answered Sep 06 '16 at 08:09

I checked this works in PHP 5.6 and PHP 7

Sample array:

$array = Array(0 => Array(
        0 => 207306,
        1 => 'Bob',
        2 => '',
    ),
    1 => Array
        (
        0 => 199730,
        1 => 'Sam',
        2 => 199714,
    ),
    2 => Array
        (
        0 => 199728,
        1 => 'Simon',
        2 => 207306,
    ),
    3 => Array
        (
        0 => 199714,
        1 => 'John',
        2 => 207306,
    ),
    4 => Array
        (
        0 => 199716,
        1 => 'Tom',
        2 => 199718,
    ),
    5 => Array
        (
        0 => 199718,
        1 => 'Phillip',
        2 => 207306,
    ),
    6 => Array
        (
        0 => 199720,
        1 => 'James',
        2 => 207306,
    ),
); 



echo "<pre>";
$emp = array();

//form the array with parent and child
foreach ($array as $val) {
    $manager = ($val[2] == '') ? 0 : $val[2];
    $exist = array_search_key($val[2], $emp);
    if ($exist)
        $emp[$exist[0]][$val[0]] = $val;
    else
    //print_R(array_search_key(199714,$emp));
        $emp[$manager][$val[0]] = $val;
}

$u_emp = $emp[0];
unset($emp[0]);

//associate the correct child/emp after the manager
foreach ($emp as $k => $val) {
    $exist = array_search_key($k, $u_emp);
    $pos = array_search($k, array_keys($u_emp));

    $u_emp = array_slice($u_emp, 0, $pos+1, true) +
            $val +
            array_slice($u_emp, $pos-1, count($u_emp) - 1, true);

}
print_R($u_emp); //print the final result

// key search function from the array
function array_search_key($needle_key, $array, $parent = array())
{
    foreach ($array AS $key => $value) {
        $parent = array();
        if ($key == $needle_key)
            return $parent;
        if (is_array($value)) {
            array_push($parent, $key);
            if (($result = array_search_key($needle_key, $value, $parent)) !== false)
                return $parent;
        }
    }
    return false;
}

score 1 · Answer 4 · answered Sep 08 '16 at 13:24

Find the below code that might be helpful.So, your output is stored in $sortedarray.

$a=array(array(207306,'Bob',''),
array (199730,'Sam',199714),
array(199728,'Simon',207306),
array(199714,'John',207306),
array(199716,'Tom',199718),
array(199718,'Phillip',207306),
array(199720,'James',207306));

$sortedarray=$a;
foreach($a as $key=>$value){
    $checkvalue=$value[2];
    $checkkey=$key;
foreach($a as $key2=>$value2){
    if($key<$key2){
            if ($value2[0]===$checkvalue){
                $sortedarray[$key]=$value2;
                $sortedarray[$key2]=$value;
        }else{
            }
    }
  }
 }

 print_r($sortedarray);

Marcus · Answer 5 · 2016-08-24T12:25:54.577

What about this approach:

Create an empty array result.

Loop over your array and only take the items out of it where [2] is empty and insert them into result.

When this Loop is done you use a foreach-Loop inside a while-loop. With the foreach-Loop you take every item out of your array where [2] is already part of result. And you do this as long as your array contains anything.

$result = array();
$result[''] = 'root';

while(!empty($yourArray)){
  foreach($yourArray as $i=>$value){
    if(isset($result[$value[2]])){
      // use the next line only to show old order
      $value['oldIndex'] = $i;
      $result[$value[0]] = $value;
      unset($yourArray[$i]);
    }
  }
}

unset($result['']);

PS: You may run into trouble by removing parts of an array while walking over it. If you do so ... try to solve this :)

PPS: Think about a break condition if your array have an unsolved loop or a child without an parent.

score 0 · Answer 6 · answered Sep 07 '16 at 05:03

0

you can use your array in variable $arr and use this code it will give you required output.

function check($a, $b) {   
    return ($a[0] == $b[2]) ? -1 : 1;
}


uasort($arr, 'check');
echo '<pre>';
print_r(array_values($arr));
echo '</pre>';

answered Sep 07 '16 at 05:03

piyushiiitm

25
3

Same issue than maxhb's answer: http://stackoverflow.com/questions/39121729/sort-array-values-based-on-parent-child-relationship#comment66004812_39326118 – bwoebi Sep 08 '16 at 13:26

Sort array values based on parent/child relationship

6 Answers6

Linked