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
NetworkAnalysisinSpatialNET.Network, nebenReachundShortestPath(ADR 0049); Optionen sind dieTraversalOptionsvon 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)liefertIEnumerable<TraceHit<TNodeId, TEdgeId>>:TraceHit(Node, TypeId, Source, Cost, Via, Kind)mitKindausSource(die Quelle selbst, Kosten 0),Reached,Blocked(erreicht, aber nicht durchlaufen) undOtherSource(eine andere Quelle desselben Aufrufs, erreicht, aber nicht durchlaufen).Viaist 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
sourceslaufen einmal. - Richtungen werden beachtet (ADR 0049); in einem Netzwerk mit Fließrichtung läuft der Trace nur stromabwärts.
TraceEdges(sources, options, cancellationToken)liefertIEnumerable<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; dieVia-Kanten ausTracebilden nur einen Baum und lassen die schließenden Kanten einer Masche aus.Supply(sources, sinks, options, cancellationToken)liefertIEnumerable<SinkSupply<TNodeId>>(Sink, Sources)für jede Senke, in der Reihenfolge vonsinks, 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 einIProgress<SupplyProgress>(erledigte Quellen und ihre Gesamtzahl, wennsourceseine Sammlung ist), weil sie bis zum letzten Lauf still sind; gemeldet wird wie beim Builder (ADR 0050).TraceundTraceEdgesstreamen, ihre Ergebnisse sind also der Fortschritt.- Die Ergebnisse von
Supplykommen nach dem letzten Lauf, weil eine Senke auch von der letzten Quelle erreicht werden kann;TraceundTraceEdgesstreamen ab dem ersten Treffer. SupplyundFindUnsuppliedbrauchen keine Kosten und laufen als Breitensuche;MaxCostwird dann nicht beachtet, und ein anderes Gewicht als Länge ist eineArgumentException.
- Die Ergebnisse von
- 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
Supplymerkt sich seine Einträge pro Senke. - Reihenfolge und Cache: Die Läufe fragen
IGraphgestapelt 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 vonInvalidGraphException; Ausnahmen des Hosts laufen durch;OperationCanceledExceptionbei 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,
Supplygleich der Referenz für jede Senke,TraceEdgesgleich 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ürSupplyü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;
Supplyliefert 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
Traceeine 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ürSupplyundFindUnsupplied) - 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)