How do I flatten laravel recursive relationship collection (tree collections)?

Question

How do I flatten a collection with hierarchy self referenced models, tree collections into a single dimension collection. I have a self referencing model having parents and children.

I want the result to return a eloquent collection, not a simple collection or an array. array has been used as result results for easy demonstration

relationships are declared like this.

public function parent()
{
    return $this->belongsTo(self::class, 'parent_id');
}

public function parentRecursive()
{
    return $this->parent()->with('parentRecursive');
}

public function children()
{
    return $this->hasMany(self::class, 'parent_id');
}

public function childrenRecursive()
{
    return $this->children()->with('childrenRecursive');
}

so when i call the model->childrenRecursive it returns the collection as it should be. like this. i have changed it toArray() to make it easy to read.

array:1 [
  0 => array:6 [
    "id" => 5
    "name" => "I am a child of 1"
    "parent_id" => "1"
    "created_at" => "2016-12-26 13:53:50"
    "updated_at" => "2016-12-26 13:53:50"
    "children_recursive" => array:1 [
      0 => array:6 [
        "id" => 6
        "name" => "I am child of 5"
        "parent_id" => "5"
        "created_at" => "2016-12-26 13:53:50"
        "updated_at" => "2016-12-26 13:53:50"
        "children_recursive" => array:2 [
          0 => array:6 [
            "id" => 7
            "name" => "I am child of 6"
            "parent_id" => "6"
            "created_at" => "2016-12-26 13:53:50"
            "updated_at" => "2016-12-26 13:53:50"
            "children_recursive" => []
          ],
          1 => array:6 [
            "id" => 8
            "name" => "I am child of 6 too"
            "parent_id" => "6"
            "created_at" => "2016-12-26 13:53:50"
            "updated_at" => "2016-12-26 13:53:50"
            "children_recursive" => []
          ]
        ]
      ]
    ]
  ]
]

what I want to achieve is the collection to be single dimension. here is how the toArray() to that collection should look like.

array:4 [
  0 => array:6 [
    "id" => 5
    "name" => "I am a child of 1"
    "parent_id" => "1"
    "created_at" => "2016-12-26 13:53:50"
    "updated_at" => "2016-12-26 13:53:50"
    ],
  1 => array:6 [
    "id" => 6
    "name" => "I am child of 5"
    "parent_id" => "5"
    "created_at" => "2016-12-26 13:53:50"
    "updated_at" => "2016-12-26 13:53:50"
    ],
  2 => array:6 [
    "id" => 7
    "name" => "I am child of 6"
    "parent_id" => "6"
    "created_at" => "2016-12-26 13:53:50"
    "updated_at" => "2016-12-26 13:53:50"
    ],
  3 => array:6 [
    "id" => 8
    "name" => "I am child of 6 too"
    "parent_id" => "6"
    "created_at" => "2016-12-26 13:53:50"
    "updated_at" => "2016-12-26 13:53:50"
    ]
]

I have tried many collection methods like filter, flatMap, flatten and multiple array methods. but haven't found an appropriate solution.

Answer 1

I didn't find any builtin method into theLaravel collection either. You may try something like this (Use it as a global function or as a dedicated class method, it's up to you. here is the idea):

function flatten($array) {
    $result = [];
    foreach ($array as $item) {
        if (is_array($item)) {
            $result[] = array_filter($item, function($array) {
                return ! is_array($array);
            });
            $result = array_merge($result, flatten($item));
        } 
    }
    return array_filter($result);
}

Then use it like this:

// When available into global scope as a function
$flattenArray = flatten($arrayFromTheCollection);

Answer 2

For these who does run into a dead loop because of incest relationship, I used this solution to retrieve descendants' attributes through eager loaded relationship - worked like fully flattening the relationship but avoid running into dead loop by foreach.

Solution link

Answer 3

I like this attribute solution for no particular reason other than having to ability to extract information easily using map after fetching.

public function chilrenRecursive()
{
    return $this->children()->with('chilrenRecursive');
}

public function getFlatSelfAndChildrenAttribute()
{
    return collect([$this])->merge(
        $this->chilrenRecursive->flatMap(function($q){
            return $q->flatSelfAndChildren ?? collect([$q]);
        })
    );
}

// Example controller code
return $thing->flatSelfAndChildren->map(function($q){ return $q->id;})->toArray();

Answer 4

this is my code, it might help ^_^

    Collection::macro('flattenTree', function ($childrenField = 'children', $levelAttribute = 'level')
    {
        $toProcess = $this->items;
        $processed = [];
        while($item = array_shift($toProcess))
        {
            $item->$levelAttribute ++;
            $processed[] = $item;
            if (count($item->$childrenField) > 0) {
                $children = array_reverse($item->$childrenField->items);
                foreach ($children as $child) {
                    $child->$levelAttribute = $item->$levelAttribute;
                    array_unshift($toProcess,$child);
                }
            }
        }
        return Collection::make($processed);
    });

you should put this code in the boot method of AppServiceProvider.php or any provider you wish, and then you can use it like this

Category::where('parent_category_id', null)->get()->flattenTree();

this will flat the tree and add a level attribute to each object to indicate the depth level of the object

good luck for everyone

Answer 5

This will will recursively flatten. It doesn't prevent duplicates though, so you'll need to filter them out if that's an issue.

In your AppServiceProvider::boot method

use Illuminate\Support\Collection;

//...

Collection::macro('flattenTree', function ($childrenField) {
    $result = collect();

     foreach ($this->items as $item) {
        $result->push($item);

        if ($item->$childrenField instanceof Collection) {
            $result = $result->merge($item->$childrenField->flattenTree($childrenField));
        }
    }

    return $result;
});

Then

$flattened = $myCollection->flattenTree('childrenRecursive');

// or in the case of the question
$flattened = $model->childrenRecursive->flattenTree('childrenRecursive');

Answer 6

It's a bit late, but I'm going to post what I wish I had been able to find before I ended up writing it myself.

Similar to the original post, I have a recursive parent/child relationship in my categories table (but this could apply to any table with a self-referencing parent_id column). You can set up your Model like this:

Category.php

<?php
namespace App\Models;
use Illuminate\Database\Eloquent\Model;

class Category extends Model {

    // Relationships
    public function parent()
    {
        return $this->belongsTo('App\Models\Category', 'parent_id');
    }

    public function children()
    {
        return $this->hasMany('App\Models\Category', 'parent_id');
    }

    public function nested_ancestors()
    {
        return $this->belongsTo('App\Models\Category', 'parent_id')->with('parent');
    }

    public function nested_descendants()
    {
        return $this->hasMany('App\Models\Category', 'parent_id')->with('children');
    }

    // Attributes
    public function getFlatAncestorsAttribute()
    {
        return collect(flat_ancestors($this));
    }

    public function getFlatDescendantsAttribute()
    {
        return collect(flat_descendants($this));
    }
}

Then somewhere in your application, you need to have a place to put some global helper functions. You could follow the instructions found here, and then just paste in the following helper functions:

Helpers.php

function flat_ancestors($model) {
  $result = [];
  if ($model->parent) {
    $result[] = $model->parent;
    $result = array_merge($result, flat_ancestors($model->parent));
  }
  return $result;
}

function flat_descendants($model) {
  $result = [];
  foreach ($model->children as $child) {
    $result[] = $child;
    if ($child->children) {
      $result = array_merge($result, flat_descendants($child));
    }
  }
  return $result;
}

The code above will then allow you to use $category->flat_ancestors, which will produce a flat collection of all the category's ancestors, no matter how many there are. Similarly, using $category->flat_descendants will yield a flat collection of all the child categories, and the child's children categories, and so on until all the posterity categories have been accounted for.

Some things to be careful of:

• This type of approach could potentially lead to an infinite loop if you have Category 1 referencing Category 2 as its parent, and then Category 2 has Category 1 as its parent. Just be careful that parent/child relationships are incest free :-)
• This type of approach also isn't very efficient. It'll be fine for a bunch of parent/child recursive relationships, but especially for the flat_descendants functions, the number of database queries grows exponentially for each generation level.