Table of Contents

Tracing: ein Lauf pro Quelle, Versorgungsgebiete und die Versorgung von Senken

Die Frage, die einem Leitungsnetz am häufigsten gestellt wird, ist nicht der kürzeste Weg, sondern wer von wem versorgt wird: welche Kunden an Trafo 4711 hängen, welche Kunden kein Trafo erreicht und welche zwei Trafos zugleich erreichen, was in einem Niederspannungsnetz meist ein Fehler im Schaltzustand oder in den Daten ist. SpatialNET beantwortet sie mit einem Trace auf IGraph (ADR 0049). Der Host nennt die Quellen (z. B. alle Trafos eines Gebiets) und, wo er nach Versorgung fragt, die Senken (z. B. die Kunden). Der Trace läuft von jeder Quelle für sich, hält an gesperrten Knoten und an anderen Quellen und streamt, was er erreicht. Ein Knoten, den zwei Quellen erreichen, wird deshalb einmal pro Quelle gemeldet, Mehrfachversorgung wird also sichtbar statt verdeckt. Der Speicher eines Laufs ist durch ein Versorgungsgebiet begrenzt, nicht durch das ganze Netzwerk, und ein Trace über alle 10.000 Trafos eines Netzes hält den Shard-Cache warm, wenn die Quellen nach Shard sortiert kommen.

English version: 0051-tracing-pro-quelle-versorgung.md

Consequences

  • Ort: statische Klasse NetworkAnalysis in SpatialNET.Network, neben Reach und ShortestPath (ADR 0049); Optionen sind die TraversalOptions von dort (Gewicht, Zustand, Kanten- und Knotentypen, MaxCost).
  • Quellen und Senken übergibt der Host, sie sind keine Rollen im Modell: Ein Knoten ist Quelle, weil er in der Liste der Quellen dieses Aufrufs steht. Derselbe Trafo ist Quelle für den Niederspannungs-Trace und Senke für einen Mittelspannungs-Trace.
  • Trace(sources, options, cancellationToken) liefert IEnumerable<TraceHit<TNodeId, TEdgeId>>:
    • TraceHit(Node, TypeId, Source, Cost, Via, Kind) mit Kind aus Source (die Quelle selbst, Kosten 0), Reached, Blocked (erreicht, aber nicht durchlaufen) und OtherSource (eine andere Quelle desselben Aufrufs, erreicht, aber nicht durchlaufen). Via ist die Kante, über die der Knoten zuerst erreicht wurde; keine bei der Quelle.
    • Ein Lauf pro Quelle, in der Reihenfolge von sources; innerhalb eines Laufs nach Kosten (Dijkstra mit dem gewählten Gewicht, Standard Länge). Die Kosten sind die des günstigsten Wegs von dieser Quelle, z. B. die Kabellänge ab dem Trafo.
    • Ein Lauf durchläuft keine gesperrten Knoten (Normalzustand oder Abweichung, ADR 0049) und keine anderen Quellen. Ohne den zweiten Halt liefe ein Trace in einem vermaschten Netz durch jede Station ins ganze Netzwerk.
    • Eine gesperrte Quelle liefert nur ihren eigenen Treffer mit Kind = Blocked: Ein Trafo außer Betrieb versorgt nichts.
    • Ein Knoten, den mehrere Quellen erreichen, erscheint einmal pro Quelle. Doppelte Einträge in sources laufen einmal.
    • Richtungen werden beachtet (ADR 0049); in einem Netzwerk mit Fließrichtung läuft der Trace nur stromabwärts.
  • TraceEdges(sources, options, cancellationToken) liefert IEnumerable<TracedEdge<TNodeId, TEdgeId>>(Edge, Source): jede Kante, die ein Lauf durchläuft oder betritt, einmal pro Quelle, auch die Kante, die zu einem gesperrten Knoten oder einer anderen Quelle führt. Damit zeichnet der Host ein Versorgungsgebiet als Linien; die Via-Kanten aus Trace bilden nur einen Baum und lassen die schließenden Kanten einer Masche aus.
  • Supply(sources, sinks, options, cancellationToken) liefert IEnumerable<SinkSupply<TNodeId>>(Sink, Sources) für jede Senke, in der Reihenfolge von sinks, nach allen Läufen: Eine leere Liste heißt nicht versorgt, mehr als ein Eintrag heißt mehrfach versorgt. Es merkt sich einen kleinen Eintrag pro Senke (für 500.000 Kunden einige zehn Megabyte) und jeweils ein Versorgungsgebiet. FindUnsupplied(sources, sinks, options, cancellationToken) liefert nur die Senken mit leerer Liste. Beide nehmen optional ein IProgress<SupplyProgress> (erledigte Quellen und ihre Gesamtzahl, wenn sources eine Sammlung ist), weil sie bis zum letzten Lauf still sind; gemeldet wird wie beim Builder (ADR 0050). Trace und TraceEdges streamen, ihre Ergebnisse sind also der Fortschritt.
    • Die Ergebnisse von Supply kommen nach dem letzten Lauf, weil eine Senke auch von der letzten Quelle erreicht werden kann; Trace und TraceEdges streamen ab dem ersten Treffer.
    • Supply und FindUnsupplied brauchen keine Kosten und laufen als Breitensuche; MaxCost wird dann nicht beachtet, und ein anderes Gewicht als Länge ist eine ArgumentException.
  • Speicher: Ein Lauf merkt sich einen Eintrag pro besuchtem Knoten seines Gebiets und gibt ihn frei, wenn das Gebiet fertig ist. In radialen Niederspannungsnetzen hat ein Gebiet einige hundert bis wenige tausend Knoten. Der Fall „ganzes Netzwerk“ aus ADR 0049 (eine Besucht-Menge über Millionen Knoten) entsteht nicht; nur Supply merkt sich seine Einträge pro Senke.
  • Reihenfolge und Cache: Die Läufe fragen IGraph gestapelt nach der Front des aktuellen Gebiets. Übergibt der Host die Quellen nach Shard sortiert, benutzen aufeinanderfolgende Läufe dieselben Shards, und ein Trace über alle Trafos lädt jeden Shard etwa einmal. Das ist eine Empfehlung, keine Regel; das Ergebnis hängt außer in der Reihenfolge der Ausgabe nicht von der Reihenfolge der Quellen ab.
  • Determinismus: Dieselben Quellen, Senken und Daten in derselben Reihenfolge ergeben dieselben Treffer in derselben Reihenfolge; gleiche Kosten entscheidet die Reihenfolge der Kanten vom Host, wie in ADR 0049.
  • Ausnahmen wie in ADR 0049: Eine unbekannte Quell- oder Senken-ID wirft ArgumentException; die Datenfehler von InvalidGraphException; Ausnahmen des Hosts laufen durch; OperationCanceledException bei Abbruch.
  • Tests (ADR 0008): Eine Referenz im Testprojekt, die pro Quelle eine einfache Breitensuche und Bellman-Ford rechnet, verglichen mit CsCheck auf Zufallsgraphen: dieselben Knoten pro Quelle, dieselben Kosten, Halt an gesperrten Knoten und anderen Quellen, eine gesperrte Quelle versorgt nichts, Mehrfachversorgung gefunden, Supply gleich der Referenz für jede Senke, TraceEdges gleich jeder Kante mit einem Ende im Gebiet, und dieselbe Ausgabe für dieselbe Eingabe. Handgeschriebene Fälle für zwei Trafos mit offener und geschlossener Trennstelle, einen von beiden Seiten gespeisten Ring, gerichtete Kanten und doppelte Quellen.
  • Benchmark: NetworkBenchmarks (ADR 0049) bekommt einen Fall für Supply über das synthetische Netzwerk mit 10.000 Quellen und 500.000 Senken, mit nach Shard sortierten und gemischten Quellen, und misst Zeit, Speicher und Shard-Ladevorgänge.
  • Playground: In der Netzwerk-Ansicht (ADR 0050) lassen sich Knoten als Quellen markieren; die Ansicht färbt jedes Versorgungsgebiet und markiert nicht oder mehrfach versorgte Senken.

Considered Options

  • Eine Welle von allen Quellen zugleich, die jeden Knoten mit der nächsten Quelle beschriftet (verworfen: Sie verdeckt Mehrfachversorgung, also genau den Fehler, den der Host sucht, und braucht eine Besucht-Menge über das ganze Netzwerk)
  • Ein Treffer pro Knoten mit einer Liste aller seiner Quellen (verworfen: Die Liste steht erst fest, wenn alle Läufe fertig sind, was wieder Speicher über das ganze Netzwerk braucht; Supply liefert genau diese Form für die Senken, wo der Host sie braucht)
  • Nur an gesperrten Knoten halten, nicht an anderen Quellen (verworfen: In einem vermaschten Netz liefe jeder Lauf über jede Station und deckte das ganze Netzwerk ab)
  • Auch für Trace eine Breitensuche (verworfen: Die Kosten ab der Quelle, etwa die Kabellänge, sind gewünscht, und Dijkstra auf einem Versorgungsgebiet kostet wenig; die Breitensuche bleibt für Supply und FindUnsupplied)
  • Rollen Quelle und Senke im Modell, oder ein Parameter mit Sperr-Typen (verworfen: Die Liste der Quellen eines Aufrufs sagt, was eine Quelle ist; Sperren nach Typ sind ein INetworkState, der nach Typ sperrt, ADR 0049)
  • Nur die Baumkanten (Via) für das Versorgungsgebiet (verworfen: In einer Masche fehlen die schließenden Kanten, und das gezeichnete Gebiet hätte Lücken)
  • Die Quellen parallel laufen lassen (vorerst verworfen: Reihenfolge der Ausgabe und Shard-Cache sind nacheinander einfacher; der Benchmark entscheidet)