TemplesOfCode\NodesAndEdges\DFS\DepthFirstOrder

Complexity

Total Complexity

9

Size/Duplication

Total Lines	103
Duplicated Lines	0 %

Importance

Changes

0

5 Methods

Rating	Name	Duplication	Size	Complexity
A	reversePostorder()	0	3	1
A	__construct()	0	20	3
A	dfs()	0	20	3
A	preorder()	0	3	1
A	postorder()	0	3	1

<?php


namespace TemplesOfCode\NodesAndEdges\DFS;

use TemplesOfCode\NodesAndEdges\Graph;

/**
 * Class DepthFirstOrder
 * @package TemplesOfCode\NodesAndEdges
 */
class DepthFirstOrder
{
    /**
     * @var bool[]
     */
    protected $marked;

    /**
     * @var Graph
     */
    protected $graph;

    /**
     * @var array
     */
    private $pre;

    /**
     * @var array
     */
    private $post;

    /**
     * @var array
     */
    private $reversePost;

    /**
     * DepthFirstOrder constructor.
     *
     * @param Graph $graph
     */
    public function __construct(Graph $graph)
    {
        // init
        $this->pre = [];
        // init
        $this->post = [];
        // init
        $this->reversePost = [];
        // set
        $this->graph = $graph;
        // set
        $vertices = $graph->getVertices();
        // set
        $this->marked = array_fill(0, $vertices, false);
        // iterate over the vertices
        for ($vertex = 0; $vertex < $vertices; $vertex++) {
            // check for visit
            if (!$this->marked[$vertex]) {
                // execute DFS logic
                $this->dfs($vertex);
            }
        }
    }

    /**
     * @param int $vertex
     */
    protected function dfs(int $vertex)
    {
        // enqueue $vertex - add to end
        array_push($this->pre, $vertex);
        // mark the visit
        $this->marked[$vertex] = true;
        // get neighbors
        $neighbors = $this->graph->adjacent($vertex);
        // iterate over the set
        foreach ($neighbors as $w) {
            // check for previous visit
            if (!$this->marked[$w]) {
                // has not been visited yet
                $this->dfs($w);
            }
        }
        // enqueue $vertex - add to end
        array_push($this->post, $vertex);
        // push to the reverse post stack - add to beginning
        array_unshift($this->reversePost, $vertex);
    }

    /**
     * @return array
     */
    public function preorder()
    {
        return $this->pre;
    }

    /**
     * @return array
     */
    public function postorder()
    {
        return $this->post;
    }

    /**
     * @return array
     */
    public function reversePostorder()
    {
       return $this->reversePost;
    }
}