github.com

classDigraph

packages/sql-parser/src/Automaton/Digraph.php:17
final class Digraph
Restricted visibility: declared "@visibility root". Code outside that scope must not name this declaration.

Closes sets over a relation: each node ends with the union of every node it reaches.

This is the traversal of DeRemer and Pennello, which finds the strongly connected components of the relation and gives every member of a component the same set. It runs on an explicit stack, as the relations of a large grammar chain deeper than the call stack should be asked to go.

Methods§

public function close(
    int $nodeCount,
    array<int, list<int>> $edges,
    array<int, array<int, int>> $sets,
): array<int, array<int, int>>
source§

Closes the sets.

Parameters

$nodeCountintHow many nodes there are, numbered from zero
$edgesarray<int, list<int>>Nodes each node reaches directly
$setsarray<int, array<int, int>>Initial set of each node, as bitset words

Returns

array<int, array<int, int>> Closed set of each node
Test cases 1
Called from 2
Calls 2
public function traverse(
    int $root,
    array<int, list<int>> $edges,
    array<int, array<int, int>> &$sets,
    array<int, int> &$marks,
    list<int> &$stack,
): void
source§

Traverses the relation from one node, closing every node it reaches.

Parameters

$rootintNode to start from
$edgesarray<int, list<int>>Nodes each node reaches directly
$setsarray<int, array<int, int>>Sets being closed, updated in place
$marksarray<int, int>Traversal marks, updated in place
$stacklist<int>Nodes of the component being explored, updated in place
Test cases 1
Called from 1
Calls 4

Test cases 5§

Test cases that cover or call this symbol, from the coverage report and from the analyzed test sources.

Dedicated tests 2
Other tests reaching this symbol 3

Relations§

Instantiated in 1
Method calls 2
Type declarations 1