PHP topological sort

LIST: controller name => priority:required controllers

$array(
"controller_3" => "3",
"controller_1" => "1:controller_2",
"controller_2" => "2",
"controller_4" => "1:controller_2&controller_1",
"controller_x" => "2:controller_not_exists",
"controller_loopexit1" => "4:controller_loopexit2",
"controller_loopexit2" => "5:controller_loopexit1"
)

sorted and expected output:

controller_2
controller_1
controller_4
controller_3

---

First sort by priority, then reorder based on required controllers to be loaded before. ensure not to be stuck in an infinite loop due to controllers requiring each other.

---

I assume I’ll need something like this:

function cmp($a, $b) {
    if ($a == $b) {
        return 0;
    }
    return ($a < $b) ? -1 : 1;
}

uasort($controllers_array, 'cmp');

Please help solve this with these steps:

1. Remove infinite loop controllers (ex: controller_loopexit1 & controller_loopexit2)
2. Remove controllers that have a dependency of a controller that doesn`t exist (ex: controller_x depending on controller_not_exists.)
3. Sort remaining items by priority number, lowest comes first
4. Second sort by dependencies

Answer

Code:

<?php

include 'vendor/autoload.php';

class TheSortedControllers{

    private $inputControllerList = [];
    private $inputControllerMap = [];
    private $sorter = null;

    function __construct($inputControllerList){
        $this->inputControllerList = $inputControllerList;
        $this->sorter = new MJSTopSortImplementationsStringSort();
    }

    function inputMapper(){

        $controllersList = $this->inputControllerList;

        foreach($controllersList as $controllerId=>$controllerData){

            $controllerData = (explode(":",$controllerData));
            $this->inputControllerMap[$controllerId]['priority'] = (int)$controllerData[0];

            if(isset($controllerData[1])){
                $this->inputControllerMap[$controllerId]['required'] = explode("&",$controllerData[1]);
            }

        }

    }

    function sortByPriority($a, $b)
    {
        return $a['priority'] - $b['priority'];
    }

    function sort(){

        $this->inputMapper();

        uasort($this->inputControllerMap, array($this, "sortByPriority"));

        foreach($this->inputControllerMap as $controllerID=>$controllerData){

            $required = $controllerData['required'] ?? [];

            $this->sorter->add($controllerID, $required);
        }

        return $this->sorter->sort();
    }
}


$controllersList =  array(
    "controller_3" => "3",
    "controller_1" => "1:controller_2",
    "controller_2" => "2",
    "controller_4" => "1:controller_2&controller_1",
);

$theSortedControllers = new TheSortedControllers($controllersList);

try {
    $outputControllersList = $theSortedControllers->sort();
    print_r($outputControllersList);
} catch (Exception $e) {
    echo 'Message: ' .$e->getMessage();
}

Usage:

1. I am using https://github.com/marcj/topsort.php. To use it you must have Composer. Run composer require marcj/topsort to install the code dependency.
2. That’s it. In case of an exception, the code does not automatically remove the nodes (controllers), it’s best to use human intervention to make sure you resolve those exceptions and have a proper input.

Examples:

Case 1

Input (Your Original Input – Missing Dependency):

$controllersList =  array(
    "controller_3" => "3",
    "controller_1" => "1:controller_2",
    "controller_2" => "2",
    "controller_4" => "1:controller_2&controller_1",
    "controller_x" => "2:controller_not_exists",
    "controller_loopexit1" => "4:controller_loopexit2",
    "controller_loopexit2" => "5:controller_loopexit1"
);

Output:

Message: Dependency `controller_not_exists` not found, required by `controller_x`

---

Case 2

Input (Add the missing dependency, you still have circular-dependency/infinite-loop):

$controllersList =  array(
    "controller_3" => "3",
    "controller_1" => "1:controller_2",
    "controller_2" => "2",
    "controller_4" => "1:controller_2&controller_1",
    "controller_x" => "2:controller_not_exists",
    "controller_loopexit1" => "4:controller_loopexit2",
    "controller_loopexit2" => "5:controller_loopexit1",
    "controller_not_exists" => "10:controller_2",
);

Output:

Message: Circular dependency found: controller_loopexit1->controller_loopexit2->controller_loopexit1

---

Case 3

Input (Removed the controllers with circular dependency):

$controllersList =  array(
    "controller_3" => "3",
    "controller_1" => "1:controller_2",
    "controller_2" => "2",
    "controller_4" => "1:controller_2&controller_1",
    "controller_x" => "2:controller_not_exists",
    "controller_not_exists" => "10:controller_2",
);

Output:

Array
(
    [0] => controller_2
    [1] => controller_1
    [2] => controller_4
    [3] => controller_not_exists
    [4] => controller_x
    [5] => controller_3
)

---

Case 4

Input (Removed controller_not_exists and controller_x):

$controllersList =  array(
    "controller_3" => "3",
    "controller_1" => "1:controller_2",
    "controller_2" => "2",
    "controller_4" => "1:controller_2&controller_1",
);

Output:

Array
(
    [0] => controller_2
    [1] => controller_1
    [2] => controller_4
    [3] => controller_3
)