Download the PHP package telkins/laravel-dag-manager without Composer

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
• Testing
• Additional Notes
• Changelog
• Contributing
• Security
• Credits
• License

Basic Usage

Creating a direct edge:

Deleting a direct edge:

Installation

This package requires PHP 7.2 or higher as well as Laravel 6.0 or higher.

You can install the package via composer:

The package will automatically register itself.

You can publish the migration with:

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

You can optionally publish the config file with:

This is the contents of the published config file:

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:

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:

An ID and source must be provided.

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

Again, an ID and source must be provided.

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

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:

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

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

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\Models\DagEdge class:

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

Testing

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.