PHPackages                             wolfulus/topsort - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. wolfulus/topsort

ActiveLibrary[Utility & Helpers](/categories/utility)

wolfulus/topsort
================

High-Performance TopSort/Dependency resolving algorithm

1.2.0(5y ago)078MITPHPPHP >=7.3

Since Oct 16Pushed 5y agoCompare

[ Source](https://github.com/WoLfulus/topsort)[ Packagist](https://packagist.org/packages/wolfulus/topsort)[ GitHub Sponsors](https://github.com/marcj)[ RSS](/packages/wolfulus-topsort/feed)WikiDiscussions master Synced yesterday

READMEChangelog (1)Dependencies (3)Versions (6)Used By (0)

Topological Sort / Dependency resolver in PHP
=============================================

[](#topological-sort--dependency-resolver-in-php)

[![Build Status](https://camo.githubusercontent.com/ee5181f71f04d621275629da383f239fd81ed8471978233353ea50333481b069/68747470733a2f2f7472617669732d63692e6f72672f6d6172636a2f746f70736f72742e7068702e737667)](https://travis-ci.org/marcj/topsort.php)[![Code Climate](https://camo.githubusercontent.com/ae1e41cf4f9f117fd17d064a80375035dc3abcfcc76898eddb9f9b93249df0bc/68747470733a2f2f636f6465636c696d6174652e636f6d2f6769746875622f6d6172636a2f746f70736f72742e7068702f6261646765732f6770612e7376673f)](https://codeclimate.com/github/marcj/topsort.php)[![Test Coverage](https://camo.githubusercontent.com/fa735689e346c6a9def389039a6fb834803344fe46437ff18034ab1cd9ec277a/68747470733a2f2f636f6465636c696d6174652e636f6d2f6769746875622f6d6172636a2f746f70736f72742e7068702f6261646765732f636f7665726167652e7376673f)](https://codeclimate.com/github/marcj/topsort.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?
-----------

[](#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
------------

[](#installation)

Use composer package: \[marcj/topsort)\[\]

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

```

```
include 'vendor/autoload.php';

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

$result = $sorter->sort();
```

Implementations
---------------

[](#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

[](#arraysort)

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

### FixedArraySort

[](#fixedarraysort)

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

### StringSort

[](#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

[](#groupedarraysort)

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

### GroupedStringSort

[](#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
-------------------------

[](#benchmarks-with-php-709)

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.

CountImplementationMemoryDuration50FixedArraySort0b0.0001s50ArraySort0b0.0001s50StringSort0b0.0001s1,000FixedArraySort53,432b0.0013s1,000ArraySort37,720b0.0012s1,000StringSort89,112b0.0013s10,000FixedArraySort692,464b0.0141s10,000ArraySort529,240b0.0138s10,000StringSort1,080,472b0.0154s100,000FixedArraySort5,800,200b0.1540s100,000ArraySort4,199,280b0.1499s100,000StringSort10,124,000b0.1645s1,000,000FixedArraySort49,561,888b1.5456s1,000,000ArraySort33,559,408b1.5597s1,000,000StringSort95,480,848b1.7942sCountImplementationMemoryDuration50GroupedArraySort0b0.0002s50GroupedStringSort0b0.0002s1,000GroupedArraySort112,280b0.0090s1,000GroupedStringSort99,440b0.0025s10,000GroupedArraySort1,431,320b0.8385s10,000GroupedStringSort1,176,304b0.0267s100,000GroupedArraySort12,318,072b132.9709s100,000GroupedStringSort11,129,144b0.2788s1,000,000GroupedArraySort-too long1,000,000GroupedStringSort106,488,496b3.0879s

###  Health Score

28

—

LowBetter than 54% of packages

Maintenance20

Infrequent updates — may be unmaintained

Popularity9

Limited adoption so far

Community12

Small or concentrated contributor base

Maturity62

Established project with proven stability

 Bus Factor1

Top contributor holds 50% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Every ~528 days

Total

5

Last Release

2113d ago

Major Versions

0.2 → 1.0.02015-06-17

PHP version history (2 changes)0.1PHP >=5.4

1.2.0PHP >=7.3

### Community

Maintainers

![](https://www.gravatar.com/avatar/a87192ba5cdccfebcde0b2c392a93db792ae98b45dc009124a0e13b5354dfd52?d=identicon)[WoLfulus](/maintainers/WoLfulus)

---

Top Contributors

[![marcj](https://avatars.githubusercontent.com/u/450980?v=4)](https://github.com/marcj "marcj (9 commits)")[![totten](https://avatars.githubusercontent.com/u/1336047?v=4)](https://github.com/totten "totten (5 commits)")[![thebuccaneersden](https://avatars.githubusercontent.com/u/512767?v=4)](https://github.com/thebuccaneersden "thebuccaneersden (1 commits)")[![tomvlk](https://avatars.githubusercontent.com/u/3877688?v=4)](https://github.com/tomvlk "tomvlk (1 commits)")[![ve3](https://avatars.githubusercontent.com/u/1568262?v=4)](https://github.com/ve3 "ve3 (1 commits)")[![WoLfulus](https://avatars.githubusercontent.com/u/412397?v=4)](https://github.com/WoLfulus "WoLfulus (1 commits)")

---

Tags

topological sorttopsortdependency resolving

###  Code Quality

TestsPHPUnit

### Embed Badge

![Health badge](/badges/wolfulus-topsort/health.svg)

```
[![Health](https://phpackages.com/badges/wolfulus-topsort/health.svg)](https://phpackages.com/packages/wolfulus-topsort)
```

###  Alternatives

[marcj/topsort

High-Performance TopSort/Dependency resolving algorithm

24715.6M50](/packages/marcj-topsort)

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)