PHP Order array based on elements dependency

Question

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

andre · Accepted Answer · 2016-09-26 22:17:15Z

5

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;
}

answered Sep 26, 2016 at 22:17

andre

1943 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

owenmelbz Over a year ago

@andrew this works perfectly (almost) :P I had to add $items = array_unique($items, SORT_REGULAR); incase some items had been requested twice in the list!

ymakux Over a year ago

I haven't tested it too much but looks like a working solution and only 2 loops! Thanks!

Collectives™ on Stack Overflow

PHP Order array based on elements dependency

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related