Hydration
9 months ago
TopologicalSort
9 months ago
CriteriaOrderings.php
9 months ago
HydrationCompleteHandler.php
9 months ago
SQLResultCasing.php
9 months ago
StronglyConnectedComponents.php
9 months ago
TopologicalSort.php
9 months ago
index.php
9 months ago
StronglyConnectedComponents.php
84 lines
| 1 | <?php |
| 2 | declare (strict_types=1); |
| 3 | namespace MailPoetVendor\Doctrine\ORM\Internal; |
| 4 | if (!defined('ABSPATH')) exit; |
| 5 | use InvalidArgumentException; |
| 6 | use function array_keys; |
| 7 | use function array_pop; |
| 8 | use function array_push; |
| 9 | use function min; |
| 10 | use function spl_object_id; |
| 11 | final class StronglyConnectedComponents |
| 12 | { |
| 13 | private const NOT_VISITED = 1; |
| 14 | private const IN_PROGRESS = 2; |
| 15 | private const VISITED = 3; |
| 16 | private $nodes = []; |
| 17 | private $states = []; |
| 18 | private $edges = []; |
| 19 | private $dfs = []; |
| 20 | private $lowlink = []; |
| 21 | private $maxdfs = 0; |
| 22 | private $representingNodes = []; |
| 23 | private $stack = []; |
| 24 | public function addNode($node) : void |
| 25 | { |
| 26 | $id = spl_object_id($node); |
| 27 | $this->nodes[$id] = $node; |
| 28 | $this->states[$id] = self::NOT_VISITED; |
| 29 | $this->edges[$id] = []; |
| 30 | } |
| 31 | public function hasNode($node) : bool |
| 32 | { |
| 33 | return isset($this->nodes[spl_object_id($node)]); |
| 34 | } |
| 35 | public function addEdge($from, $to) : void |
| 36 | { |
| 37 | $fromId = spl_object_id($from); |
| 38 | $toId = spl_object_id($to); |
| 39 | $this->edges[$fromId][$toId] = \true; |
| 40 | } |
| 41 | public function findStronglyConnectedComponents() : void |
| 42 | { |
| 43 | foreach (array_keys($this->nodes) as $oid) { |
| 44 | if ($this->states[$oid] === self::NOT_VISITED) { |
| 45 | $this->tarjan($oid); |
| 46 | } |
| 47 | } |
| 48 | } |
| 49 | private function tarjan(int $oid) : void |
| 50 | { |
| 51 | $this->dfs[$oid] = $this->lowlink[$oid] = $this->maxdfs++; |
| 52 | $this->states[$oid] = self::IN_PROGRESS; |
| 53 | array_push($this->stack, $oid); |
| 54 | foreach ($this->edges[$oid] as $adjacentId => $ignored) { |
| 55 | if ($this->states[$adjacentId] === self::NOT_VISITED) { |
| 56 | $this->tarjan($adjacentId); |
| 57 | $this->lowlink[$oid] = min($this->lowlink[$oid], $this->lowlink[$adjacentId]); |
| 58 | } elseif ($this->states[$adjacentId] === self::IN_PROGRESS) { |
| 59 | $this->lowlink[$oid] = min($this->lowlink[$oid], $this->dfs[$adjacentId]); |
| 60 | } |
| 61 | } |
| 62 | $lowlink = $this->lowlink[$oid]; |
| 63 | if ($lowlink === $this->dfs[$oid]) { |
| 64 | $representingNode = null; |
| 65 | do { |
| 66 | $unwindOid = array_pop($this->stack); |
| 67 | if (!$representingNode) { |
| 68 | $representingNode = $this->nodes[$unwindOid]; |
| 69 | } |
| 70 | $this->representingNodes[$unwindOid] = $representingNode; |
| 71 | $this->states[$unwindOid] = self::VISITED; |
| 72 | } while ($unwindOid !== $oid); |
| 73 | } |
| 74 | } |
| 75 | public function getNodeRepresentingStronglyConnectedComponent($node) |
| 76 | { |
| 77 | $oid = spl_object_id($node); |
| 78 | if (!isset($this->representingNodes[$oid])) { |
| 79 | throw new InvalidArgumentException('unknown node'); |
| 80 | } |
| 81 | return $this->representingNodes[$oid]; |
| 82 | } |
| 83 | } |
| 84 |