vertilia/algo-toposort

Topological sort algorithm

Maintainers

Details

github.com/vertilia/algo-toposort

Source

Issues

Installs: 4

Dependents: 0

Suggesters: 0

Security: 0

Stars: 0

Watchers: 1

Forks: 0

Open Issues: 0

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

Requires

  • php: >=7.4

Requires (Dev)

BSD-2-Clause d6e4310560e97d58dc58ecf6066b043a53dfbc00

searchsorttopotopologicaldepth-first

This package is auto-updated.

Last update: 2024-11-27 17:51:28 UTC

README

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

Install

composer require vertilia/algo-toposort

Usage

Example tree to sort topologically:

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: