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.

→ Mathematik-Units · std.grid · Graphdatenbank

import std.graph;

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

<WRAP info> Graph* war belegt. Die 65 Graph*-Funktionen im Bestand gehören zur 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>

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.

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;
}

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

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.

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;
}

Dijkstra    dist[1] : 2.000000
BellmanFord dist[1] : 1.000000
Rueckgabe BellmanFord: 1

<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>

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.

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.

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

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

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;
}

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

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.

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

• 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 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.