Class GraphKShortestPathsExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

K-shortest-path enumeration via Yen's algorithm, exposed as a lazy sequence: paths arrive in nondecreasing total weight and the caller controls the cost by how far it enumerates (Take(k) for the classic k-shortest query). Paths are simple (loopless) and vertex-distinct — parallel edges only influence the weight, where the cheapest one counts.

public static class GraphKShortestPathsExtensions

Inheritance

object

GraphKShortestPathsExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

EnumerateShortestPaths<TVertex, TWeight>(IReadOnlyGraph<TVertex, WeightedEdge<TVertex, TWeight>>, TVertex, TVertex)

Lazily enumerates the simple paths from source to target in nondecreasing total weight, using the weights carried by the graph's WeightedEdge<TVertex, TWeight> edges.

public static IEnumerable<ShortestPathResult<TVertex, TWeight>> EnumerateShortestPaths<TVertex, TWeight>(this IReadOnlyGraph<TVertex, WeightedEdge<TVertex, TWeight>> graph, TVertex source, TVertex target) where TVertex : notnull where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, WeightedEdge<TVertex, TWeight>>

The graph to search.

source TVertex

The start vertex.

target TVertex

The end vertex.

Returns

IEnumerable<ShortestPathResult<TVertex, TWeight>>

The simple paths, cheapest first.

Type Parameters

TVertex

The vertex type.

TWeight

The numeric weight type.

Exceptions

ArgumentException

Either endpoint is not in the graph.

NegativeWeightException

An edge with negative weight is encountered during enumeration.

InvalidOperationException

The graph lost an edge of an already-yielded path between enumeration steps.

EnumerateShortestPaths<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, TVertex, TVertex, Func<TEdge, TWeight>)

Lazily enumerates the simple paths from source to target in nondecreasing total weight (Yen's algorithm over repeated Dijkstra runs). An unreachable target yields an empty sequence.

public static IEnumerable<ShortestPathResult<TVertex, TWeight>> EnumerateShortestPaths<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex source, TVertex target, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to search.

source TVertex

The start vertex.

target TVertex

The end vertex.

weightSelector Func<TEdge, TWeight>

Maps an edge to its (non-negative) weight.

Returns

IEnumerable<ShortestPathResult<TVertex, TWeight>>

The simple paths, cheapest first.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

ArgumentException

Either endpoint is not in the graph.

NegativeWeightException

An edge with negative weight is encountered during enumeration.

InvalidOperationException

The graph lost an edge of an already-yielded path between enumeration steps.