Class OverlappingYensAlgorithm<TWeight>

Namespace

AlgorithmsSW.EdgeWeightedDigraph

Assembly

AlgorithmsSW.dll

This is like YensAlgorithm<TWeight>, but instead of looking for a fixed number of shortest paths, it looks for shortest paths until the intersection among all paths found is empty. This particular version is used to implement a more efficient version of finding critical edges.

[ExerciseReference(4, 4, 7)]
public class OverlappingYensAlgorithm<TWeight> : IKShortestPaths<TWeight> where TWeight : INumber<TWeight>, IMinMaxValue<TWeight>

Type Parameters

TWeight

The type of the edge weights.

Inheritance

object

OverlappingYensAlgorithm<TWeight>

Implements

IKShortestPaths<TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>)

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Interpolate<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Substitute<T, TBuffer>(TBuffer, (T input, T[] output)[])

Comparable.ToComparable<T>(T, IComparer<T>)

Formatter.AsText<T>(T?)

Formatter.Describe<TLabel, TDescription>(TLabel, TDescription, string)

Formatter.Log<T>(T)

Formatter.Pretty<T>(T, params int[])

Constructors

OverlappingYensAlgorithm(IEdgeWeightedDigraph<TWeight>, int, int)

Initializes a new instance of the OverlappingYensAlgorithm<TWeight> class.

public OverlappingYensAlgorithm(IEdgeWeightedDigraph<TWeight> digraph, int source, int target)

Parameters

digraph IEdgeWeightedDigraph<TWeight>

The directed graph in which to find the paths.

source int

The source vertex from where paths originate.

target int

The target vertex to which paths should lead.

Properties

CriticalEdges

public ISet<(int, int)>? CriticalEdges { get; }

Property Value

ISet<(int, int)>

PathRank

public int PathRank { get; }

Property Value

int

Methods

GetPath(int)

Gets the kth shortest path, if it exist, starting from 0, among all shortest paths that have a non-zero intersection.

public DirectedPath<TWeight> GetPath(int rank)

Parameters

rank int

The rank (lowest rank 0 is the shortest) of the path to get.

Returns

DirectedPath<TWeight>

The path with the given rank.

Exceptions

InvalidOperationException

A path of the given rank does not exist.

HasPath(int)

public bool HasPath(int k)

Parameters

k int

Returns

bool