Get Entire Tree Efficiently

[darthtaco]

I have a 360-node tree with N degrees of depth. The tree (represented by a model called TreeNode) will be accessed frequently, but altered very infrequently.

I'm trying to build output similar to the following, in order to build a select dropdown of similar structure.

Product
Product > Category A
Product > Category A > Subcategory 1
Product > Category A > Subcategory 2
Product > Category B
Product > Category C
Product > Category C > Subcategory 1
Product > Category C > Subcategory 1 > Subcategory (a)
Product > Category D
Product > Category D > Subcategory 1
Product > Category D > Subcategory 2
...

In order to do this, I have created a method in my TreeNode model called getPath():

public function getPath() {
    $ancestors = $this->getAncestors(['Name']);
    return implode(' > ',array_merge(array_column($ancestors->toArray(),'Name'),array($this->Name)));
}

Then I iterate over the results of a TreeNode::all() and call getPath() for each one.

@foreach( TreeNode::all() as $node )
   {{ $node->getPath() }}<br />
@endforeach

Although the correct output is produced, the problem here is that this method takes 360 database queries build this tree, and if the list of nodes grows the problem will only compound. I have a feeling I'm doing this wrong, but looking through the code for laravel-nestedset I haven't been able to find an alternative way to build the entire tree.

Is there a more efficient way to do this?

Thanks

[lazychaser]

Hi! If you're using my package, it can be done easily. First of all, you need to query all nodes and convert them to a tree like so:

$tree = TreeNode::all()->toTree();

This will fill parent and children relations for each node. Now we can use recursion for building path:

public function stringPath()
{
   $parent = $this->parent;
   return $parent ? $parent->stringPath().' > '.$this->Name : $this->Name;
}

This will be much faster, but we can optimize this further by caching path:

protected $stringPath;

public function stringPath()
{
   if ($this->stringPath) return $this->stringPath;

   $parent = $this->parent;
   return $this->stringPath = $parent ? $parent->stringPath().' > '.$this->Name : $this->Name;
}

[darthtaco]

@lazychaser thanks so much for responding so quickly.

That method does not appear to work for me. When I run a foreach loop over the results from $tree = TreeNode::all()->toTree(), only the three root nodes are returned, and so I never get any deeper than the first level. So, when calling the stringPath() method, I only get the path to the root nodes.

I tried using your stringPath() method above with the results from TreeNode::all() (without calling toTree()) and, while I got the correct output, it generated over 1,400 queries to the database.

I am using L5 and your version 2.2.0.

Any suggestions?

[lazychaser]

Yeah, you right, this is my mistake, you need to call toTree on different collection to fill relations and then iterate over original collection:

$nodes = TreeNode::all();
\Kalnoy\Nestedset\Collection::make($nodes)->toTree();

// iterate over $nodes
foreach ($nodes as $node)

In fact, I believe I should extract relationships filling to a separate method on collection.

[lazychaser]

Released v2.3.0 with linkNodes method, no you can do following:

$nodes = TreeNode::defaultOrder()->get()->linkNodes();

foreach ($nodes as $node)

[darthtaco]

@lazychaser that fix works well, and generates only one DB query. Thanks a million!

[lazychaser]

I'm glad that worked!

[engraniaokasha]

hi , when i used totree() i did't get parent ..why?

[ComputerMaverick69]

Released v2.3.0 with linkNodes method, no you can do following:

$nodes = TreeNode::defaultOrder()->get()->linkNodes();

foreach ($nodes as $node)

This seemed to work in getting the relationships however the children collection returns an empty array despite there being a child node to a parent node.