Server : Apache System : Linux server2.corals.io 4.18.0-348.2.1.el8_5.x86_64 #1 SMP Mon Nov 15 09:17:08 EST 2021 x86_64 User : corals ( 1002) PHP Version : 7.4.33 Disable Function : exec,passthru,shell_exec,system Directory : /home/corals/old/vendor/magento/framework/Data/ |
<?php
/**
* Copyright © Magento, Inc. All rights reserved.
* See COPYING.txt for license details.
*/
namespace Magento\Framework\Data;
/**
* Graph data structure
*/
class Graph
{
/**#@+
* Search modes
*/
const DIRECTIONAL = 1;
const INVERSE = 2;
const NON_DIRECTIONAL = 3;
/**#@-*/
/**#@-*/
protected $_nodes = [];
/**
* Declared relations directed "from" "to"
*
* @var array
*/
protected $_from = [];
/**
* Inverse relations "to" "from"
*
* @var array
*/
protected $_to = [];
/**
* Validate consistency of the declared structure and assign it to the object state
*
* @param array $nodes plain array with node identifiers
* @param array $relations array of 2-item plain arrays, which represent relations of nodes "from" "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);
}
}
/**
* Set a relation between nodes
*
* @param string|int $fromNode
* @param string|int $toNode
* @return $this
* @throws \InvalidArgumentException
*/
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;
}
/**
* Export relations between nodes. Can return inverse relations
*
* @param int $mode
* @return array
* @throws \InvalidArgumentException
*/
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}'");
}
}
/**
* Find a cycle in the graph
*
* Returns first/all found cycle
* Optionally may specify a node to return a cycle if it is in any
*
* @param string|int $node
* @param boolean $firstOnly found only first cycle
* @return array
*/
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;
}
/**
* Find paths to reachable nodes from root node
*
* Returns array of paths, key is destination node and value is path (an array) from rootNode to destination node
* Eg. dest => [root, A, dest] means root -> A -> dest
*
* @param string|int $rootNode
* @param int $mode
* @return array
*/
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;
}
/**
* "Depth-first search" of a path between nodes
*
* Returns path as array of nodes or empty array if path does not exist.
* Only first found path is returned. It will be not necessary the shortest or optimal in any way.
*
* @param string|int $fromNode
* @param string|int $toNode
* @param int $mode
* @return array
*/
public function dfs($fromNode, $toNode, $mode = self::DIRECTIONAL)
{
$this->_assertNode($fromNode, true);
$this->_assertNode($toNode, true);
return $this->_dfs($fromNode, $toNode, $this->getRelations($mode));
}
/**
* Recursive sub-routine of dfs()
*
* @param string|int $fromNode
* @param string|int $toNode
* @param array $graph
* @param array &$visited
* @param array $stack
* @return array
* @link http://en.wikipedia.org/wiki/Depth-first_search
*/
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 [];
}
/**
* Verify existence or non-existence of a node
*
* @param string|int $node
* @param bool $mustExist
* @return void
* @throws \InvalidArgumentException according to assertion rules
*/
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.");
}
}
}
}