Tracing: one run per source, supply areas and the supply of sinks
The question a utility network is mostly asked is not the shortest path but who is supplied by whom: which customers hang on transformer 4711, which customers no transformer reaches, and which ones two transformers reach at once, which in a low-voltage network is usually a mistake in the switching state or the data. SpatialNET answers it with a trace on IGraph (ADR 0049). The host names the sources (for example all transformers of an area) and, where it asks about supply, the sinks (for example the customers). The trace runs from each source on its own, stops at blocked nodes and at other sources, and streams what it reaches. A node that two sources reach is therefore reported once per source, so multiple supply becomes visible instead of hidden. The memory a run needs is bounded by one supply area, not by the whole network, and a trace over all 10,000 transformers of a network keeps the shard cache warm when the sources come sorted by shard.
German version: 0051-tracing-pro-quelle-versorgung.de.md
Consequences
- Placement: static class
NetworkAnalysisinSpatialNET.Network, next toReachandShortestPath(ADR 0049); options are theTraversalOptionsfrom there (weight, state, edge and node types,MaxCost). - Sources and sinks are what the host passes, not roles in the model: a node is a source because it is in the list of sources of this call. The same transformer is a source for the low-voltage trace and a sink for a medium-voltage one.
Trace(sources, options, cancellationToken)returnsIEnumerable<TraceHit<TNodeId, TEdgeId>>:TraceHit(Node, TypeId, Source, Cost, Via, Kind)withKindone ofSource(the source itself, cost 0),Reached,Blocked(reached but not passed) andOtherSource(another source of the same call, reached but not passed).Viais the edge over which the node was reached first; none for the source.- One run per source, in the order of
sources; within a run in order of cost (Dijkstra with the chosen weight, default length). The cost is that of the cheapest way from this source, for example the cable length from the transformer. - A run does not pass blocked nodes (normal state or deviation, ADR 0049) and other sources. Without the second stop a trace in a meshed network would run through every station into the whole network.
- A blocked source gives only its own hit with
Kind = Blocked: a transformer out of service supplies nothing. - A node that several sources reach appears once per source. Duplicates in
sourcesare run once. - Directions are respected (ADR 0049); for a network with a direction of flow the trace runs downstream only.
TraceEdges(sources, options, cancellationToken)returnsIEnumerable<TracedEdge<TNodeId, TEdgeId>>(Edge, Source): every edge a run passes or enters, once per source, also the edge that leads to a blocked node or another source. With it the host draws a supply area as lines; theViaedges ofTraceform only a tree and miss the closing edges of a mesh.Supply(sources, sinks, options, cancellationToken)returnsIEnumerable<SinkSupply<TNodeId>>(Sink, Sources)for every sink, in the order ofsinks, after all runs: an empty list means not supplied, more than one entry means multiple supply. It keeps one small entry per sink (for 500,000 customers some tens of megabytes) and one supply area at a time.FindUnsupplied(sources, sinks, options, cancellationToken)returns only the sinks with an empty list. Both take an optionalIProgress<SupplyProgress>(sources done, and their total ifsourcesis a collection), because they are silent until the last run; it is reported as for the builder (ADR 0050).TraceandTraceEdgesstream, so their results are the progress.- The results of
Supplycome after the last run, because a sink can be reached by the last source;TraceandTraceEdgesstream from the first hit. SupplyandFindUnsuppliedneed no costs and run as a breadth-first search;MaxCostis then ignored, and setting a weight other than length is anArgumentException.
- The results of
- Memory: a run keeps one entry per visited node of its area and frees it when the area is done. In radial low-voltage networks an area has some hundreds to a few thousand nodes. The whole-network case of ADR 0049 (one visited set over millions of nodes) does not arise; only
Supplykeeps its entries per sink. - Order and the cache: the runs ask
IGraphfor the frontier of the current area in batches. If the host passes the sources sorted by shard, consecutive runs use the same shards, and a trace over all transformers loads each shard about once. This is a recommendation, not a rule; the result does not depend on the order of the sources except for the order of the output. - Determinism: the same sources, sinks and data in the same order give the same hits in the same order; equal costs are decided by the order of the edges from the host, as in ADR 0049.
- Exceptions as in ADR 0049: an unknown source or sink id throws
ArgumentException; the data errors ofInvalidGraphException; exceptions of the host pass through;OperationCanceledExceptionon cancellation. - Tests (ADR 0008): a reference in the test project that runs a plain breadth-first search and Bellman-Ford per source, compared with CsCheck on random graphs: the same nodes per source, the same costs, stops at blocked nodes and other sources, a blocked source supplies nothing, multiple supply found,
Supplyequal to the reference for every sink,TraceEdgesequal to every edge with an end in the area, and the same output for the same input. Hand-written cases for two transformers with an open and a closed separation point, a ring fed from both sides, directed edges and duplicate sources. - Benchmark:
NetworkBenchmarks(ADR 0049) gets a case forSupplyover the synthetic network with 10,000 sources and 500,000 sinks, with the sources sorted by shard and shuffled, and records time, memory and shard loads. - Playground: in the network view (ADR 0050) nodes can be marked as sources; the view colours each supply area and marks sinks that are not or multiply supplied.
Considered Options
- One wave from all sources at once that labels each node with the nearest source (rejected: it hides multiple supply, which is the error the host looks for, and needs one visited set over the whole network)
- One hit per node with a list of all its sources (rejected: the list is only known when every run is done, which again needs memory over the whole network;
Supplygives exactly this form for the sinks, where the host needs it) - Stopping only at blocked nodes, not at other sources (rejected: in a meshed network every run would cross every station and cover the whole network)
- A breadth-first search for
Tracetoo (rejected: the cost from the source, such as the cable length, is wanted, and Dijkstra on one supply area costs little; the breadth-first search stays forSupplyandFindUnsupplied) - Roles source and sink in the model, or a parameter with barrier types (rejected: the list of sources of a call says what a source is; barriers by type are an
INetworkStatethat blocks by type, ADR 0049) - Only the tree edges (
Via) for the supply area (rejected: in a mesh they leave out the closing edges, and the drawn area would have gaps) - Running the sources in parallel (rejected for now: the order of the output and the shard cache are simpler in sequence; the benchmark decides)