← Code-Übersicht

FlussLayout.php

Pfad: src/Infrastructure/Flow/FlussLayout.php

Ext: php

Größe: 2961 Bytes

Geändert: 2026-07-15 23:54:20+02

<?php
declare(strict_types=1);

namespace Demo\Infrastructure\Flow;

/**
 * Reiner Layout-Algorithmus fuer den Prozess-DAG: berechnet je Knoten Rang
 * (laengster Pfad vom Start) und Spalte (deterministische Position je Rang).
 * Ohne I/O, damit unit-testbar. Setzt einen azyklischen Graphen voraus.
 */
final class FlussLayout
{
    /**
     * Berechnet Rang und Spalte je Knoten.
     *
     * @param list<int>                  $knoten Schritt-Ids.
     * @param list<array{0:int,1:int}>   $kanten Kanten als [vorgaenger_id, schritt_id].
     * @return array{pos:array<int,array{rang:int,spalte:int}>,maxRang:int,maxSpalten:int}
     */
    public function berechne(array $knoten, array $kanten): array
    {
        $nachfolger = [];
        $eingang = [];
        foreach ($knoten as $k) {
            $nachfolger[$k] = [];
            $eingang[$k] = 0;
        }
        foreach ($kanten as $kante) {
            [$von, $zu] = $kante;
            $nachfolger[$von][] = $zu;
            $eingang[$zu]++;
        }
        $rang = $this->berechneRaenge($knoten, $nachfolger, $eingang);

        $sortiert = $knoten;
        usort($sortiert, static fn (int $a, int $b): int => [$rang[$a], $a] <=> [$rang[$b], $b]);
        $pos = [];
        $zaehler = [];
        foreach ($sortiert as $k) {
            $r = $rang[$k];
            $spalte = $zaehler[$r] ?? 0;
            $pos[$k] = ['rang' => $r, 'spalte' => $spalte];
            $zaehler[$r] = $spalte + 1;
        }

        return [
            'pos' => $pos,
            'maxRang' => $rang === [] ? 0 : max($rang),
            'maxSpalten' => $zaehler === [] ? 0 : max($zaehler),
        ];
    }

    /**
     * Bestimmt je Knoten den laengsten Pfad vom Start (topologisch, Kahn).
     *
     * @param list<int>                $knoten     Schritt-Ids.
     * @param array<int,list<int>>     $nachfolger Nachfolger je Knoten.
     * @param array<int,int>           $eingang    Eingangsgrad je Knoten.
     * @return array<int,int> Rang je Knoten.
     */
    private function berechneRaenge(array $knoten, array $nachfolger, array $eingang): array
    {
        $rang = [];
        $warteschlange = [];
        foreach ($knoten as $k) {
            $rang[$k] = 0;
            if ($eingang[$k] === 0) {
                $warteschlange[] = $k;
            }
        }
        sort($warteschlange);
        while ($warteschlange !== []) {
            $n = (int) array_shift($warteschlange);
            $neu = [];
            foreach ($nachfolger[$n] as $s) {
                if ($rang[$n] + 1 > $rang[$s]) {
                    $rang[$s] = $rang[$n] + 1;
                }
                $eingang[$s]--;
                if ($eingang[$s] === 0) {
                    $neu[] = $s;
                }
            }
            if ($neu !== []) {
                $warteschlange = array_merge($warteschlange, $neu);
                sort($warteschlange);
            }
        }

        return $rang;
    }
}