Class UndirectedShortestPathAlgorithmBase<TVertex, TEdge>

Base class for all shortest path finder algorithms in undirected graphs.

Inheritance
System.Object
AlgorithmBase<IUndirectedGraph<TVertex, TEdge>>
RootedAlgorithmBase<TVertex, IUndirectedGraph<TVertex, TEdge>>
UndirectedShortestPathAlgorithmBase<TVertex, TEdge>
UndirectedDijkstraShortestPathAlgorithm<TVertex, TEdge>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: QuikGraph.Algorithms.ShortestPath
Assembly: QuikGraph.dll
Syntax
public abstract class UndirectedShortestPathAlgorithmBase<TVertex, TEdge> : RootedAlgorithmBase<TVertex, IUndirectedGraph<TVertex, TEdge>>, IAlgorithm<IUndirectedGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent, IVertexColorizerAlgorithm<TVertex>, IUndirectedTreeBuilderAlgorithm<TVertex, TEdge>, IDistancesCollection<TVertex> where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex

Vertex type.
TEdge

Edge type.

Constructors

| Improve this Doc View Source

UndirectedShortestPathAlgorithmBase(IAlgorithmComponent, IUndirectedGraph<TVertex, TEdge>, Func<TEdge, Double>)

Initializes a new instance of the UndirectedShortestPathAlgorithmBase<TVertex, TEdge> class.

Declaration
protected UndirectedShortestPathAlgorithmBase(IAlgorithmComponent host, IUndirectedGraph<TVertex, TEdge> visitedGraph, Func<TEdge, double> edgeWeights)
Parameters
Type Name Description
IAlgorithmComponent host

Host to use if set, otherwise use this reference.
IUndirectedGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Func<TEdge, System.Double> edgeWeights

Function that computes the weight for a given edge.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

edgeWeights is null.
| Improve this Doc View Source

UndirectedShortestPathAlgorithmBase(IAlgorithmComponent, IUndirectedGraph<TVertex, TEdge>, Func<TEdge, Double>, IDistanceRelaxer)

Initializes a new instance of the UndirectedShortestPathAlgorithmBase<TVertex, TEdge> class.

Declaration
protected UndirectedShortestPathAlgorithmBase(IAlgorithmComponent host, IUndirectedGraph<TVertex, TEdge> visitedGraph, Func<TEdge, double> edgeWeights, IDistanceRelaxer distanceRelaxer)
Parameters
Type Name Description
IAlgorithmComponent host

Host to use if set, otherwise use this reference.
IUndirectedGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Func<TEdge, System.Double> edgeWeights

Function that computes the weight for a given edge.
IDistanceRelaxer distanceRelaxer

Distance relaxer.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

edgeWeights is null.
System.ArgumentNullException

distanceRelaxer is null.

Properties

| Improve this Doc View Source

DistanceRelaxer

Distance relaxer.

Declaration
public IDistanceRelaxer DistanceRelaxer { get; }
Property Value
Type Description
IDistanceRelaxer
| Improve this Doc View Source

Distances

Vertices distances.

Declaration
[Obsolete("Use methods on IDistancesCollection to interact with the distances instead.")]
public IDictionary<TVertex, double> Distances { get; }
Property Value
Type Description
System.Collections.Generic.IDictionary<TVertex, System.Double>
| Improve this Doc View Source

VerticesColors

Stores vertices associated to their colors (treatment state).

Declaration
public IDictionary<TVertex, GraphColor> VerticesColors { get; }
Property Value
Type Description
System.Collections.Generic.IDictionary<TVertex, GraphColor>
| Improve this Doc View Source

Weights

Function that given an edge return the weight of this edge.

Declaration
public Func<TEdge, double> Weights { get; }
Property Value
Type Description
System.Func<TEdge, System.Double>

Methods

| Improve this Doc View Source

DistancesIndexGetter()

Gets the function that gives access to distances from a vertex.

Declaration
protected Func<TVertex, double> DistancesIndexGetter()
Returns
Type Description
System.Func<TVertex, System.Double>
| Improve this Doc View Source

GetDistance(TVertex)

Gets the distance associated to the given vertex.

Declaration
public double GetDistance(TVertex vertex)
Parameters
Type Name Description
TVertex vertex

The vertex to get the distance for.
Returns
Type Description
System.Double

The distance associated with the vertex.
Exceptions
Type Condition
System.InvalidOperationException

Algorithm has not been run.
| Improve this Doc View Source

GetDistances()

Gets the distances for all vertices currently known.

Declaration
public IEnumerable<KeyValuePair<TVertex, double>> GetDistances()
Returns
Type Description
System.Collections.Generic.IEnumerable<System.Collections.Generic.KeyValuePair<TVertex, System.Double>>

The System.Collections.Generic.KeyValuePair{Vertex,Distance} for the known vertices.
| Improve this Doc View Source

GetVertexColor(TVertex)

Gets the GraphColor associated to the given vertex.

Declaration
public GraphColor GetVertexColor(TVertex vertex)
Parameters
Type Name Description
TVertex vertex

The vertex.
Returns
Type Description
GraphColor

The vertex GraphColor.
Exceptions
Type Condition
System.ArgumentNullException

vertex is null.
VertexNotFoundException

vertex has no associated color.
| Improve this Doc View Source

GetVertexDistance(TVertex)

Gets the distance associated to the given vertex.

Declaration
protected double GetVertexDistance(TVertex vertex)
Parameters
Type Name Description
TVertex vertex

The vertex to get the distance for.
Returns
Type Description
System.Double
| Improve this Doc View Source

Initialize()

Called on algorithm initialization step.

Declaration
protected override void Initialize()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IUndirectedGraph<TVertex, TEdge>>.Initialize()
| Improve this Doc View Source

OnTreeEdge(TEdge, Boolean)

Called on each TreeEdge event.

Declaration
protected virtual void OnTreeEdge(TEdge edge, bool reversed)
Parameters
Type Name Description
TEdge edge

Concerned edge.
System.Boolean reversed

Indicates if the edge is reversed.
| Improve this Doc View Source

Relax(TEdge, TVertex, TVertex)

Runs the relaxation algorithm on the given edge.

Declaration
protected bool Relax(TEdge edge, TVertex source, TVertex target)
Parameters
Type Name Description
TEdge edge

Edge to relax.
TVertex source

Source vertex.
TVertex target

Target vertex.
Returns
Type Description
System.Boolean

True if relaxation decreased the target vertex distance, false otherwise.
| Improve this Doc View Source

SetVertexDistance(TVertex, Double)

Sets the distance associated to the given vertex.

Declaration
protected void SetVertexDistance(TVertex vertex, double distance)
Parameters
Type Name Description
TVertex vertex

The vertex to get the distance for.
System.Double distance

The distance.
| Improve this Doc View Source

TryGetDistance(TVertex, out Double)

Tries to get the distance associated to the given vertex.

Declaration
public bool TryGetDistance(TVertex vertex, out double distance)
Parameters
Type Name Description
TVertex vertex

The vertex.
System.Double distance

Associated distance.
Returns
Type Description
System.Boolean

True if the distance was found, false otherwise.
Exceptions
Type Condition
System.InvalidOperationException

Algorithm has not been run.

Events

| Improve this Doc View Source

TreeEdge

Fired when the distance label for the target vertex is decreased. The edge that participated in the last relaxation for vertex v is an edge in the shortest paths tree.

Declaration
public event UndirectedEdgeAction<TVertex, TEdge> TreeEdge
Event Type
Type Description
UndirectedEdgeAction<TVertex, TEdge>

Implements

Extension Methods