Traversing Hierarchy Tree Adjacency List Model in Yii2

Question

I was stuck on a logic I can't understand how it would be done and traverse the list.

Actually I was creating a category list that would be further used in creating the products. I wanted the category list should be in the form of parent and its sub nodes like adjacency list model.

Database:

id        categoryname        parent [id is the foreign key for the parent]
 1           a                  1
 2           b                  2
 3           c                  2
 4           e                  2
 5           f                  3
 6           g                  4

Fetching the details with ActiveQuery in yii2:

$rows = Category::find()
             ->asArray()
             ->all();

$rows array contains the data like this form

Array
(
  [0] => Array
    (
        [id] => 1
        [categoryname] => a
        [parent] => 1 
   )

  [1] => Array
    (
        [id] => 2
        [categoryname] => b
        [parent] =>2
    )

  [2] => Array
    (
        [id] => 3
        [categoryname] => c
        [parent] => 2
    )
)
And so on...

I wanted the desired output should be like this form of list

[ 
  [ 
    'id' => 1, 
    'categoryname' => 'a'
  ], 
  [ 
    'id' => 2, 
    'categoryname' => 'b'
  ], 
  [ 
    'id' => 3,
    'categoryname' => 'b > c'
  ], 
  [ 
    'id' => 4, 
    'categoryname' => 'b>c>f' 
  ]
 ] 
 

I tried: when I get the rows from the table and stores them in an associative array. The child-ids for each branch node are stored in another associative array.

foreach ($rows as $row){
        $id = $row["id"];
        $parent_id = $row["parent"] === NULL ? "NULL" : $row["parent"];
        $data[$id] = $row;
        $index[$parent_id][] = $id;
    }
    function display_child_nodes($parent_id, $level,$data,$index)
    {

        $parent_id = $parent_id === NULL ? "NULL" : $parent_id;
        if (isset($index[$parent_id])) {
            foreach ($index[$parent_id] as $id) {
                $result['id'] = $data[$id]['id'];
                $result['name'] = $data[$id]['categoryname'];
                $result['level'] = $level;
                echo str_repeat("-", $level) . $data[$id]["categoryname"] . "\n";
                display_child_nodes($id, $level + 1,$data,$index);
            }

        }
    }
    display_child_nodes(NULL, 0,$data,$index);

I followed this reference for result but i cant get the desired output.

I had gone through with stack overflow question but none is useful for me . So anybody can help Appreciated in advanced.

Answer 1

You can use Iterators for that. Let's extend RecursiveArrayIterator and call new iterator AdjacencyListIterator:

class AdjacencyListIterator extends RecursiveArrayIterator
{
    private $adjacencyList;

    public function __construct(
        array $adjacencyList,
        array $array = null,
        $flags = 0
    ) {
        $this->adjacencyList = $adjacencyList;

        $array = !is_null($array)
            ? $array
            : array_filter($adjacencyList, function ($node) {
                return is_null($node['parent']);
            });

        parent::__construct($array, $flags);
    }

    private $children;

    public function hasChildren()
    {
        $children = array_filter($this->adjacencyList, function ($node) {
            return $node['parent'] === $this->current()['id'];
        });

        if (!empty($children)) {
            $this->children = $children;
            return true;
        }

        return false;
    }

    public function getChildren()
    {
        return new static($this->adjacencyList, $this->children);
    }
}

By the way, take a notice, for top level parents parent should be null (and not the same as id).

Having this iterator you can generate paths like that:

$iterator = new RecursiveIteratorIterator(
    new AdjacencyListIterator($rows),
    RecursiveIteratorIterator::SELF_FIRST
);

$path = [];
foreach ($iterator as $node) {
    $depth = $iterator->getDepth();
    $path[$depth] = $node['categoryname'];

    echo implode(' > ', array_slice($path, 0, $depth + 1)), PHP_EOL;
}

Here is working demo.

This approach can be a bit slower, than custom recursive function. But it is actually more flexible. By changing only the mode of traversing, you can get leafs only, for example:

$iterator = new RecursiveIteratorIterator(
    new AdjacencyListIterator($rows)
);

foreach ($iterator as $leaf) {
    echo $leaf['categoryname'], PHP_EOL;
}

This case differs from previous in that we set $mode of the RecursiveIteratorIterator to the default one RecursiveIteratorIterator::LEAVES_ONLY.