Owen Melbourne Owen Melbourne - 2 months ago 10
PHP Question

PHP Order array based on elements dependency

Fairly hard one to explain, but effectively I've got an array of items which have IDs, of which can contain a list of IDs for other array items. for example

$items = [
[id: 'one', deps: ['three']],
[id: 'two'],
[id: 'three', deps: ['four', 'two']],
[id: 'four']
];


So as you can see here, one depends on three, and three depends on four and two.

I need to get a new array, that contains these items in order - so that the dependencies are listed in order. So the above array would convert into

$items = [
[id: 'four'],
[id: 'two'],
[id: 'three', deps: ['four', 'two']],
[id: 'one', deps: ['three']]
];


How would I complete this? I've tried various while loops checking for item positions, but can't crack it.

Thanks

UPDATE Some people have said its a duplicate question of THIS but the main difference being the above example has multiple dependencies - whereas the mentioned thread only works on a single string dependency

Answer

you can use a function like this, that iterates until all dependencies are met, or no more dependencies can be resolved:

$items = array(array('id' => 'one', 'deps' => array('three')),
                array('id' => 'two'),
                array('id' => 'three', 'deps' => array('four', 'two')),
                array('id' =>'four'));


$sortedItems = sortDeps($items);
var_dump($sortedItems);

function sortDeps($items) {
    $res = array();
    $doneList = array();

    // while not all items are resolved:
    while(count($items) > count($res)) {
        $doneSomething = false;

        foreach($items as $itemIndex => $item) {
            if(isset($doneList[$item['id']])) {
                // item already in resultset
                continue;
            }
            $resolved = true;

            if(isset($item['deps'])) {
                foreach($item['deps'] as $dep) {
                    if(!isset($doneList[$dep])) {
                        // there is a dependency that is not met:
                        $resolved = false;
                        break;
                    }
                }
            }
            if($resolved) {
                //all dependencies are met:
                $doneList[$item['id']] = true;
                $res[] = $item;
                $doneSomething = true;
            }
        }
        if(!$doneSomething) {
            echo 'unresolvable dependency';
        }
    }
    return $res;
}
Comments