PHPackages                             telkins/laravel-dag-manager - 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. [Database & ORM](/categories/database)
4. /
5. telkins/laravel-dag-manager

ActiveLibrary[Database & ORM](/categories/database)

telkins/laravel-dag-manager
===========================

A SQL-based Directed Acyclic Graph (DAG) solution for Laravel.

v4.0.1(1y ago)325.0k10[4 issues](https://github.com/telkins/laravel-dag-manager/issues)MITPHPPHP ^8.2CI passing

Since May 3Pushed 2mo ago2 watchersCompare

[ Source](https://github.com/telkins/laravel-dag-manager)[ Packagist](https://packagist.org/packages/telkins/laravel-dag-manager)[ RSS](/packages/telkins-laravel-dag-manager/feed)WikiDiscussions main Synced 1mo ago

READMEChangelog (10)Dependencies (6)Versions (29)Used By (0)

A SQL-based Directed Acyclic Graph (DAG) solution for Laravel
=============================================================

[](#a-sql-based-directed-acyclic-graph-dag-solution-for-laravel)

[![Latest Stable Version](https://camo.githubusercontent.com/91d8e74a528d8d7e55c66ca2f2856dbf78d921bd110fa47f2c7288f00962f745/68747470733a2f2f706f7365722e707567782e6f72672f74656c6b696e732f6c61726176656c2d6461672d6d616e616765722f762f737461626c65)](https://packagist.org/packages/telkins/laravel-dag-manager)[![run tests](https://github.com/telkins/laravel-dag-manager/workflows/run%20tests/badge.svg)](https://github.com/telkins/laravel-dag-manager/workflows/run%20tests/badge.svg)[![Total Downloads](https://camo.githubusercontent.com/091938a22d549e916da783b9702d1441038b2e9bf2eedecc2c7ae3664518fd16/68747470733a2f2f706f7365722e707567782e6f72672f74656c6b696e732f6c61726176656c2d6461672d6d616e616765722f646f776e6c6f616473)](https://packagist.org/packages/telkins/laravel-dag-manager)[![License](https://camo.githubusercontent.com/d6b5e87472a3df0768d5418f6f5b2880241c0805b52458d8686502152800e1da/68747470733a2f2f706f7365722e707567782e6f72672f74656c6b696e732f6c61726176656c2d6461672d6d616e616765722f6c6963656e7365)](https://packagist.org/packages/telkins/laravel-dag-manager)

This package allows you to create, persist, and remove directed acyclic graphs.

- [Basic Usage](#basic-usage)
- [Installation](#installation)
- [Usage](#usage)
- [Warning](#warning)
- [Testing](#testing)
- [Additional Notes](#additional-notes)
- [Changelog](#changelog)
- [Contributing](#contributing)
- [Security](#security)
- [Credits](#credits)
- [License](#license)

Basic Usage
-----------

[](#basic-usage)

Creating a direct edge:

```
$newEdges = dag()->createEdge($startVertex, $endVertex, $source);
// $newEdges contains all new edges, including the specified direct edge, that were created as a result of the request.
```

Deleting a direct edge:

```
$deleted = dag()->deleteEdge($startVertex, $endVertex, $source);
// $deleted is true if any edges were deleted as a result of the request, false otherwise.
```

Installation
------------

[](#installation)

The latest version of this package requires PHP 8.2 or higher as well as Laravel 12.0 or higher.

You can install the package via composer:

```
composer require telkins/laravel-dag-manager
```

The package will automatically register itself.

You can publish the migration with:

```
php artisan vendor:publish --provider="Telkins\Dag\Providers\DagServiceProvider" --tag="migrations"
```

Note: The default migration assumes you are using integers for your DAG edge IDs.

You can optionally publish the config file with:

```
php artisan vendor:publish --provider="Telkins\Dag\Providers\DagServiceProvider" --tag="config"
```

This is the contents of the published config file:

```
return [
    /**
     *-------------------------------------------------------------------------
     * Max Hops
     *-------------------------------------------------------------------------
     *
     * This value represents the maximum number of hops that are allowed where
     * hops "[i]ndicates how many vertex hops are necessary for the path; it is
     * zero for direct edges".
     *
     * The more hops that are allowed (and used), then the more DAG edges will
     * be created.  This will have an increasing impact on performance, space,
     * and memory.  Whether or not it's negligible, noticeable, or impactful
     * depends on a variety of factors.
     */
    'max_hops' => 5,

    /**
     *-------------------------------------------------------------------------
     * Default Database Connection Name
     *-------------------------------------------------------------------------
     *
     * This is the name of the database connection where the dag table
     * can be found.
     *
     * Set to `null` to use the default connection.
     */
    'default_database_connection_name' => null,

    /**
     *-------------------------------------------------------------------------
     * Table Name
     *-------------------------------------------------------------------------
     *
     * This is the name of the table where the dag structure
     * will be stored.
     */
    'table_name' => 'dag_edges',
];
```

Warning
-------

[](#warning)

From Kemal Erdogan's article, ["A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases"](https://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o):

> In theory, the size of the transitive closure set of a fair DAG can be very large with this model, well beyond the millions. The maximum number of edges for a given DAG itself is a research topic in Graph Theory, but my practical tests show that there exist DAGs with 100 vertices and 300 edges whose transitive closure would create well beyond 20,000,000 rows with this algorithm.

Please be mindful of this when creating "excessively" large and/or complex graphs.

Usage
-----

[](#usage)

For Eloquent models that are "DAG managed", you can add the `Telkins\Models\Traits\IsDagManaged` trait:

```
use Illuminate\Database\Eloquent\Model;
use Telkins\Models\Traits\IsDagManaged;

class MyModel extends Model
{
    use IsDagManaged;

    // ...
}
```

This will allow you to easily access certain functionality from your model class.

To apply a scope that only includes models that are descendants of the specified model ID:

```
$descendants = MyModel::dagDescendantsOf($myModel->id, 'my-source')->get();
```

An ID and source must be provided.

Likewise, to apply a scope that only includes models that are ancestors of the specified model ID:

```
$ancestors = MyModel::dagAncestorsOf($myModel->id, 'my-source')->get();
```

Again, an ID and source must be provided.

Finally, one can apply a scope that will get both ancestors and descendants:

```
$ancestors = MyModel::dagRelationsOf($myModel->id, 'my-source')->get();
```

Each of the aforementioned methods also allow the caller to constrain the results based on the number of hops. So, if you want to get the immediate children of the specified model ID, then you could do the following:

```
$descendants = MyModel::dagDescendantsOf($myModel->id, 'my-source', 0)->get();
```

And, of course, in order to get the parents and grandparents of the specified model ID, you could do the following:

```
$ancestors = MyModel::dagAncestorsOf($myModel->id, 'my-source', 1)->get();
```

Not providing the `$maxHops` parameter means that all descendants, ancestors, or relations will be returned.

### Custom DAG edge model

[](#custom-dag-edge-model)

You can use your own model class if you need to customise the behavior of the DAG edge model.

Your custom model class must extend the `Telkins\Dag\Models\DagEdge` class:

```
namespace App\Models;

use Telkins\Dag\Models\DagEdge as BaseModel;

class MyDagEdge extends BaseModel
{
...
```

You can then specify the fully qualified class name of your custom model in the package config file.

```
// config/laravel-dag-manager.php
...
'edge_model' => \App\Models\MyDagEdge::class,
...
```

Testing
-------

[](#testing)

```
composer test
```

Additional Notes
----------------

[](#additional-notes)

Contributors may want to consider leveraging any of the following:

- [relaxedws/lca](https://github.com/relaxedws/lca): A PHP Library to find Lowest Common ancestor from a Directed Acyclic Graph.
- [clue/graph](https://github.com/clue/graph): A mathematical graph/network library written in PHP.
- [graphp/algorithms](https://github.com/graphp/algorithms): Graph algorithms in PHP, a collection of common (and not so common) ones.

Changelog
---------

[](#changelog)

Please see [CHANGELOG](CHANGELOG.md) for more information what has changed recently.

Contributing
------------

[](#contributing)

Please see [CONTRIBUTING](CONTRIBUTING.md) for details.

Security
--------

[](#security)

tbd

Credits
-------

[](#credits)

- [Travis Elkins](https://github.com/telkins)
- [All contributors](../../contributors)

Additionally:

- Kemal Erdogan and his article entitled, ["A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases"](https://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o).
- [xib](https://github.com/xib) and his MySQL stored procedures port (which is not currently used, but may be in a future version): [xib/DAG\_MySQL.sql](https://gist.github.com/xib/21786eeaa970911f0693)

License
-------

[](#license)

The MIT License (MIT). Please see [License File](LICENSE) for more information.

###  Health Score

55

—

FairBetter than 98% of packages

Maintenance67

Regular maintenance activity

Popularity34

Limited adoption so far

Community18

Small or concentrated contributor base

Maturity86

Battle-tested with a long release history

 Bus Factor1

Top contributor holds 80.5% 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 ~97 days

Recently: every ~186 days

Total

27

Last Release

395d ago

Major Versions

v0.10.0 → v1.0.02021-01-02

v1.3.0 → v2.0.02023-03-28

v2.0.0 → v3.0.02024-08-26

v3.0.0 → v4.0.02025-04-12

PHP version history (7 changes)v0.0.1PHP >=7.1

v0.0.3PHP >=7.1.3

v0.1.1PHP ^7.2

v1.0.0PHP ^7.4 || ^8.0

v1.1.0PHP ^7.4|^8.0

v2.0.0PHP ^8.1

v3.0.0PHP ^8.2

### Community

Maintainers

![](https://www.gravatar.com/avatar/d0099a02e09e4fd03c5aca40dd7cc943391d0333009959c276321e59f6423965?d=identicon)[travis.elkins](/maintainers/travis.elkins)

---

Top Contributors

[![telkins](https://avatars.githubusercontent.com/u/53731?v=4)](https://github.com/telkins "telkins (95 commits)")[![akalongman](https://avatars.githubusercontent.com/u/423050?v=4)](https://github.com/akalongman "akalongman (12 commits)")[![Nika-Simonishvili](https://avatars.githubusercontent.com/u/89088777?v=4)](https://github.com/Nika-Simonishvili "Nika-Simonishvili (5 commits)")[![gbuckingham89](https://avatars.githubusercontent.com/u/1455253?v=4)](https://github.com/gbuckingham89 "gbuckingham89 (3 commits)")[![dealense7](https://avatars.githubusercontent.com/u/60123889?v=4)](https://github.com/dealense7 "dealense7 (1 commits)")[![rupertraphael](https://avatars.githubusercontent.com/u/19609578?v=4)](https://github.com/rupertraphael "rupertraphael (1 commits)")[![ankaraWyaro](https://avatars.githubusercontent.com/u/157008301?v=4)](https://github.com/ankaraWyaro "ankaraWyaro (1 commits)")

---

Tags

dagdirected-acyclic-graphhacktoberfestlaravelsqllaravelsqlgraphDAGtelkinsacyclicdirectedlaravel-dag-manager

###  Code Quality

TestsPHPUnit

### Embed Badge

![Health badge](/badges/telkins-laravel-dag-manager/health.svg)

```
[![Health](https://phpackages.com/badges/telkins-laravel-dag-manager/health.svg)](https://phpackages.com/packages/telkins-laravel-dag-manager)
```

###  Alternatives

[illuminate/database

The Illuminate Database package.

2.8k52.4M9.4k](/packages/illuminate-database)[watson/validating

Eloquent model validating trait.

9723.3M47](/packages/watson-validating)[dyrynda/laravel-model-uuid

This package allows you to easily work with UUIDs in your Laravel models.

4802.8M8](/packages/dyrynda-laravel-model-uuid)[clickbar/laravel-magellan

This package provides functionality for working with the postgis extension in Laravel.

423715.4k1](/packages/clickbar-laravel-magellan)[reedware/laravel-relation-joins

Adds the ability to join on a relationship by name.

2121.2M13](/packages/reedware-laravel-relation-joins)[outerweb/settings

Application wide settings stored in your database

4899.2k5](/packages/outerweb-settings)

PHPackages © 2026

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