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.1(2mo ago)44.5M↓24.1%12MITPHPPHP >=7.0

Since Apr 13Pushed 2mo ago7 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 2d ago

READMEChangelogDependencies (8)Versions (5)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

56

—

FairBetter than 97% of packages

Maintenance85

Actively maintained with recent releases

Popularity47

Moderate usage in the ecosystem

Community23

Small or concentrated contributor base

Maturity58

Maturing project, gaining track record

 Bus Factor2

2 contributors hold 50%+ of commits

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 ~1279 days

Total

3

Last Release

78d 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)")[![sevka](https://avatars.githubusercontent.com/u/772210?v=4)](https://github.com/sevka "sevka (2 commits)")[![ve3](https://avatars.githubusercontent.com/u/1568262?v=4)](https://github.com/ve3 "ve3 (1 commits)")[![kelunik](https://avatars.githubusercontent.com/u/2743004?v=4)](https://github.com/kelunik "kelunik (1 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)")

---

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

24816.9M66](/packages/marcj-topsort)[panakour/filament-flat-page

This is my package filament-flat-page

121.7k](/packages/panakour-filament-flat-page)

PHPackages © 2026

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