marcobuschini/mlb-dag-bundle

This bundle provides entities, and methods to handle directed acyclic graphs.

dev-master 2018-07-28 21:54 UTC

Requires

• php: >=5.3.1
• symfony/symfony: ~2.3.41 || ~2.7.13 || ~2.8.6 || ~3.0.6

Requires (Dev)

• doctrine/data-fixtures: ~1.0
• doctrine/doctrine-bundle: ~1.0
• doctrine/doctrine-fixtures-bundle: ^2.2
• doctrine/orm: ~2.3 || ~2.5
• phpunit/php-code-coverage: ~2.2
• phpunit/phpunit: ~4.1
• satooshi/php-coveralls: ~1.0

MIT

• Marco L. Buschini

• graph
• DAG
• acyclic

README

marcobuschini/MLBDagBundle

When managing complex relationship between entities belonging to the real world we often see that they cannot fit simple data models, such as lists, maps, and even trees.

This Symony2 bundle implements a Doctrine data model that allows an application to manage Directed Acyclic Graphs by using both an adjacency list, and a full transitive closure for indirect edges.

A DAG is a set of nodes connected by a set of oriented edges so that no closed loop (cycle) can be created in the data structure. This structure is best handled with an adjacency list, that is a list of edges connecting pairs of nodes (edge E connects node A to node B, but not the opposite). To prevent large amounts of queries to find if node B is reachable from node A a full transitive closure is implemented, that is a list of indirect edges is managed by the bundle. So that if node A connects to node B that connects to node C, an indirect edge from node A to node C is managed by the bundle's logic.

It is important to note that the data structure MUST NOT be modified outside of this bundle as the logic for preventing cycles, and for creating indirect edges IS NOT handled by the database, but by the bundle itself.