Graph Class Reference

Public Member Functions
	__construct (array $nodes, array $relations)
	addRelation ($fromNode, $toNode)
	getRelations ($mode=self::DIRECTIONAL)
	findCycle ($node=null, $firstOnly=true)
	findPathsToReachableNodes ($rootNode, $mode=self::DIRECTIONAL)
	dfs ($fromNode, $toNode, $mode=self::DIRECTIONAL)

Data Fields
const	DIRECTIONAL = 1
const	INVERSE = 2
const	NON_DIRECTIONAL = 3

Protected Member Functions
	_dfs ($fromNode, $toNode, $graph, &$visited=[], $stack=[])
	_assertNode ($node, $mustExist)

Protected Attributes
	$_nodes = []
	$_from = []
	$_to = []

Detailed Description

Graph data structure

Definition at line 11 of file Graph.php.

Constructor & Destructor Documentation

__construct()

__construct	(	array	$nodes,
		array	$relations
	)

Validate consistency of the declared structure and assign it to the object state

Parameters

array	$nodes	plain array with node identifiers
array	$relations	array of 2-item plain arrays, which represent relations of nodes "from" "to"

Definition at line 47 of file Graph.php.

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

Member Function Documentation

_assertNode()

_assertNode (   $node,   $mustExist  )

protected

Verify existence or non-existence of a node

Parameters

string | int	$node
bool	$mustExist

Returns

void

Exceptions

Definition at line 224 of file Graph.php.

    {
        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.");
            }
        }
    }

_dfs()

_dfs (   $fromNode,   $toNode,   $graph, &  $visited = [],   $stack = []  )

protected

Recursive sub-routine of dfs()

Parameters

string | int	$fromNode
string | int	$toNode
array	$graph
array	&$visited
array	$stack

Returns

array http://en.wikipedia.org/wiki/Depth-first_search

Definition at line 195 of file Graph.php.

    {
        $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 [];
    }

addRelation()

addRelation	(		$fromNode,
			$toNode
	)

Set a relation between nodes

Parameters

string | int	$fromNode
string | int	$toNode

Returns

$this

Exceptions

Definition at line 67 of file Graph.php.

    {
        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;
    }

dfs()

dfs	(		$fromNode,
			$toNode,
			$mode = self::DIRECTIONAL
	)

"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.

Parameters

string | int	$fromNode
string | int	$toNode
int	$mode

Returns

array

Definition at line 177 of file Graph.php.

    {
        $this->_assertNode($fromNode, true);
        $this->_assertNode($toNode, true);
        return $this->_dfs($fromNode, $toNode, $this->getRelations($mode));
    }

findCycle()

findCycle	(		$node = null,
			$firstOnly = true
	)

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

Parameters

string | int	$node
boolean	$firstOnly	found only first cycle

Returns

array

Definition at line 116 of file Graph.php.

    {
        $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;
    }

findPathsToReachableNodes()

findPathsToReachableNodes	(		$rootNode,
			$mode = self::DIRECTIONAL
	)

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

Parameters

string | int	$rootNode
int	$mode

Returns

array

Definition at line 143 of file Graph.php.

    {
        $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;
    }

getRelations()

getRelations

(

$mode = self::DIRECTIONAL

)

Export relations between nodes. Can return inverse relations

Parameters

int

$mode

Returns

array

Exceptions

Definition at line 86 of file Graph.php.

    {
        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}'");
        }
    }

Field Documentation

$_from

$_from = []

protected

Definition at line 32 of file Graph.php.

$_nodes

$_nodes = []

protected

#- #-

Definition at line 25 of file Graph.php.

$_to

$_to = []

protected

Definition at line 39 of file Graph.php.

DIRECTIONAL

const DIRECTIONAL = 1

#+ Search modes

Definition at line 16 of file Graph.php.

INVERSE

const INVERSE = 2

Definition at line 18 of file Graph.php.

NON_DIRECTIONAL

const NON_DIRECTIONAL = 3

Definition at line 20 of file Graph.php.

---

The documentation for this class was generated from the following file:

• vendor/magento/framework/Data/Graph.php