*/ private array $nodes = []; /** * DFS state for the different nodes, indexed by node object id and using one of * this class' constants as value. * * @var array */ private array $states = []; /** * Edges between the nodes. The first-level key is the object id of the outgoing * node; the second array maps the destination node by object id as key. * * @var array> */ private array $edges = []; /** * DFS numbers, by object ID * * @var array */ private array $dfs = []; /** * lowlink numbers, by object ID * * @var array */ private array $lowlink = []; private int $maxdfs = 0; /** * Nodes representing the SCC another node is in, indexed by lookup-node object ID * * @var array */ private array $representingNodes = []; /** * Stack with OIDs of nodes visited in the current state of the DFS * * @var list */ private array $stack = []; public function addNode(object $node): void { $id = spl_object_id($node); $this->nodes[$id] = $node; $this->states[$id] = self::NOT_VISITED; $this->edges[$id] = []; } public function hasNode(object $node): bool { return isset($this->nodes[spl_object_id($node)]); } /** * Adds a new edge between two nodes to the graph */ public function addEdge(object $from, object $to): void { $fromId = spl_object_id($from); $toId = spl_object_id($to); $this->edges[$fromId][$toId] = true; } public function findStronglyConnectedComponents(): void { foreach (array_keys($this->nodes) as $oid) { if ($this->states[$oid] === self::NOT_VISITED) { $this->tarjan($oid); } } } private function tarjan(int $oid): void { $this->dfs[$oid] = $this->lowlink[$oid] = $this->maxdfs++; $this->states[$oid] = self::IN_PROGRESS; array_push($this->stack, $oid); foreach ($this->edges[$oid] as $adjacentId => $ignored) { if ($this->states[$adjacentId] === self::NOT_VISITED) { $this->tarjan($adjacentId); $this->lowlink[$oid] = min($this->lowlink[$oid], $this->lowlink[$adjacentId]); } elseif ($this->states[$adjacentId] === self::IN_PROGRESS) { $this->lowlink[$oid] = min($this->lowlink[$oid], $this->dfs[$adjacentId]); } } $lowlink = $this->lowlink[$oid]; if ($lowlink === $this->dfs[$oid]) { $representingNode = null; do { $unwindOid = array_pop($this->stack); if (! $representingNode) { $representingNode = $this->nodes[$unwindOid]; } $this->representingNodes[$unwindOid] = $representingNode; $this->states[$unwindOid] = self::VISITED; } while ($unwindOid !== $oid); } } public function getNodeRepresentingStronglyConnectedComponent(object $node): object { $oid = spl_object_id($node); if (! isset($this->representingNodes[$oid])) { throw new InvalidArgumentException('unknown node'); } return $this->representingNodes[$oid]; } }