PHPackages                             vaimo/topological-sort - 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. vaimo/topological-sort

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

vaimo/topological-sort
======================

High-Performance TopSort/Dependency resolving algorithm (compatibility version to work with 7.0 - 7.2)

2.0.0(9mo ago)44.2M—6.2%12MITPHPPHP >=7.0

Since Apr 13Pushed 9mo ago9 watchersCompare

[ Source](https://github.com/vaimo/topological-sort)[ Packagist](https://packagist.org/packages/vaimo/topological-sort)[ GitHub Sponsors](https://github.com/marcj)[ RSS](/packages/vaimo-topological-sort/feed)WikiDiscussions master Synced 1mo ago

READMEChangelogDependencies (4)Versions (3)Used By (2)

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

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

**NOTE: this is a direct copy of the marcj/topsort with the only difference being the guaranteed compatibility with PHP 7.0 - 7.2**

[![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](https://packagist.org/packages/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

48

—

FairBetter than 95% of packages

Maintenance56

Moderate activity, may be stable

Popularity47

Moderate usage in the ecosystem

Community22

Small or concentrated contributor base

Maturity56

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 52% 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 ~2301 days

Total

2

Last Release

290d ago

Major Versions

1.0.0 → 2.0.02025-08-01

PHP version history (2 changes)1.0.0PHP >=5.3

2.0.0PHP >=7.0

### Community

Maintainers

![](https://www.gravatar.com/avatar/695d3feefa2118fb7005d5c6b3bbccb2e164ab48bb1a3eb64b3e7595298ce9e4?d=identicon)[vaimo](/maintainers/vaimo)

---

Top Contributors

[![marcj](https://avatars.githubusercontent.com/u/450980?v=4)](https://github.com/marcj "marcj (13 commits)")[![totten](https://avatars.githubusercontent.com/u/1336047?v=4)](https://github.com/totten "totten (5 commits)")[![jooname](https://avatars.githubusercontent.com/u/36262953?v=4)](https://github.com/jooname "jooname (3 commits)")[![ve3](https://avatars.githubusercontent.com/u/1568262?v=4)](https://github.com/ve3 "ve3 (1 commits)")[![thebuccaneersden](https://avatars.githubusercontent.com/u/512767?v=4)](https://github.com/thebuccaneersden "thebuccaneersden (1 commits)")[![kelunik](https://avatars.githubusercontent.com/u/2743004?v=4)](https://github.com/kelunik "kelunik (1 commits)")[![tomvlk](https://avatars.githubusercontent.com/u/3877688?v=4)](https://github.com/tomvlk "tomvlk (1 commits)")

---

Tags

topological sorttopsortdependency resolving

###  Code Quality

TestsPHPUnit

Code StylePHP\_CodeSniffer

### Embed Badge

![Health badge](/badges/vaimo-topological-sort/health.svg)

```
[![Health](https://phpackages.com/badges/vaimo-topological-sort/health.svg)](https://phpackages.com/packages/vaimo-topological-sort)
```

###  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)