DIgraph

digraph.php

<?php
declare(strict_types = 1);

namespace FFW\Container;

class Digraph
{
    public const SOURCE_VERTEX = 'Source Vertex';

    /** @var string[][] */
    private $adjacencyList = [];

    public function addVertex(string $vertex, string $prevVertex): void
    {
        if (! isset($this->adjacencyList[$vertex])) {
            $this->adjacencyList[$vertex] = [];
        }
        if ($prevVertex !== self::SOURCE_VERTEX && ! in_array($vertex, $this->adjacencyList[$prevVertex], true)) {
            $this->adjacencyList[$prevVertex][] = $vertex;
        }
    }

    public function cycleFrom(string $vertex): array
    {
        $visitedVertices = [];
        $traversedPathStack = [];

        $visitedVertices[$vertex] = true;
        $traversedPathStack[] = $vertex;
        $visitedNeighbourIndex = 0;
        while (count($traversedPathStack) > 0) {
            $vertex = $traversedPathStack[count($traversedPathStack) - 1];
            while($visitedNeighbourIndex < count($this->adjacencyList[$vertex])) {
                $adjacentVertex = $this->adjacencyList[$vertex][$visitedNeighbourIndex];
                if (in_array($adjacentVertex, $traversedPathStack, true)) {
                    return array_merge($traversedPathStack, [$adjacentVertex]);
                }
                if (! array_key_exists($adjacentVertex, $visitedVertices)) {
                    $vertex = $adjacentVertex;
                    $visitedVertices[$vertex] = true;
                    $traversedPathStack[] = $vertex;
                    $visitedNeighbourIndex = 0;
                } else {
                    $visitedNeighbourIndex++;
                }
            }
            array_pop($traversedPathStack);
        }
        return [];
    }
}