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

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

• Basic Usage
• Installation
• Usage
• Warning
• Unit Testing
• Additional Notes
• Changelog
• Contributing
• Security
• Credits
• License

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

This package requires PHP 7.1.3 or higher as well as Laravel 5.6 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,
];

Warning

From Kemal Erdogan's article, "A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases":

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

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 descending from the specified model ID:

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

An ID and source must be provided. You may optionally provide the following arguments:

• $order: This will order the results by the number of hops. This can be 'asc' (default), 'desc', or something falsy for no ordering.
• $distinct: This determines whether or not the scope will return a distinct set of entries. Sometimes it's possible to have the same descendant appear via multiple paths. If it's desirable to get this in your result set multiple times, then pass false. It defaults to true.

Unit Testing

tbd

Additional Notes

Contributors may want to consider leveraging any of the following:

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

Changelog

Please see CHANGELOG for more information what has changed recently.

Contributing

Please see CONTRIBUTING for details.

Security

tbd

Credits

• Travis Elkins
• All contributors

Additionally:

• Kemal Erdogan and his article entitled, "A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases".
• xib and his MySQL stored procedures port (which is not currently used, but may be in a future version): xib/DAG_MySQL.sql

License

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