laravel-adjacency-list

Laravel Adjacency List

This Laravel Eloquent extension provides recursive relationships for trees and graphs using common table expressions (CTE).

Compatibility

• MySQL 8.0+
• MariaDB 10.2+
• PostgreSQL 9.4+
• SQLite 3.8.3+
• SQL Server 2008+
• SingleStore 8.1+ (only trees)

Installation

composer require staudenmeir/laravel-adjacency-list:"^1.0"

Use this command if you are in PowerShell on Windows (e.g. in VS Code):

composer require staudenmeir/laravel-adjacency-list:"^^^^1.0"

Versions

Usage

The package offers recursive relationships for traversing two types of data structures:

• Trees: One Parent per Node (One-to-Many)
• Graphs: Multiple Parents per Node (Many-to-Many)

Trees: One Parent per Node (One-to-Many)

Use the package to traverse a tree structure with one parent per node. Use cases might be recursive categories, a page hierarchy or nested comments.

Supports Laravel 5.5+.

• Getting Started
• Included Relationships
• Trees
• Filters
• Order
• Depth
• Path
• Custom Paths
• Nested Results
• Initial & Recursive Query Constraints
• Cycle Detection
• Additional Methods
• Custom Relationships
• Deep Relationship Concatenation
• Known Issues

Getting Started

Consider the following table schema for hierarchical data in trees:

Schema::create('users', function (Blueprint $table) {
    $table->id();
    $table->unsignedBigInteger('parent_id')->nullable();
});

Use the HasRecursiveRelationships trait in your model to work with recursive relationships:

class User extends Model
{
    use \Staudenmeir\LaravelAdjacencyList\Eloquent\HasRecursiveRelationships;
}

By default, the trait expects a parent key named parent_id. You can customize it by overriding getParentKeyName():

class User extends Model
{ 
    public function getParentKeyName()
    {
        return 'parent_id';
    }
}

By default, the trait uses the model's primary key as the local key. You can customize it by overriding getLocalKeyName():

class User extends Model
{
    public function getLocalKeyName()
    {
        return 'id';
    }
}

Included Relationships

The trait provides various relationships:

• ancestors(): The model's recursive parents.
• ancestorsAndSelf(): The model's recursive parents and itself.
• bloodline(): The model's ancestors, descendants and itself.
• children(): The model's direct children.
• childrenAndSelf(): The model's direct children and itself.
• descendants(): The model's recursive children.
• descendantsAndSelf(): The model's recursive children and itself.
• parent(): The model's direct parent.
• parentAndSelf(): The model's direct parent and itself.
• rootAncestor(): The model's topmost parent.
• rootAncestorOrSelf(): The model's topmost parent or itself.
• siblings(): The parent's other children.
• siblingsAndSelf(): All the parent's children.

$ancestors = User::find($id)->ancestors;

$users = User::with('descendants')->get();

$users = User::whereHas('siblings', function ($query) {
    $query->where('name', 'John');
})->get();

$total = User::find($id)->descendants()->count();

User::find($id)->descendants()->update(['active' => false]);

User::find($id)->siblings()->delete();

Trees

The trait provides the tree() query scope to get all models, beginning at the root(s):

$tree = User::tree()->get();

treeOf() allows you to query trees with custom constraints for the root model(s). Consider a table with multiple separate lists:

$constraint = function ($query) {
    $query->whereNull('parent_id')->where('list_id', 1);
};

$tree = User::treeOf($constraint)->get();

You can also pass a maximum depth:

$tree = User::tree(3)->get();

$tree = User::treeOf($constraint, 3)->get();

You can also chaperone tree relationships to load ancestors and parent relationships already present in the tree to (potentially) reduce N+1 queries:

$users = User::tree(3)->get();

$users->loadTreeRelationships();

Or with toTree():

$users = User::tree(1)->get();

$tree = $users->loadTreeRelationships()->toTree();

Filters

The trait provides query scopes to filter models by their position in the tree:

• hasChildren(): Models with children.
• hasParent(): Models with a parent.
• isLeaf()/doesntHaveChildren(): Models without children.
• isRoot(): Models without a parent.

$noLeaves = User::hasChildren()->get();

$noRoots = User::hasParent()->get();

$leaves = User::isLeaf()->get();
$leaves = User::doesntHaveChildren()->get();

$roots = User::isRoot()->get();

Order

The trait provides query scopes to order models breadth-first or depth-first:

• breadthFirst(): Get siblings before children.
• depthFirst(): Get children before siblings.

$tree = User::tree()->breadthFirst()->get();

$descendants = User::find($id)->descendants()->depthFirst()->get();

Depth

The results of ancestor, bloodline, descendant and tree queries include an additional depth column.

It contains the model's depth relative to the query's parent. The depth is positive for descendants and negative for ancestors:

$descendantsAndSelf = User::find($id)->descendantsAndSelf()->depthFirst()->get();

echo $descendantsAndSelf[0]->depth; // 0
echo $descendantsAndSelf[1]->depth; // 1
echo $descendantsAndSelf[2]->depth; // 2

Change the column name by overriding getDepthName() if your table already contains a depth column:

class User extends Model
{
    public function getDepthName()
    {
        return 'depth';
    }
}

Depth Constraints

You can use the whereDepth() query scope to filter models by their relative depth:

$descendants = User::find($id)->descendants()->whereDepth(2)->get();

$descendants = User::find($id)->descendants()->whereDepth('<', 3)->get();

Queries with whereDepth() constraints that limit the maximum depth still build the entire (sub)tree internally. Use withMaxDepth() to set a maximum depth that improves query performance by only building the requested section of the tree:

$descendants = User::withMaxDepth(3, function () use ($id) {
    return User::find($id)->descendants;
});

This also works with negative depths (where it's technically a minimum):

$ancestors = User::withMaxDepth(-3, function () use ($id) {
    return User::find($id)->ancestors;
});

Path

The results of ancestor, bloodline, descendant and tree queries include an additional path column.

It contains the dot-separated path of local keys from the query's parent to the model:

$descendantsAndSelf = User::find(1)->descendantsAndSelf()->depthFirst()->get();

echo $descendantsAndSelf[0]->path; // 1
echo $descendantsAndSelf[1]->path; // 1.2
echo $descendantsAndSelf[2]->path; // 1.2.3

Change the column name by overriding getPathName() if your table already contains a path column:

class User extends Model
{
    public function getPathName()
    {
        return 'path';
    }

You can also customize the path separator by overriding getPathSeparator():

class User extends Model
{
    public function getPathSeparator()
    {
        return '.';
    }
}

Custom Paths

You can add custom path columns to the query results:

class User extends Model
{
    public function getCustomPaths()
    {
        return [
            [
                'name' => 'slug_path',
                'column' => 'slug',
                'separator' => '/',
            ],
        ];
    }
}

$descendantsAndSelf = User::find(1)->descendantsAndSelf;

echo $descendantsAndSelf[0]->slug_path; // user-1
echo $descendantsAndSelf[1]->slug_path; // user-1/user-2
echo $descendantsAndSelf[2]->slug_path; // user-1/user-2/user-3

You can also reverse custom paths:

class User extends Model
{
    public function getCustomPaths()
    {
        return [
            [
                'name' => 'reverse_slug_path',
                'column' => 'slug',
                'separator' => '/',
                'reverse' => true,
            ],
        ];
    }
}

Nested Results

Use the toTree() method on a result collection to generate a nested tree:

$users = User::tree()->get();

$tree = $users->toTree();

This recursively sets children relationships:

[
  {
    "id": 1,
    "children": [
      {
        "id": 2,
        "children": [
          {
            "id": 3,
            "children": []
          }
        ]
      },
      {
        "id": 4,
        "children": [
          {
            "id": 5,
            "children": []
          }
        ]
      }
    ]
  }
]

Initial & Recursive Query Constraints

You can add custom constraints to the CTE's initial and recursive query. Consider a query where you want to traverse a tree while skipping inactive users and their descendants:

$tree = User::withQueryConstraint(function (Builder $query) {
   $query->where('users.active', true);
}, function () {
   return User::tree()->get();
});

You can also add a custom constraint to only the initial or recursive query using withInitialQueryConstraint()/ withRecursiveQueryConstraint().

Cycle Detection

If your tree contains cycles, you need to enable cycle detection to prevent infinite loops:

class User extends Model
{
    public function enableCycleDetection(): bool
    {
        return true;
    }
}

You can also retrieve the start of a cycle, i.e., the first duplicate node. With this option, the query results include an is_cycle column that indicates whether the node is part of a cycle:

class User extends Model
{
    public function enableCycleDetection(): bool
    {
        return true;
    }

    public function includeCycleStart(): bool
    {
        return true;
    }
}

$users = User::find($id)->descendants;

foreach ($users as $user) {
    dump($user->is_cycle);
}

Additional Methods

The trait also provides methods to check relationships between models:

• isChildOf(Model $model): Checks if the current model is a child of the given model.
• isParentOf(Model $model): Checks if the current model is a parent of the given model.
• getDepthRelatedTo(Model $model): Returns the depth of the current model related to the given model.

$rootUser = User::create(['parent_id' => null]); 
$firstLevelUser = User::create(['parent_id' => $rootUser->id]); 
$secondLevelUser = User::create(['parent_id' => $firstLevelUser->id]);  

$isChildOf = $secondLevelUser->isChildOf($firstLevelUser); // Output: true
$isParentOf = $rootUser->isParentOf($firstLevelUser); // Output: true
$depthRelatedTo = $secondLevelUser->getDepthRelatedTo($rootUser); // Output: 2

Custom Relationships

You can also define custom relationships to retrieve related models recursively.

• HasManyOfDescendants
• BelongsToManyOfDescendants
• MorphToManyOfDescendants
• MorphedByManyOfDescendants
• Intermediate Scopes
• [Usage outside of Larav