====== std.graph — Graphalgorithmen ======

Gewichtete Graphen in CSR-Darstellung: BFS/DFS, topologische Sortierung, Dijkstra und Bellman-Ford, minimaler Spannbaum, Zusammenhangskomponenten, starke Komponenten, Zweifärbbarkeit und Max-Flow nach Dinic mit minimalem Schnitt.

→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:grid|std.grid]] · [[lyx_-_programmiersprache:units:graphdb|Graphdatenbank]]

<code lyx>
import std.graph;
</code>

Schicht 0, hängt an ''std.math'' und ''std.alloc''. 45 Funktionen. Alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt.

----

===== Warum das Präfix ''Gph'' heißt =====

<WRAP info>
**''Graph*'' war belegt.** Die 65 ''Graph*''-Funktionen im Bestand gehören zur [[lyx_-_programmiersprache:units:graphdb|Graphdatenbank]] — Knoten, Kanten, Attribute, Zeit- und Typindizes, Musterabfragen. Das ist ein **Wissensgraph**, kein Algorithmenpaket: dort gibt es keinen Dijkstra, keine topologische Sortierung, keinen Spannbaum.

''std.grid'' konnte Pfadfindung, aber nur auf Gittern. Straßennetze, Abhängigkeitsgraphen und Ablaufpläne sind keine Gitter — diese Lücke schließt ''std.graph''.
</WRAP>

----

===== Aufbau: erst füllen, dann bauen =====

Ein Graph wird in zwei Schritten benutzt. ''GphAddEdge'' sammelt die Kanten, ''GphBuild'' überführt sie in die CSR-Darstellung. **Vor ''GphBuild'' liefert kein Algorithmus ein Ergebnis**, danach nimmt der Graph keine Kanten mehr an.

<code lyx>
unit main;
import std.io;
import std.string;
import std.alloc;
import std.graph;

fn ZF(t: pchar, v: f64): void { Print(t); PrintF64(v); }
fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }

fn main(): int64 {
    var g: int64 := GphNew(5, 8, true);       // 5 Knoten, Platz für 8 Kanten, gerichtet
    GphAddEdge(g, 0, 1, 4.0);
    GphAddEdge(g, 0, 2, 1.0);
    GphAddEdge(g, 2, 1, 2.0);
    GphAddEdge(g, 1, 3, 5.0);
    GphAddEdge(g, 2, 3, 8.0);
    GphAddEdge(g, 3, 4, 3.0);
    GphBuild(g);

    ZI("Knoten   : ", GphNodeCount(g));
    ZI("Kanten   : ", GphEdgeCount(g));
    ZI("Grad(0)  : ", GphDegree(g, 0));
    ZI("HasCycle : ", GphHasCycle(g) as int64);

    var dist: int64 := alloc(5 * 8);
    var prev: int64 := alloc(5 * 8);
    GphDijkstra(g, 0, dist, prev);
    ZF("dist[1]  : ", peekf64(dist + 8));
    ZF("dist[3]  : ", peekf64(dist + 24));
    ZF("dist[4]  : ", peekf64(dist + 32));

    var order: int64 := alloc(5 * 8);
    var cnt: int64 := GphTopoSort(g, order);
    Print("TopoSort : ");
    var i: int64 := 0;
    while (i < cnt) { Print(IntToStr(peek64(order + i * 8))); Print(" "); i := i + 1; }
    PrintLn("");

    var path: int64 := alloc(5 * 8);
    var plen: int64 := GphPathFrom(prev, 4, path, 5);
    Print("Pfad 0->4: ");
    i := 0;
    while (i < plen) { Print(IntToStr(peek64(path + i * 8))); Print(" "); i := i + 1; }
    PrintLn("");
    GphFree(g);
    return 0;
}
</code>

<code>
Knoten   : 5
Kanten   : 6
Grad(0)  : 2
HasCycle : 0
dist[1]  : 3.000000
dist[3]  : 8.000000
dist[4]  : 11.000000
TopoSort : 0 2 1 3 4
Pfad 0->4: 0 2 1 3 4
</code>

''dist[1]'' ist **3**, nicht 4: der Weg über Knoten 2 (1+2) ist kürzer als die direkte Kante (4). ''GphPathFrom'' setzt aus dem ''prev''-Feld den Weg zusammen — es braucht die Höchstlänge als Argument und liefert die tatsächliche zurück.

**''GphFree'' gehört dazu.** ''GphNew'' reserviert Speicher, den kein Aufräumen von selbst zurückgibt.

----

===== Kürzeste Wege: die Wahl ist keine Geschmacksfrage =====

<code lyx>
unit main;
import std.io;
import std.string;
import std.alloc;
import std.graph;

fn ZF(t: pchar, v: f64): void { Print(t); PrintF64(v); }

fn main(): int64 {
    // 0->1 = 2 ; 0->2 = 5 ; 2->1 = -4    richtig ist dist[1] = 1
    var g: int64 := GphNew(3, 4, true);
    GphAddEdge(g, 0, 1,  2.0);
    GphAddEdge(g, 0, 2,  5.0);
    GphAddEdge(g, 2, 1, -4.0);
    GphBuild(g);

    var d1: int64 := alloc(3 * 8);
    var p1: int64 := alloc(3 * 8);
    GphDijkstra(g, 0, d1, p1);
    ZF("Dijkstra    dist[1] : ", peekf64(d1 + 8));

    var d2: int64 := alloc(3 * 8);
    var p2: int64 := alloc(3 * 8);
    var rc: int64 := GphBellmanFord(g, 0, d2, p2);
    ZF("BellmanFord dist[1] : ", peekf64(d2 + 8));
    Print("Rueckgabe BellmanFord: "); PrintLn(IntToStr(rc));
    GphFree(g);
    return 0;
}
</code>

<code>
Dijkstra    dist[1] : 2.000000
BellmanFord dist[1] : 1.000000
Rueckgabe BellmanFord: 1
</code>

<WRAP alert>
**Dijkstra liefert hier ein falsches Ergebnis — stillschweigend.** Der richtige Weg ist ''0 → 2 → 1'' mit 5 − 4 = **1**; Dijkstra meldet 2. Es gibt keine Fehleranzeige, das Ergebnis sieht gültig aus.

Der Grund: Dijkstra erklärt einen Knoten für abgeschlossen, sobald er ihn zum ersten Mal erreicht, und kommt darauf nicht zurück. Knoten 1 wird über die direkte Kante mit 2 abgeschlossen, **bevor** der billigere Umweg über Knoten 2 sichtbar wird. **Bei negativen Kantengewichten gehört Bellman-Ford hierher, ohne Ausnahme.**
</WRAP>

<box tip>
> **Dieses Gegenbeispiel ist sorgfältig gewählt.** Eine negative Kante allein genügt **nicht**, um Dijkstra zu Fall zu bringen — beim ersten Versuch lieferte er zufällig das richtige Ergebnis, weil der Zielknoten noch nicht abgeschlossen war. Der Fehler tritt nur auf, wenn eine negative Kante einen **bereits abgeschlossenen** Knoten betrifft. Wer das beim Prüfen nicht trifft, hat einen grünen Test ohne Aussage.
</box>

''GphBellmanFord'' gibt **1** zurück, wenn alles in Ordnung ist, und **0**, wenn ein **negativer Zyklus** gefunden wurde — dann gibt es keine kürzesten Wege, und die Distanzen sind bedeutungslos. Unerreichbare Knoten trägt es als **−1** ein, nicht als Unendlich.

^ Verfahren ^ Voraussetzung ^ Aufwand ^
| ''GphBfs'' | ungewichtet (jede Kante zählt 1) | linear |
| ''GphDijkstra'' | **keine negativen Gewichte** | O(m log n) |
| ''GphBellmanFord'' | beliebige Gewichte, erkennt negative Zyklen | O(n·m) |

----

===== Struktur =====

^ Funktion ^ Liefert ^
| ''GphTopoSort(g, out)'' | Reihenfolge; **weniger als ''n'' Knoten heißt: der Graph hat einen Zyklus** |
| ''GphHasCycle(g)'' | direkt gefragt |
| ''GphComponents(g, outComp)'' | Zusammenhangskomponenten, Anzahl als Rückgabe |
| ''GphScc(g, outComp)'' | **stark** zusammenhängende Komponenten (gerichtet) |
| ''GphIsConnected(g)'' | ein Stück? |
| ''GphIsBipartite(g, outColor)'' | Zweifärbbarkeit, Färbung in ''outColor'' |
| ''GphReachable(g, s)'' | Anzahl von ''s'' aus erreichbarer Knoten |
| ''GphDfsOrder(g, s, outOrder)'' | Tiefensuche-Reihenfolge |

Der Rückgabewert von ''GphTopoSort'' ist die eigentliche Zyklenprüfung: eine topologische Sortierung existiert genau dann, wenn der Graph kreisfrei ist. Kommen weniger als ''GphNodeCount'' Knoten zurück, steckt der Rest in einem Zyklus.

==== Union-Find und Spannbaum ====

''GphMstKruskal(g, outEdges, outWeight)'' liefert den minimalen Spannbaum. Die zugrunde liegende Union-Find-Struktur ist einzeln nutzbar: ''GphUfNew'', ''GphUfFind'', ''GphUfUnion'', ''GphUfSame'', ''GphUfSize'', ''GphUfFree''.

----

===== Fluss und Schnitt =====

Flussnetze sind eine **eigene** Struktur — ''GphFlowNew'' statt ''GphNew'', mit eigenem ''Build'' und eigenem ''Free'':

<code lyx>
unit main;
import std.io;
import std.string;
import std.alloc;
import std.graph;

fn ZF(t: pchar, v: f64): void { Print(t); PrintF64(v); }

fn main(): int64 {
    var f: int64 := GphFlowNew(4, 5);
    GphFlowAddEdge(f, 0, 1, 3.0);
    GphFlowAddEdge(f, 0, 2, 2.0);
    GphFlowAddEdge(f, 1, 2, 1.0);
    GphFlowAddEdge(f, 1, 3, 2.0);
    GphFlowAddEdge(f, 2, 3, 3.0);
    GphFlowBuild(f);

    ZF("MaxFlow 0->3 : ", GphMaxFlow(f, 0, 3));

    var side: int64 := alloc(4 * 8);
    var cnt: int64 := GphMinCut(f, 0, side);
    Print("Knoten auf der Quellseite: "); PrintLn(IntToStr(cnt));
    Print("und zwar : ");
    var i: int64 := 0;
    while (i < 4) {
        if (peek64(side + i * 8) == 1) { Print(IntToStr(i)); Print(" "); }
        i := i + 1;
    }
    PrintLn("");
    GphFlowFree(f);
    return 0;
}
</code>

<code>
MaxFlow 0->3 : 5.000000
Knoten auf der Quellseite: 1
und zwar : 0
</code>

**5, nicht 4** — neben ''0→1→3'' (2) und ''0→2→3'' (2) trägt der Weg ''0→1→2→3'' noch eine weitere Einheit.

<box tip>
> **''GphMinCut'' gibt die Zahl der Knoten auf der Quellseite zurück, nicht die der Schnittkanten.** ''outSide'' bekommt je Knoten 1 oder 0. Hier bleibt nur Knoten 0 übrig: beide Kanten aus der Quelle sind ausgeschöpft (3+2 = 5), im Restnetz ist nichts mehr erreichbar. Das ist der Satz von Ford und Fulkerson in Zahlen — der größte Fluss ist genau so groß wie der kleinste Schnitt.
</box>

^ Funktion ^ Zweck ^
| ''GphFlowAddEdge(f, u, v, cap)'' | gerichtete Kante, gibt den Kantenindex zurück |
| ''GphFlowAddUndirected'' | Kapazität in beide Richtungen |
| ''GphMaxFlow(f, s, t)'' | Dinic |
| ''GphMinCut(f, s, outSide)'' | Schnitt aus dem Restnetz |
| ''GphFlowOn(f, k)'' | tatsächlicher Fluss über Kante ''k'' |
| ''GphFlowResidual(f, i)'' | verbleibende Kapazität |
| ''GphBipartiteMatch(g, nLeft, outMatch)'' | größte Zuordnung im bipartiten Graphen |

''GphFlowOn'' ist der Weg zur **Lösung** statt nur zum Wert: nach ''GphMaxFlow'' steht dort je Kante, wie viel tatsächlich fließt.

----

===== Grenzen =====

  * ''GphNew(n, maxEdges, directed)'' legt die Kantenzahl **im Voraus** fest — mehr Kanten nimmt ''GphAddEdge'' nicht an.
  * Kein Floyd-Warshall (alle Paare) und kein A* auf allgemeinen Graphen. A* auf Gittern hat [[lyx_-_programmiersprache:units:grid|std.grid]].
  * Knoten sind Zahlen von ''0'' bis ''n−1''. Wer Namen braucht, führt die Zuordnung selbst.

----

Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt; das Dijkstra-Gegenbeispiel und die Rückgabekonvention von ''GphMinCut'' einzeln nachgemessen bzw. aus der Quelle abgelesen.