Table of Contents

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 NetworkAnalysis

Inheritance

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

graph IGraph<TNodeId, TEdgeId>

The network.

sources IEnumerable<TNodeId>

The sources; duplicates are run once.

sinks IEnumerable<TNodeId>

The sinks; duplicates are reported once.

options TraversalOptions<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).

progress IProgress<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).

cancellationToken CancellationToken

Stops the search between two nodes.

Returns

IEnumerable<TNodeId>

Type Parameters

TNodeId
TEdgeId

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

graph IGraph<TNodeId, TEdgeId>

The network.

starts IEnumerable<TNodeId>

The start nodes; duplicates are used once.

options TraversalOptions<TNodeId, TEdgeId>?

Weight, switching state, type filters and maximum cost; null for the defaults.

cancellationToken CancellationToken

Stops the search between two nodes.

Returns

IEnumerable<ReachedNode<TNodeId, TEdgeId>>

Type Parameters

TNodeId
TEdgeId

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

graph or starts is null, or the weight of the options.

ArgumentOutOfRangeException

The options are invalid (fallback or MaxCost negative 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

graph IGraph<TNodeId, TEdgeId>

The network.

from TNodeId

The start node. A blocked start node is not passed, so it reaches only itself.

to TNodeId

The target node; it may be blocked, since it is only reached.

options TraversalOptions<TNodeId, TEdgeId>?

Weight, switching state, type filters and maximum cost; null for the defaults.

cancellationToken CancellationToken

Stops the search between two nodes.

Returns

NetworkPath<TNodeId, TEdgeId>?

Type Parameters

TNodeId
TEdgeId

Exceptions

ArgumentNullException

An argument is null, or the weight of the options.

ArgumentOutOfRangeException

The options are invalid.

ArgumentException

from or to is 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

graph IGraph<TNodeId, TEdgeId>

The network.

sources IEnumerable<TNodeId>

The sources; duplicates are run once.

sinks IEnumerable<TNodeId>

The sinks; duplicates are reported once.

options TraversalOptions<TNodeId, TEdgeId>?

Switching state and type filters; null for the defaults. The weight must be length and MaxCost is ignored, since the runs are breadth-first searches without costs.

progress IProgress<SupplyProgress>?

Runs done of all runs; reported at most every 250 ms and at the end of the last run, on the calling thread.

cancellationToken CancellationToken

Stops the search between two nodes.

Returns

IEnumerable<SinkSupply<TNodeId>>

Type Parameters

TNodeId
TEdgeId

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

graph IGraph<TNodeId, TEdgeId>

The network.

sources IEnumerable<TNodeId>

The sources; duplicates are run once. They are also the stops: a run does not pass another source.

options TraversalOptions<TNodeId, TEdgeId>?

Weight, switching state, type filters and maximum cost; null for the defaults.

cancellationToken CancellationToken

Stops the search between two nodes.

Returns

IEnumerable<TraceHit<TNodeId, TEdgeId>>

Type Parameters

TNodeId
TEdgeId

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

graph or sources is null, 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

graph IGraph<TNodeId, TEdgeId>

The network.

sources IEnumerable<TNodeId>

The sources; duplicates are run once. They are also the stops.

options TraversalOptions<TNodeId, TEdgeId>?

Weight, switching state, type filters and maximum cost; null for the defaults.

cancellationToken CancellationToken

Stops the search between two nodes.

Returns

IEnumerable<TracedEdge<TNodeId, TEdgeId>>

Type Parameters

TNodeId
TEdgeId

Exceptions

ArgumentNullException

graph or sources is null, 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.