Graph.php

Go to the documentation of this file.

<?php
namespace Magento\Framework\Data;

class Graph
{
    const DIRECTIONAL = 1;

    const INVERSE = 2;

    const NON_DIRECTIONAL = 3;

    protected $_nodes = [];

    protected $_from = [];

    protected $_to = [];

    public function __construct(array $nodes, array $relations)
    {
        foreach ($nodes as $node) {
            $this->_assertNode($node, false);
            $this->_nodes[$node] = $node;
        }
        foreach ($relations as $pair) {
            list($fromNode, $toNode) = $pair;
            $this->addRelation($fromNode, $toNode);
        }
    }

    public function addRelation($fromNode, $toNode)
    {
        if ($fromNode == $toNode) {
            throw new \InvalidArgumentException("Graph node '{$fromNode}' is linked to itself.");
        }
        $this->_assertNode($fromNode, true);
        $this->_assertNode($toNode, true);
        $this->_from[$fromNode][$toNode] = $toNode;
        $this->_to[$toNode][$fromNode] = $fromNode;
        return $this;
    }

    public function getRelations($mode = self::DIRECTIONAL)
    {
        switch ($mode) {
            case self::DIRECTIONAL:
                return $this->_from;
            case self::INVERSE:
                return $this->_to;
            case self::NON_DIRECTIONAL:
                $graph = $this->_from;
                foreach ($this->_to as $idTo => $relations) {
                    foreach ($relations as $idFrom) {
                        $graph[$idTo][$idFrom] = $idFrom;
                    }
                }
                return $graph;
            default:
                throw new \InvalidArgumentException("Unknown search mode: '{$mode}'");
        }
    }

    public function findCycle($node = null, $firstOnly = true)
    {
        $nodes = null === $node ? $this->_nodes : [$node];
        $results = [];
        foreach ($nodes as $node) {
            $result = $this->dfs($node, $node);
            if ($result) {
                if ($firstOnly) {
                    return $result;
                } else {
                    $results[] = $result;
                }
            }
        }
        return $results;
    }

    public function findPathsToReachableNodes($rootNode, $mode = self::DIRECTIONAL)
    {
        $graph = $this->getRelations($mode);
        $paths = [];
        $queue = [$rootNode];
        $visited = [$rootNode => $rootNode];
        $paths[$rootNode] = [$rootNode];
        while (!empty($queue)) {
            $node = array_shift($queue);
            if (!empty($graph[$node])) {
                foreach ($graph[$node] as $child) {
                    if (!isset($visited[$child])) {
                        $paths[$child] = $paths[$node];
                        $paths[$child][] = $child;
                        $visited[$child] = $child;
                        $queue[] = $child;
                    }
                }
            }
        }
        return $paths;
    }

    public function dfs($fromNode, $toNode, $mode = self::DIRECTIONAL)
    {
        $this->_assertNode($fromNode, true);
        $this->_assertNode($toNode, true);
        return $this->_dfs($fromNode, $toNode, $this->getRelations($mode));
    }

    protected function _dfs($fromNode, $toNode, $graph, &$visited = [], $stack = [])
    {
        $stack[] = $fromNode;
        $visited[$fromNode] = $fromNode;
        if (isset($graph[$fromNode][$toNode])) {
            $stack[] = $toNode;
            return $stack;
        }
        if (isset($graph[$fromNode])) {
            foreach ($graph[$fromNode] as $node) {
                if (!isset($visited[$node])) {
                    $result = $this->_dfs($node, $toNode, $graph, $visited, $stack);
                    if ($result) {
                        return $result;
                    }
                }
            }
        }
        return [];
    }

    protected function _assertNode($node, $mustExist)
    {
        if (isset($this->_nodes[$node])) {
            if (!$mustExist) {
                throw new \InvalidArgumentException("Graph node '{$node}' already exists'.");
            }
        } else {
            if ($mustExist) {
                throw new \InvalidArgumentException("Graph node '{$node}' does not exist.");
            }
        }
    }
}