Topological Sort / Dependency resolver in PHP

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.

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.

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

Examples:

$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):

$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)]).

Installation

Use composer package: marcj/topsort

{
    "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.

ArraySort

This is the most basic, most inefficient implementation of topSort using plain php arrays.

FixedArraySort

This uses \SplFixedArray of php and is therefore much more memory friendly.

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.

GroupedArraySort

This is the most basic, not so efficient implementation of grouped topSort using plain php arrays.

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.

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.

Count	Implementation	Memory	Duration
50	FixedArraySort	0b	0.0001s
50	ArraySort	0b	0.0001s
50	StringSort	0b	0.0001s
1,000	FixedArraySort	53,432b	0.0013s
1,000	ArraySort	37,720b	0.0012s
1,000	StringSort	89,112b	0.0013s
10,000	FixedArraySort	692,464b	0.0141s
10,000	ArraySort	529,240b	0.0138s
10,000	StringSort	1,080,472b	0.0154s
100,000	FixedArraySort	5,800,200b	0.1540s
100,000	ArraySort	4,199,280b	0.1499s
100,000	StringSort	10,124,000b	0.1645s
1,000,000	FixedArraySort	49,561,888b	1.5456s
1,000,000	ArraySort	33,559,408b	1.5597s
1,000,000	StringSort	95,480,848b	1.7942s

Count	Implementation	Memory	Duration
50	GroupedArraySort	0b	0.0002s
50	GroupedStringSort	0b	0.0002s
1,000	GroupedArraySort	112,280b	0.0090s
1,000	GroupedStringSort	99,440b	0.0025s
10,000	GroupedArraySort	1,431,320b	0.8385s
10,000	GroupedStringSort	1,176,304b	0.0267s
100,000	GroupedArraySort	12,318,072b	132.9709s
100,000	GroupedStringSort	11,129,144b	0.2788s
1,000,000	GroupedArraySort	-	too long
1,000,000	GroupedStringSort	106,488,496b	3.0879s