marcj/topsort

High-Performance TopSort/Dependency resolving algorithm

Topological Sort / Dependency resolver in PHP

, _(*1)

This library provides several implementations of a Topological Sort (topSort). In additional to the plain sorting algorithm it provides several implementations of a Grouped Topological Sort, means you can pass items with a type which will be grouped together in the sorting. With its implementation of using strings instead of arrays its over 20x faster than regular implementations., _(*2)

What is it?

A topological sort is useful for determining dependency loading. It tells you which elements need to be proceeded first in order to fulfill all dependencies in the correct order., _(*3)

Example usage: Unit of Work (relations), simple Package manager, Dependency Injection, ..., _(*4)

Examples:, _(*5)

$sorter = new StringSort();

$sorter->add('car1', ['owner1', 'brand1']);
$sorter->add('brand1');
$sorter->add('brand2');
$sorter->add('owner1', ['brand1']);
$sorter->add('owner2', ['brand2']);

$result = $sorter->sort();
// output would be:
[
 'brand1',
 'owner1',
 'car1',
 'brand2',
 'owner2'
]

Sometimes you want to group equal types together (imagine a UnitOfWork which wants to combine all elements from the same type to stored those in one batch):, _(*6)

$sorter = new GroupedStringSort();

$sorter->add('car1', 'car', ['owner1', 'brand1']);
$sorter->add('brand1', 'brand');
$sorter->add('brand2', 'brand');
$sorter->add('owner1', 'user', ['brand1']);
$sorter->add('owner2', 'user', ['brand2']);

$result = $sorter->sort();
// output would be:
[
 'brand2',
 'brand1',
 'owner2',
 'owner1',
 'car1'
]

$groups = $sorter->getGroups();
[
   {type: 'brand', level: 0, position: 0, length: 2},
   {type: 'user', level: 1, position: 2, length: 2},
   {type: 'car', level: 2, position: 4, length: 1},
]
//of course there may be several groups with the same type, if the dependency graphs makes this necessary.

foreach ($groups as $group) {
   $firstItem = $result[$group->position];
   $allItemsOfThisGroup = array_slice($result, $group->position, $group->length);
}

You can only store strings as elements. To sort PHP objects you can stored its hash instead. $sorter->add(spl_object_hash($obj1), [spl_object_hash($objt1Dep)])., _(*7)

Installation

Use composer package: marcj/topsort, _(*8)

{
    "require": {
        "marcj/topsort": "~0.1"
    }
}

include 'vendor/autoload.php';

$sorter = new GroupedStringSort;
$sorter->add(...);

$result = $sorter->sort();

Implementations

tl;dr: Use FixedArraySort for normal topSort or GroupedStringSort for grouped topSort since its always the fastest and has a good memory footprint., _(*9)

ArraySort

This is the most basic, most inefficient implementation of topSort using plain php arrays., _(*10)

FixedArraySort

This uses \SplFixedArray of php and is therefore much more memory friendly., _(*11)

StringSort

This uses a string as storage and has therefore no array overhead. It's thus a bit faster and has almost equal memory footprint like FixedArraySort. Small drawback: You can not store element ids containing a null byte., _(*12)

GroupedArraySort

This is the most basic, not so efficient implementation of grouped topSort using plain php arrays., _(*13)

GroupedStringSort

This uses a string as storage and has therefore no array operations overhead. It's extremely faster and has better memory footprint than GroupedArraySort. Small drawback: You can not store element ids containing a null byte., _(*14)

Benchmarks with PHP 7.0.9

Test data: 1/3 has two edges, 1/3 has one edge and 1/3 has no edges. Use the benchmark command in ./bin/console to play with it., _(*15)