How can I rearrange array items moving dependencies on top?

Question

I have the following array where each item may (or may not depend) on another one:

$test = array(
    'c' => array(
        'depends' => 'b'
    ),
    'a' => array(),
    'b' => array(
        'depends' => 'a'
    ),
    'd' => array(
        'depends' => 'a'
    ),
);

I want to move (or make another array) with dependencies are moved at the top. First a, then b and d (both depend on a) and finally c which depends on b. The order of b and d is irrelevant:

$rearranged = array(
    'a' => array(),
    'b' => array(
        'depends' => 'a'
    ),
    'd' => array(
        'depends' => 'a'
    ),
    'c' => array(
        'depends' => 'b'
    ),
);

I'm pretty sure that this is a quite common situation and before reinventing the wheel and waste time I'd like to know if there is any data structure that can do the job for me.

EDIT: forgot to say that circular references should be detected (b depends on a that depends on b should not be allowed).

Answer 1

This is called topological sorting. If you consider your structure as a graph, where "a depends on b" is equal to a directed edge from vertex b to vertex a, you should just do a topological sort to get your answer.

Implementation of topological sort can be done like this:

let graph[ n ][ n ] be the graph corresponding to your array (graph[ i ][ j ] = 1 means j depends on i).

1. ans = {} // empty sequence
   
2. income = new array[ n ]
   
3. income[ i ] = number of edges incoming to vertex i
   
4. used = new array[ n ] // shows if any vertex has already been used, default all false
   
5. while ans.size != n // there are still unused vertexes
   do begin
   find i s.t. income[ i ] == 0 and used[ i ] == false
   ans.append( i )
   for each j s.t. graph[ i ][ j ] == 1 decrement income[ j ]
   end
   
6. return ans

Answer 2

array_multisort will help you here..

<?php

    $test = array(
        'c' => array(
            'depends' => 'b'
        ),
        'a' => array(),
        'b' => array(
            'depends' => 'a'
        ),
        'd' => array(
            'depends' => 'a'
        )
    );

    function sortArray($array= array())
         {
            $depend = array();
            foreach ($array as $key => $value)
            {

                if (isset($value['depends']))
                {
                    $depend[$key] = $value['depends'];
                }
                else
                {
                   $depend[$key] = null;
                }

            }
            return $depend;
         }


         function findCircularReference($array)
         {
            foreach($array as $key=>$value)
            {
               if(isset($array[$value]) && ($array[$value] == $key))
               {
                  return true;
               }
            }
            return false;
         }

         $depend = sortArray($test);
         $checkReference  = findCircularReference($depend);

         if( ! $checkReference)
         {
             array_multisort($depend, SORT_ASC, $test);
         }
         else
         {
             trigger_error("Circular reference", E_USER_ERROR);
         }


         print_r($test);
?>

Answer 3

Tested and works:

Basically it loops through each node and checks the depth of that node from the top of the tree and appends the value to a new array $ar. Then it sorts $test based on the depth level of each node stored in $ar using array_multisort().

<?php
$test = array(
    'c' => array(
        'depends' => 'b'
    ),
    'a' => array(),
    'b' => array(
        'depends' => 'a'
    ),
    'd' => array(
        'depends' => 'a'
    ),
);


function getNodeLevel($ar,$n,$ref=array())
{
       if(!isset($ar[$n]['depends'])){return 0;}
       if(in_array($n,$ref)){return -1;}
       $ref[]=$n;
       $r=getNodeLevel($ar,$ar[$n]['depends'],$ref);
       return ($r==-1?-1:$r+1);
}


$ar=array();

foreach($test as $i=>$tmp)
{
    $ar[]=getNodeLevel($test,$i);
}

if(!in_array(-1,$ar))
{
    array_multisort($ar,SORT_ASC,$test);
    print_r($test);
}else{
     trigger_error("Circular reference detected.", E_USER_ERROR);
}