Get a Tree from a Graph (Many-toMany) Relationship and filter it

[nilskretschmer]

Hi,

I really like this package for being simple and easy on resources, because it uses already existing functionality of common databases. Thanks for this!

Currently I am trying to use this package for the following use case:

Setup

I have the following setup in my app:

1. Page-Model -> BelongsToMany Components
2. Component-Model -> BelongsToMany Pages
3. Component-Model -> hasChildren (other components, using children()-function of this library)
4. A "Component-Tree" could be different for each page, but I can attach/detach already existing Components and set relations.

So a Component could be related with one or many pages. A component could have subcomponents (children). The Components' Children can be different for each page.

You could say that with this setup you can create pages and components independently of each other and building unique page<->component relationships while still re-use existing components.

Migrations

pages

    {
        Schema::create('pages', function (Blueprint $table) {
            $table->id();
            $table->string('title');
            $table->text('description');
            $table->string('url');
            $table->json('attributes')->nullable();
            $table->unsignedBigInteger('parent_id')->nullable();
            $table->timestamps();
        });
    }

components

    public function up(): void
    {
        Schema::create('components', function (Blueprint $table) {
            $table->id();
            $table->string('name');
            $table->string('type');
            $table->jsonb('attributes')->nullable();
            $table->timestamps();
        });
    }

component_page

    public function up(): void
    {
        Schema::create('component_page', function (Blueprint $table) {
            $table->timestamps();
            $table->primary(['page_id', 'component_id']);
            $table->foreignId('page_id')
                ->references('id')->on('pages')
                ->constrained()
                ->onUpdate('cascade')
                ->onDelete('cascade');
            $table->foreignId('component_id')
                ->references('id')->on('components')
                ->constrained()
                ->onUpdate('cascade')
                ->onDelete('cascade');
            $table->integer('position');
            $table->unique(['page_id', 'position']);
        });
    }

component_component (associate components with components)

    public function up(): void
    {
        Schema::create('component_component', function (Blueprint $table) {
            $table->id();
            $table->integer('child_position');
            $table->foreignId('parent_id')
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->foreignId('child_id')
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->foreignId('page_id')
            ->references('id')->on('pages')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->timestamps();
        });
    }

The Problems

Now imagine you want to return all components and their children to the frontend where the pivot (component_component-Table) has the same page_id like the page you are on:

    public function show(Page $page)
    {
        $page->load(['components.children' => function ($query) use ($page) {
            $query->wherePivot('page_id', $page->id);
        }]);

        return Inertia::render('Admin/Pages/Edit', [
            'page' => $page,
    ]);
    }

And this data in the component_component table:

Expected:

[
    "id": "parent_id"
    "children" : [
        {
            "id": "child_id"
            "children": [
                {
                    "id": "nested_child_id"
                }
             ]
         }
     ]
]

But instead it returns two parents with one nested children each. Instead there should only be one parent with one children and that children has another children nested inside.

Questions

1. How to build a tree in a Graph (Many-To-Many)? So how to get a page component tree in this example?
2. How to add query constraints to the tree? Like return only those children that have the same page_id in their pivot table?

[staudenmeir]

Hi @nilskretschmer,

But instead it returns two parents with one nested children each.

Can you share the result (as compared to the expected one)?

[nilskretschmer]

Hey @staudenmeir,

thank you so much for reaching out to me.

the result was:

[
    "id": "parent_id"
    "children" : [
        {
            "id": "child_id"
            "children": [
             ]
         },
        {
            "id": "another_child_id"
            "children": [
             ]
         },
     ]
]

So instead of being nested the children were neighbours. I just realised the problem was that the first child had indeed children - but they weren't fetched from the database. So the result is correct - it was just not recursive (the children of the first child were missing in the result).

I also noticed that I could change my database schema and completely drop the component_page table (or change it) and put all component/page relations into the component_component-table. This table has all informations I need to generate a page tree. The algorithm would look somehow like:

1. Get all components of a page that have the same page_id, like the page I want to return and have no parent_id -> these are the "root"-components of the page.
2. Load all children of the root-components recursively
3. Return the page tree including all root-components and their nested children to the frontend

I mentioned some problems with this approach using the library:

• There isn't any toTree() or tree() method for graphs (components can belong to many pages, pages have many components)
• Loading children using the children-relationship or children() method is not recursive
• Using descendants I get all children recursively but without a tree structure - all children are just flat in the array
• I noticed that when I put children inside the protected $with attribute in my Component-Model - all children are returned recursively just like I need it to. But this also returns children that have relations with other pages which is not what I need regarding my use case (I only need the component tree for each page separately)

So I am kinda stuck here. I also experimented by implementing some recusrive relationship methods on my own, but I think this leads to loosing the positive impact of cte and this library at all.

Any suggestions?

[staudenmeir]

Are you on Laravel 10? I pushed an experimental toGraph() method into the to-graph branch. Please update the package's dependency to dev-to-graph (instead of ^1.0) and test the method.

If it works for you, we can take a look at the remaining questions/issues.

[nilskretschmer]

Thank you so much for your quick response and the new helper method. I am not quite sure how the method should be used in our context:

Should I use the toGraph() method on the page or on the components? I think for our use case to work it needs to be called on the page, because the method should return all components that are associated with the page and all their children (nested inside each component).

Could you please provide a basic example on how to use the method in this use case? Assuming there is a pivot table migration which "connects" pages to components and component parent-child-relations to each other:

    public function up(): void
    {
        Schema::create('component_page', function (Blueprint $table) {
            $table->id();
            $table->integer('child_position');
            $table->foreignId('parent_id')
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->foreignId('child_id')
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->foreignId('page_id')
            ->references('id')->on('pages')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->timestamps();
        });
    }

[staudenmeir]

Assuming there is a pivot table migration which "connects" pages to components and component parent-child-relations to each other:

Did you remove the component_component table and merge it into component_page?

[nilskretschmer]

Not yet. But I am thinking of merging them together, because I think one table should be enough to contain all information I need. But I am not sure if this is working well with this library.

The reason for that is that the examples of the library assume that models have recursive relationships with themselves. In my case it is a bit different, because Pages have a many-to-many relation with Components and each page can have a different tree of Components (with their children). So it is like a Graph of Components with the constraint of the page_id - and I am not quite sure how to implement it with the help of this library.

[staudenmeir]

Can you share some sample data for the new schema? How do you know which components are the root components for a page?

[nilskretschmer]

You are correct. There is still an issue with the schema. I first thought that all root components are simply those entries in the pivot table that do not have a parent_id set - but the reference to the component itself is missing then:

So maybe I would also need to add something like a self-referencing self_id to the table, too? Like:

public function up(): void
{
    Schema::create('component_page', function (Blueprint $table) {
        $table->id();
        $table->integer('position');
        $table->foreignId('parent_id')
        ->references('id')->on('components')
        ->nullable()
        ->constrained()
        ->onUpdate('cascade')
        ->onDelete('cascade');
        $table->foreignId('self_id')
        ->references('id')->on('components')
        ->constrained()
        ->onUpdate('cascade')
        ->onDelete('cascade');
        $table->foreignId('child_id')
        ->references('id')->on('components')
        ->nullable()
        ->constrained()
        ->onUpdate('cascade')
        ->onDelete('cascade');
        $table->foreignId('page_id')
        ->references('id')->on('pages')
        ->constrained()
        ->onUpdate('cascade')
        ->onDelete('cascade');
        $table->timestamps();
    });
}

And then there are 3 possibilites:

1. A Page has only root components (the pivot table contains only self-referencing entries. No entry has child_id nor parent_id set)
2. A Page has root components that have children (the pivot table also contains entries where the parent_ids are set on items)
3. A Page has root components whose children have children (recursive relationship. The pivot table also contains entries where child_id, parent_id and self_id is set)

For each page that I want to return the component graph for the page_id must match the Page whose Graph I am returning from my PageController.

[staudenmeir]

So maybe I would also need to add something like a self-referencing self_id to the table, too?

What query would you use to get the root components with this structure?

With the original database structure, you can use toGraph() like this:

$constraint = function ($query) use ($page) {
    $ids = $page->components()->pluck('id');

    $query->whereIn('id', $ids);
};

$components = Component::subgraph($constraint)->get();
$graph = $components->toGraph();

There's a more elegant approach, but it requires an additional package. If you keep the original database structure, I can document it.

[nilskretschmer]

What query would you use to get the root components with this structure?

It would be something like:

In the page model:

public function rootComponents()
{
    return $this->belongsToMany(Component::class)
                ->wherePivotNull('parent_id');
}

And then:

$rootComponents = $page->rootComponents;

Assuming that the Page-Model has a many-to-many relation to components using the intermediate table structure shown above. Self-Id and PageId are the foreign keys in that table that connect components and pages together.

But following your suggestion using the original structure looks also interesting. So it would be very helpful if you could document it. Which additional package do you mean?

[staudenmeir]

So it would be very helpful if you could document it. Which additional package do you mean?

Never mind, I just saw that the more elegant approach doesn't work in your case.

I've released a new version with the toTree() method for graphs (I decided to rename it from toGraph()).

[nilskretschmer]

Thanks for your help!

I will give it a try. I am unsure which database schema will be better but I think I try both. Currently I am leaning towards the version of having only one intermediate table containing everything, because it may be possible to use only one query for the tree.

I will post my result if it works.

Also I just saw that you merged the toTree-method into master and there is still the toGraph-Branch - So which branch should I use for the toTree()-method? I think the most consistent way would be to use the 1.12-version-branch?

[staudenmeir]

Also I just saw that you merged the toTree-method into master and there is still the toGraph-Branch - So which branch should I use for the toTree()-method? I think the most consistent way would be to use the 1.12-version-branch?

Don't specify a branch but revert the package version in your composer.json back to the original ^1.0. I'll delete the to-graph soon. The 1.12 branch is for Laravel 9.

[nilskretschmer]

So I tried to get it work using your examples but I still have errors. I went with the schema using only two tables first:

components-Table:

<?php

use Illuminate\Database\Migrations\Migration;
use Illuminate\Database\Schema\Blueprint;
use Illuminate\Support\Facades\Schema;

return new class extends Migration
{
    /**
     * Run the migrations.
     */
    public function up(): void
    {
        Schema::create('components', function (Blueprint $table) {
            $table->id();
            $table->string('name');
            $table->string('type');
            $table->jsonb('attributes')->nullable();
            $table->timestamps();
        });
    }

    /**
     * Reverse the migrations.
     */
    public function down(): void
    {
        Schema::dropIfExists('components');
    }
};

pages-Table:

<?php

use Illuminate\Database\Migrations\Migration;
use Illuminate\Database\Schema\Blueprint;
use Illuminate\Support\Facades\Schema;

return new class extends Migration
{
    /**
     * Run the migrations.
     */
    public function up(): void
    {
        Schema::create('pages', function (Blueprint $table) {
            $table->id();
            $table->string('title');
            $table->text('description');
            $table->string('url');
            $table->json('attributes')->nullable();
            $table->unsignedBigInteger('parent_id')->nullable();
            $table->timestamps();
        });
    }

    /**
     * Reverse the migrations.
     */
    public function down(): void
    {
        Schema::dropIfExists('pages');
    }
};

And the component_page-Table:

<?php

use Illuminate\Database\Migrations\Migration;
use Illuminate\Database\Schema\Blueprint;
use Illuminate\Support\Facades\Schema;

return new class extends Migration
{
    /**
     * Run the migrations.
     */
    public function up(): void
    {
        Schema::create('component_page', function (Blueprint $table) {
            $table->timestamps();
            $table->primary(['page_id', 'component_id']);
            $table->foreignId('page_id')
                ->references('id')->on('pages')
                ->constrained()
                ->onUpdate('cascade')
                ->onDelete('cascade');
            $table->foreignId('component_id')
                ->references('id')->on('components')
                ->constrained()
                ->onUpdate('cascade')
                ->onDelete('cascade');
            $table->integer('position');
            $table->foreignId('parent_id')
            ->nullable()
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->foreignId('child_id')
            ->nullable()
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
        });
    }

    /**
     * Reverse the migrations.
     */
    public function down(): void
    {
        Schema::dropIfExists('component_page');
    }
};

I filled in some data and the intermediate table now has these entries:

The entries without parent_id or child_id are the "root components" of each page.

As you can see, Page 1 has 3 root components and component with id 5 has a sub-component (id 6) which also has a sub component (id 7).

This is how I return that info in my controller:

    public function edit(Page $page)
    {
        $constraint = function ($query) use ($page) {
            $ids = $page->rootComponents()->pluck('id');
        
            $query->whereIn('id', $ids);
        };

        $pageComponents = Component::subgraph($constraint)->get();
        $componentTree = $pageComponents->toTree();

        return Inertia::render('Admin/Pages/Edit', [
            'page' => $page,
            'page.components' => $componentTree,
            'pages' => Page::all(),
            'components' => Component::all(),
        ]);
    }

For page 1 this is working fine and the tree looks like expected.

But the result for page 2 is not what is expected. It gives:

 "page": {
      "id": 2,
      "title": "Page 2",
      "description": "Page 2",
      "url": "page2",
      "attributes": null,
      "parent_id": null,
      "created_at": "2024-01-06T19:32:20.000000Z",
      "updated_at": "2024-01-06T19:32:20.000000Z",
      "components": [
        {
          "id": 3,
          "name": "Main Navigation",
          "type": "navigation",
          "attributes": [],
          "created_at": "2024-01-06T15:58:14.000000Z",
          "updated_at": "2024-01-06T15:58:14.000000Z",
          "depth": 0,
          "path": "3",
          "pivot_parent_id": null,
          "pivot_child_id": null,
          "pivot_position": null,
          "children": []
        },
        {
          "id": 5,
          "name": "Main Textblock",
          "type": "textblock",
          "attributes": {
            "content": "This is the main textblock."
          },
          "created_at": "2024-01-06T15:58:56.000000Z",
          "updated_at": "2024-01-06T15:58:56.000000Z",
          "depth": 0,
          "path": "5",
          "pivot_parent_id": null,
          "pivot_child_id": null,
          "pivot_position": null,
          "children": [
            {
              "id": 6,
              "name": "Sub Textblock",
              "type": "textblock",
              "attributes": {
                "content": "This is a nested Textblock"
              },
              "created_at": "2024-01-06T15:59:16.000000Z",
              "updated_at": "2024-01-06T15:59:16.000000Z",
              "depth": 1,
              "path": "5.6",
              "pivot_parent_id": 5,
              "pivot_child_id": 6,
              "pivot_position": 1,
              "children": [
                {
                  "id": 7,
                  "name": "Another Sub Textblock",
                  "type": "textblock",
                  "attributes": {
                    "content": "This is another nested Textblock"
                  },
                  "created_at": "2024-01-06T15:59:30.000000Z",
                  "updated_at": "2024-01-06T15:59:30.000000Z",
                  "depth": 2,
                  "path": "5.6.7",
                  "pivot_parent_id": 6,
                  "pivot_child_id": 7,
                  "pivot_position": 1,
                  "children": []
                }
              ]
            }
          ]
        }
      ]
    },

So I also get the child components that belong to page 1 which is wrong in the scope of my use case. All children that do not have the page_id set to 2 in the intermediate table shouldn't be returned as part of the tree. I think that is something that I still miss in your examples or in the documentation of the package: How to filter the tree based on a constraint? In my case the constaint is the page_id in the pivot table.

Also I now see that the schema using only two tables has some drawbacks: The child_id is never set on the root components - even if they have children. So I am thinking of going back to the three table schema I had first.

But I think this will not solve the problem of how to get a "component tree" for each page where each page could have a completely different "component tree" but still "reuse" the already existing components (that is why I need a many-to-many relationship here).

Can you help me out again?

[staudenmeir]

Try adding a custom recursive query constraint:
https://github.com/staudenmeir/laravel-adjacency-list#graphs-recursive-query-constraints

$pageComponents = Component::withRecursiveQueryConstraint(function (Builder $query) use ($page) {
   $query->where('component_page.page_id', $page->id);
}, function () use ($constraint) {
   return Component::subgraph($constraint)->get();
});

[nilskretschmer]

Thanks again. So there is no built-in way of handling this, correct?

So I started implementing it myself, but I still have problems to get the position data for all components in the tree.

I changed my table schema back to the table schema from the beginning:

    public function up(): void
    {
        Schema::create('pages', function (Blueprint $table) {
            $table->id();
            $table->string('title');
            $table->text('description');
            $table->string('url');
            $table->json('attributes')->nullable();
            $table->unsignedBigInteger('parent_id')->nullable();
            $table->timestamps();
        });
    }
    
    public function up(): void
    {
        Schema::create('components', function (Blueprint $table) {
            $table->id();
            $table->string('name');
            $table->string('type');
            $table->jsonb('attributes')->nullable();
            $table->timestamps();
        });
    }

    public function up(): void
    {
        Schema::create('component_page', function (Blueprint $table) {
            $table->timestamps();
            $table->primary(['page_id', 'component_id']);
            $table->foreignId('page_id')
                ->references('id')->on('pages')
                ->constrained()
                ->onUpdate('cascade')
                ->onDelete('cascade');
            $table->foreignId('component_id')
                ->references('id')->on('components')
                ->constrained()
                ->onUpdate('cascade')
                ->onDelete('cascade');
            $table->integer('position');
        });
    }

    public function up(): void
    {
        Schema::create('subcomponents', function (Blueprint $table) {
            $table->foreignId('parent_id')
            ->nullable()
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->foreignId('child_id')
            ->nullable()
            ->references('id')->on('components')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
            $table->timestamps();
            $table->integer('position');
            $table->foreignId('page_id')
            ->references('id')->on('pages')
            ->constrained()
            ->onUpdate('cascade')
            ->onDelete('cascade');
        });
    }

The Component Model:

<?php

namespace App\Models;


use Illuminate\Database\Eloquent\Factories\HasFactory;
use Illuminate\Database\Eloquent\Model;
use Illuminate\Database\Eloquent\Relations\BelongsToMany;
use Illuminate\Database\Eloquent\Casts\AsArrayObject;
use Staudenmeir\LaravelAdjacencyList\Eloquent\HasGraphRelationships;


class Component extends Model
{
    use HasFactory;

    use HasGraphRelationships;

    protected $fillable = [
        'name',
        'type',
        'attributes',
    ];

    protected $casts = [
        'attributes' => AsArrayObject::class,
    ];

    protected $appends = ['position'];


    public function getPivotColumns(): array
    {
        return ['position'];
    }

    public function getPivotTableName(): string
    {
        return 'subcomponents';
    }

    /**
     * The pages that belong to the component.
     */
    public function pages(): BelongsToMany
    {
        return $this->belongsToMany(Page::class)->withPivot('position');
    }

    public function getPositionAttribute()
    {
        // Check if the component is a subcomponent
        if ($this->pivot_position) {
            return $this->pivot_position;
        }

        if ($this->pivot) {
            return $this->pivot->position;
        }

        // Return 0  if no position is set
        return 0;
    }
}

I also added the relation to my Page Model:

<?php

namespace App\Models;

use Illuminate\Database\Eloquent\Casts\AsArrayObject;
use Illuminate\Database\Eloquent\Factories\HasFactory;
use Illuminate\Database\Eloquent\Model;
use Illuminate\Database\Eloquent\Relations\BelongsToMany;

class Page extends Model
{
    use HasFactory;    

    protected $fillable = [
        'title',
        'description',
        'url',
        'attributes',
    ];

    protected $casts = [
        'attributes' => AsArrayObject::class,
    ];

    /**
     * The components that belong to the page.
     */
    public function components(): BelongsToMany
    {
        return $this->belongsToMany(Component::class)->withPivot('position');
    }
}

And how the pageController returns the component tree of a page:

    public function edit(Page $page)
    {
        $constraint = function ($query) use ($page) {
            $ids = $page->components()->pluck('id');
        
            $query->whereIn('id', $ids);
        };

        $pageComponents = Component::withRecursiveQueryConstraint(function (Builder $query) use ($page) {
            $query->where('subcomponents.page_id', $page->id);
         }, function () use ($constraint) {
            return Component::subgraph($constraint)->get();
         });

        $componentTree = $pageComponents->toTree();

        return Inertia::render('Admin/Pages/Edit', [
            'page' => $page,
            'page.components' => $componentTree,
            'pages' => Page::all(),
            'components' => Component::all(),
        ]);
    }

But all root components return a position of 0 - so the pivot table position column from the component_page-Table seems to get lost while generating the tree. I think it has something to do with the library-specific methods I use for the tree generation and the pivot column gets lost in this process.

Do you have an idea how to fix this?

[staudenmeir]

The reason is that the root components' positions are only available in the results of the first query ($page->components):

You can add them to the tree's root components manually:

$rootComponents = $page->components;

$constraint = function ($query) use ($rootComponents) {
    $ids = $rootComponents->pluck('id');

    $query->whereIn('id', $ids);
};

$pageComponents = ...

$componentTree = ...

$componentTree->each(
    fn($component) => $component->pivot_position = $rootComponents->find($component->id)->pivot->position
);

[staudenmeir]

I just had an idea for a fundamentally different approach. It would be possible to merge the two queries into a single one:

$constraint = function ($query) use ($page) {
    $columns = $query->getQuery()->columns;
    $query->getQuery()->columns[count($columns) - 1] = DB::raw('`component_page`.`position` as `pivot_position`');

    $query->join('component_page', 'components.id', '=', 'component_page.component_id')
        ->where('component_page.page_id', $page->id);
};

$pageComponents = Component::withRecursiveQueryConstraint(function (Builder $query) use ($page) {
    $query->where('subcomponents.page_id', $page->id);
}, function () use ($constraint) {
    return Component::subgraph($constraint)->get();
});

$componentTree = $pageComponents->toTree();

The idea is to get the root components at inside the subgraph query instead of with a separate query. It's more elegant than the workaround with $componentTree->each(...) but also not perfect:

• It joins the component_page table manually instead of using the components() relationship.
• Replacing the selected column is a bit hacky (line 3).

[nilskretschmer]

Thank you so much for your help.

I will give both solutions a try and report my results.

I am not sure if my use case is an edge case for using this library but I think it is some nice example for how a graph relationship could look like in a "real life example". If I have some time left I will look into the implementation details of the library. Maybe there are some ways to improve the dev experience/the docs to handle such use cases.

Managing the positions of components on a page needs some custom algorithm to handle changes but that's fine to me. But I could imagine that this is a typical use case when working with trees or graphs. So I think it would be a nice feature to add such functionality to the library itself.

Overall I think the approach of this library is very good. It provides a feature that is somehow lacking in laravel core and is a typical use case in a lot of real life apps. And that using just the feature of modern databases with a very good performance. I would like this library/cte to become part of Laracel. It would make the life of many devs much more easier :)

[staudenmeir]

Managing the positions of components on a page needs some custom algorithm to handle changes but that's fine to me. But I could imagine that this is a typical use case when working with trees or graphs. So I think it would be a nice feature to add such functionality to the library itself.

I thought about helpers for inserting and updating trees/graphs when I wrote the package, but I didn't want to guess what people might need and potentially waste time on that. I've been waiting for people to ask about it, but you are actually the first one to bring up this topic. So I don't know how everyone else handles this.