Class GraphShortestPathExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Convenience entry points for shortest-path queries. These default to Dijkstra; instantiate BellmanFordShortestPath<TVertex, TEdge, TWeight>, AStarShortestPath<TVertex, TEdge, TWeight>, or FloydWarshallAllShortestPaths<TVertex, TEdge, TWeight> directly when negative weights, a heuristic, or all-pairs results are needed.

public static class GraphShortestPathExtensions

Inheritance

object

GraphShortestPathExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

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

Finds the shortest path from source to target using Dijkstra's algorithm and the weights carried by the graph's WeightedEdge<TVertex, TWeight> edges.

public static ShortestPathResult<TVertex, TWeight> ShortestPath<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

ShortestPathResult<TVertex, TWeight>

The query result, unreachable when no path exists.

Type Parameters

TVertex

The vertex type.

TWeight

The numeric weight type.

Exceptions

NegativeWeightException

A negative edge weight was encountered.

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

Finds the shortest path from source to target using Dijkstra's algorithm and weightSelector to read edge weights.

public static ShortestPathResult<TVertex, TWeight> ShortestPath<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 weight.

Returns

ShortestPathResult<TVertex, TWeight>

The query result, unreachable when no path exists.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

NegativeWeightException

A negative edge weight was encountered.

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

Computes shortest paths from source to every reachable vertex using Dijkstra's algorithm and the weights carried by the graph's WeightedEdge<TVertex, TWeight> edges.

public static SingleSourceShortestPaths<TVertex, TWeight> ShortestPathsFrom<TVertex, TWeight>(this IReadOnlyGraph<TVertex, WeightedEdge<TVertex, TWeight>> graph, TVertex source) where TVertex : notnull where TWeight : INumber<TWeight>

Parameters

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

The graph to search.

source TVertex

The start vertex.

Returns

SingleSourceShortestPaths<TVertex, TWeight>

A queryable single-source result.

Type Parameters

TVertex

The vertex type.

TWeight

The numeric weight type.

Exceptions

NegativeWeightException

A negative edge weight was encountered.

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

Computes shortest paths from source to every reachable vertex using Dijkstra's algorithm and weightSelector to read edge weights.

public static SingleSourceShortestPaths<TVertex, TWeight> ShortestPathsFrom<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex source, 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.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

SingleSourceShortestPaths<TVertex, TWeight>

A queryable single-source result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

NegativeWeightException

A negative edge weight was encountered.

ShortestPathsFrom<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, TVertex, Func<TEdge, TWeight>, CancellationToken)

Computes shortest paths from source to every reachable vertex using Dijkstra's algorithm, observing cancellationToken between vertex settlements.

public static SingleSourceShortestPaths<TVertex, TWeight> ShortestPathsFrom<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex source, Func<TEdge, TWeight> weightSelector, CancellationToken cancellationToken) 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.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

SingleSourceShortestPaths<TVertex, TWeight>

A queryable single-source result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

NegativeWeightException

A negative edge weight was encountered.

OperationCanceledException

The token was cancelled.