graph.php 1.17 KB
<?php

namespace addons\fastflow\model;

class graph
{
    private $found_path = [];
    private $node_stack = [];
    private $pathIndex = 0;
    private $visited = [];

    private function findAllPath($matrix, $start_node, $end_node)
    {
        $this->node_stack[] = $start_node;
        $this->visited[] = $start_node;
        $temp_node = end($this->node_stack);
        if ($temp_node == $end_node) {
            foreach ($this->node_stack as $node) {
                $this->found_path[$this->pathIndex][] = $node;
            }
            array_pop($this->node_stack);
            array_pop($this->visited);
            $this->pathIndex += 1;
            return;
        }
        $targets = $matrix[$temp_node];

        foreach ($targets as $target) {
            if (!in_array($target,$this->visited)) {
                self::findAllPath($matrix, $target, $end_node);
            }
        }
        array_pop($this->node_stack);
        array_pop($this->visited);
    }

    public function getAllPath($matrix, $start_node, $end_node)
    {
        self::findAllPath($matrix, $start_node, $end_node);
        return $this->found_path;
    }

}