vertilia/algo-toposort

Topological sort algorithm

v1.0.0 2023-07-27 14:37 UTC

Requires

• php: >=7.4

Requires (Dev)

• phpunit/phpunit: ^9

BSD-2-Clause

• search
• sort
• topo
• topological
• depth-first

README

Topological sort implementing depth-first search algorithm (Tarjan 1976).

Install

composer require vertilia/algo-toposort

Usage

Example tree to sort topologically:

graph LR
    a --> b
    a --> d
    a --> c
    a --> e
    b --> d
    c --> d
    c --> e
    d --> e

Call with array passed in constructor:

$values = [
    'a' => ['b', 'd', 'c', 'e'],
    'b' => ['d'],
    'c' => ['d', 'e'],
    'd' => ['e'],
    'e' => [],
];

$a = new TopoSort($values);

$sorted = $a->sort();

print_r($sorted);

Call by forming initial array via addNode() calls:

$a = new TopoSort();

$a->addNode('a', ['b', 'd', 'c', 'e'])
    ->addNode('b', ['d']),
    ->addNode('c', ['d', 'e']),
    ->addNode('d', ['e']),
    ->addNode('e', []);

$sorted = $a->sort();

print_r($sorted);

Call by forming initial array via addLink() calls:

$a = new TopoSort();

$a->addLink('a', 'b')
    ->addLink('a', 'd'),
    ->addLink('a', 'c'),
    ->addLink('a', 'e'),
    ->addLink('b', 'd'),
    ->addLink('c', 'd'),
    ->addLink('c', 'e'),
    ->addLink('d', 'e');

$sorted = $a->sort();

print_r($sorted);

Output:

Array
(
    [0] => a
    [1] => c
    [2] => b
    [3] => d
    [4] => e
)

Resulting order:

graph LR
    a --> c
    c --> b
    b --> d
    d --> e