Class NetworkAnalysis
- Namespace
- SpatialNET.Network
- Assembly
- SpatialNET.Network.dll
Searches on a network (ADR 0049), as extension methods on SpatialNET.Network.IGraph`2. They read only the part of the network they visit, in batches, and keep one entry per visited node.
public static class NetworkAnalysisInheritance
Inherited Members
Remarks
Blocked nodes are reached but not passed, disabled edges are left out, directions are respected (see SpatialNET.Network.TraversalOptions`2). Loops are never walked. Equal costs are decided by the order of the start nodes and of the edges from the host, so the same input gives the same output.
Thread-safe as far as the graph is: a search has no shared state.
Methods
FindUnsupplied<TNodeId, TEdgeId>(IGraph<TNodeId, TEdgeId>, IEnumerable<TNodeId>, IEnumerable<TNodeId>, TraversalOptions<TNodeId, TEdgeId>?, IProgress<SupplyProgress>?, CancellationToken)
The sinks no source supplies (ADR 0051), in the order of the sinks; see SpatialNET.Network.NetworkAnalysis.Supply``2(SpatialNET.Network.IGraph{``0,``1},System.Collections.Generic.IEnumerable{``0},System.Collections.Generic.IEnumerable{``0},SpatialNET.Network.TraversalOptions{``0,``1},System.IProgress{SpatialNET.Network.SupplyProgress},System.Threading.CancellationToken).
public static IEnumerable<TNodeId> FindUnsupplied<TNodeId, TEdgeId>(this IGraph<TNodeId, TEdgeId> graph, IEnumerable<TNodeId> sources, IEnumerable<TNodeId> sinks, TraversalOptions<TNodeId, TEdgeId>? options = null, IProgress<SupplyProgress>? progress = null, CancellationToken cancellationToken = default) where TNodeId : notnull, IEquatable<TNodeId> where TEdgeId : notnull, IEquatable<TEdgeId>Parameters
graphIGraph<TNodeId, TEdgeId>-
The network.
sourcesIEnumerable<TNodeId>-
The sources; duplicates are run once.
sinksIEnumerable<TNodeId>-
The sinks; duplicates are reported once.
optionsTraversalOptions<TNodeId, TEdgeId>?-
As for SpatialNET.Network.NetworkAnalysis.Supply``2(SpatialNET.Network.IGraph{``0,``1},System.Collections.Generic.IEnumerable{``0},System.Collections.Generic.IEnumerable{``0},SpatialNET.Network.TraversalOptions{``0,``1},System.IProgress{SpatialNET.Network.SupplyProgress},System.Threading.CancellationToken).
progressIProgress<SupplyProgress>?-
As for SpatialNET.Network.NetworkAnalysis.Supply``2(SpatialNET.Network.IGraph{``0,``1},System.Collections.Generic.IEnumerable{``0},System.Collections.Generic.IEnumerable{``0},SpatialNET.Network.TraversalOptions{``0,``1},System.IProgress{SpatialNET.Network.SupplyProgress},System.Threading.CancellationToken).
cancellationTokenCancellationToken-
Stops the search between two nodes.
Returns
- IEnumerable<TNodeId>
Type Parameters
TNodeIdTEdgeId
Exceptions
- ArgumentNullException
-
An argument is
null, or the weight of the options. - ArgumentOutOfRangeException
-
The options are invalid.
- ArgumentException
-
The weight is not length; while enumerating: a source or a sink is not in the graph.
- InvalidGraphException
-
While enumerating: the data cannot be a network.
- OperationCanceledException
-
While enumerating: the token was cancelled.
Reach<TNodeId, TEdgeId>(IGraph<TNodeId, TEdgeId>, IEnumerable<TNodeId>, TraversalOptions<TNodeId, TEdgeId>?, CancellationToken)
Every node that can be reached from the start nodes, in order of cost, lazily: stop early or stream into a table. Each node is reported once, with the start node of its cheapest way.
public static IEnumerable<ReachedNode<TNodeId, TEdgeId>> Reach<TNodeId, TEdgeId>(this IGraph<TNodeId, TEdgeId> graph, IEnumerable<TNodeId> starts, TraversalOptions<TNodeId, TEdgeId>? options = null, CancellationToken cancellationToken = default) where TNodeId : notnull, IEquatable<TNodeId> where TEdgeId : notnull, IEquatable<TEdgeId>Parameters
graphIGraph<TNodeId, TEdgeId>-
The network.
startsIEnumerable<TNodeId>-
The start nodes; duplicates are used once.
optionsTraversalOptions<TNodeId, TEdgeId>?-
Weight, switching state, type filters and maximum cost;
nullfor the defaults. cancellationTokenCancellationToken-
Stops the search between two nodes.
Returns
- IEnumerable<ReachedNode<TNodeId, TEdgeId>>
Type Parameters
TNodeIdTEdgeId
Remarks
One search from many start nodes far apart (for example every transformer of a city) runs as one wave through all
of their areas at once. Through a shard cache such as ShardedGraphBase it touches every shard again and
again, and the cache cannot keep up; in memory it keeps one entry per node of the whole network. For work over a
whole network, search from one start node (or one area) at a time, in the order of the shards.
Exceptions
- ArgumentNullException
-
graphorstartsisnull, or the weight of the options. - ArgumentOutOfRangeException
-
The options are invalid (fallback or
MaxCostnegative or NaN). - ArgumentException
-
While enumerating: a start node is not in the graph.
- InvalidGraphException
-
While enumerating: the data cannot be a network.
- OperationCanceledException
-
While enumerating: the token was cancelled.
ShortestPath<TNodeId, TEdgeId>(IGraph<TNodeId, TEdgeId>, TNodeId, TNodeId, TraversalOptions<TNodeId, TEdgeId>?, CancellationToken)
The cheapest way from one node to another (Dijkstra), or null if there is none.
public static NetworkPath<TNodeId, TEdgeId>? ShortestPath<TNodeId, TEdgeId>(this IGraph<TNodeId, TEdgeId> graph, TNodeId from, TNodeId to, TraversalOptions<TNodeId, TEdgeId>? options = null, CancellationToken cancellationToken = default) where TNodeId : notnull, IEquatable<TNodeId> where TEdgeId : notnull, IEquatable<TEdgeId>Parameters
graphIGraph<TNodeId, TEdgeId>-
The network.
fromTNodeId-
The start node. A blocked start node is not passed, so it reaches only itself.
toTNodeId-
The target node; it may be blocked, since it is only reached.
optionsTraversalOptions<TNodeId, TEdgeId>?-
Weight, switching state, type filters and maximum cost;
nullfor the defaults. cancellationTokenCancellationToken-
Stops the search between two nodes.
Returns
- NetworkPath<TNodeId, TEdgeId>?
Type Parameters
TNodeIdTEdgeId
Exceptions
- ArgumentNullException
-
An argument is
null, or the weight of the options. - ArgumentOutOfRangeException
-
The options are invalid.
- ArgumentException
-
fromortois not in the graph. - InvalidGraphException
-
The data cannot be a network.
- OperationCanceledException
-
The token was cancelled.
Supply<TNodeId, TEdgeId>(IGraph<TNodeId, TEdgeId>, IEnumerable<TNodeId>, IEnumerable<TNodeId>, TraversalOptions<TNodeId, TEdgeId>?, IProgress<SupplyProgress>?, CancellationToken)
For every sink the sources that supply it (ADR 0051), in the order of the sinks, after all runs. An empty list is a sink nobody supplies, more than one entry is multiple supply.
public static IEnumerable<SinkSupply<TNodeId>> Supply<TNodeId, TEdgeId>(this IGraph<TNodeId, TEdgeId> graph, IEnumerable<TNodeId> sources, IEnumerable<TNodeId> sinks, TraversalOptions<TNodeId, TEdgeId>? options = null, IProgress<SupplyProgress>? progress = null, CancellationToken cancellationToken = default) where TNodeId : notnull, IEquatable<TNodeId> where TEdgeId : notnull, IEquatable<TEdgeId>Parameters
graphIGraph<TNodeId, TEdgeId>-
The network.
sourcesIEnumerable<TNodeId>-
The sources; duplicates are run once.
sinksIEnumerable<TNodeId>-
The sinks; duplicates are reported once.
optionsTraversalOptions<TNodeId, TEdgeId>?-
Switching state and type filters;
nullfor the defaults. The weight must be length andMaxCostis ignored, since the runs are breadth-first searches without costs. progressIProgress<SupplyProgress>?-
Runs done of all runs; reported at most every 250 ms and at the end of the last run, on the calling thread.
cancellationTokenCancellationToken-
Stops the search between two nodes.
Returns
- IEnumerable<SinkSupply<TNodeId>>
Type Parameters
TNodeIdTEdgeId
Remarks
A sink is supplied by a source if the run of that source reaches and passes to it (hit kind SpatialNET.Network.TraceHitKind.Source or SpatialNET.Network.TraceHitKind.Reached); a blocked sink, or a sink that is another source, is not supplied by that run.
Exceptions
- ArgumentNullException
-
An argument is
null, or the weight of the options. - ArgumentOutOfRangeException
-
The options are invalid.
- ArgumentException
-
The weight is not length; while enumerating: a source or a sink is not in the graph.
- InvalidGraphException
-
While enumerating: the data cannot be a network.
- OperationCanceledException
-
While enumerating: the token was cancelled.
Trace<TNodeId, TEdgeId>(IGraph<TNodeId, TEdgeId>, IEnumerable<TNodeId>, TraversalOptions<TNodeId, TEdgeId>?, CancellationToken)
Runs one search per source (ADR 0051) and streams every node it reaches, in the order of the sources and, within a run, in order of cost. A node that several sources reach is reported once per source.
public static IEnumerable<TraceHit<TNodeId, TEdgeId>> Trace<TNodeId, TEdgeId>(this IGraph<TNodeId, TEdgeId> graph, IEnumerable<TNodeId> sources, TraversalOptions<TNodeId, TEdgeId>? options = null, CancellationToken cancellationToken = default) where TNodeId : notnull, IEquatable<TNodeId> where TEdgeId : notnull, IEquatable<TEdgeId>Parameters
graphIGraph<TNodeId, TEdgeId>-
The network.
sourcesIEnumerable<TNodeId>-
The sources; duplicates are run once. They are also the stops: a run does not pass another source.
optionsTraversalOptions<TNodeId, TEdgeId>?-
Weight, switching state, type filters and maximum cost;
nullfor the defaults. cancellationTokenCancellationToken-
Stops the search between two nodes.
Returns
- IEnumerable<TraceHit<TNodeId, TEdgeId>>
Type Parameters
TNodeIdTEdgeId
Remarks
A run does not pass blocked nodes and other sources; it reports them as SpatialNET.Network.TraceHitKind.Blocked and SpatialNET.Network.TraceHitKind.OtherSource. A blocked source gives only its own hit. A run keeps its memory only until its area is done. For the shard cache, pass the sources sorted by shard.
Exceptions
- ArgumentNullException
-
graphorsourcesisnull, or the weight of the options. - ArgumentOutOfRangeException
-
The options are invalid.
- ArgumentException
-
While enumerating: a source is not in the graph.
- InvalidGraphException
-
While enumerating: the data cannot be a network.
- OperationCanceledException
-
While enumerating: the token was cancelled.
TraceEdges<TNodeId, TEdgeId>(IGraph<TNodeId, TEdgeId>, IEnumerable<TNodeId>, TraversalOptions<TNodeId, TEdgeId>?, CancellationToken)
Every edge a run passes or enters (ADR 0051), once per source, in the order of the sources: the edges of a supply area, including the closing edges of a mesh and the edge that leads to a blocked node or another source.
public static IEnumerable<TracedEdge<TNodeId, TEdgeId>> TraceEdges<TNodeId, TEdgeId>(this IGraph<TNodeId, TEdgeId> graph, IEnumerable<TNodeId> sources, TraversalOptions<TNodeId, TEdgeId>? options = null, CancellationToken cancellationToken = default) where TNodeId : notnull, IEquatable<TNodeId> where TEdgeId : notnull, IEquatable<TEdgeId>Parameters
graphIGraph<TNodeId, TEdgeId>-
The network.
sourcesIEnumerable<TNodeId>-
The sources; duplicates are run once. They are also the stops.
optionsTraversalOptions<TNodeId, TEdgeId>?-
Weight, switching state, type filters and maximum cost;
nullfor the defaults. cancellationTokenCancellationToken-
Stops the search between two nodes.
Returns
- IEnumerable<TracedEdge<TNodeId, TEdgeId>>
Type Parameters
TNodeIdTEdgeId
Exceptions
- ArgumentNullException
-
graphorsourcesisnull, or the weight of the options. - ArgumentOutOfRangeException
-
The options are invalid.
- ArgumentException
-
While enumerating: a source is not in the graph.
- InvalidGraphException
-
While enumerating: the data cannot be a network.
- OperationCanceledException
-
While enumerating: the token was cancelled.