Class FloydWarshallAllShortestPaths<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

The Floyd-Warshall all-pairs shortest-path algorithm. Supports negative edge weights; throws NegativeCycleException when any negative cycle exists. Reachability is tracked explicitly, so weight types without an infinity value (int, decimal, ...) work unchanged.

public sealed class FloydWarshallAllShortestPaths<TVertex, TEdge, TWeight> where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Inheritance

object

FloydWarshallAllShortestPaths<TVertex, TEdge, TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Constructors

FloydWarshallAllShortestPaths(Func<TEdge, TWeight>)

Initializes the algorithm with the function that reads an edge's weight.

public FloydWarshallAllShortestPaths(Func<TEdge, TWeight> weightSelector)

Parameters

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Exceptions

ArgumentNullException

weightSelector is null.

Methods

Compute(IReadOnlyGraph<TVertex, TEdge>)

Computes shortest paths between every pair of vertices.

public AllPairsShortestPaths<TVertex, TWeight> Compute(IReadOnlyGraph<TVertex, TEdge> graph)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to analyze.

Returns

AllPairsShortestPaths<TVertex, TWeight>

A queryable all-pairs result.

Exceptions

NegativeCycleException

The graph contains a negative cycle.

Compute(IReadOnlyGraph<TVertex, TEdge>, CancellationToken)

Computes shortest paths between every pair of vertices, observing cancellationToken between pivot iterations.

public AllPairsShortestPaths<TVertex, TWeight> Compute(IReadOnlyGraph<TVertex, TEdge> graph, CancellationToken cancellationToken)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to analyze.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

AllPairsShortestPaths<TVertex, TWeight>

A queryable all-pairs result.

Exceptions

NegativeCycleException

The graph contains a negative cycle.

OperationCanceledException

The token was cancelled.