Class GraphDagPathExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Shortest, longest, and critical paths on directed acyclic graphs: one topological pass with edge relaxation, so negative weights are fine (this is the fast answer when Dijkstra rejects them with NegativeWeightException). Cyclic input throws GraphCycleException.

public static class GraphDagPathExtensions

Inheritance

object

GraphDagPathExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

CriticalPath<TVertex, TWeight>(IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>)

Finds the critical path using the weights carried by the graph's WeightedEdge<TVertex, TWeight> edges.

public static ShortestPathResult<TVertex, TWeight> CriticalPath<TVertex, TWeight>(this IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>> graph) where TVertex : notnull where TWeight : INumber<TWeight>

Parameters

graph IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>

The directed acyclic graph to search.

Returns

ShortestPathResult<TVertex, TWeight>

The heaviest path, from its start vertex to its end vertex.

Type Parameters

TVertex

The vertex type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph has no vertices.

GraphCycleException

The graph contains a cycle.

CriticalPath<TVertex, TEdge, TWeight>(IDirectedGraph<TVertex, TEdge>, Func<TEdge, TWeight>)

Finds the critical path: the maximum-weight path anywhere in the directed acyclic graph (start and end are free). When every edge is negative the best path is a single vertex with distance zero.

public static ShortestPathResult<TVertex, TWeight> CriticalPath<TVertex, TEdge, TWeight>(this IDirectedGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed acyclic graph to search.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

ShortestPathResult<TVertex, TWeight>

The heaviest path, from its start vertex to its end vertex.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph has no vertices.

GraphCycleException

The graph contains a cycle.

DagLongestPathsFrom<TVertex, TWeight>(IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>, TVertex)

Computes longest paths from source using the weights carried by the graph's WeightedEdge<TVertex, TWeight> edges.

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

Parameters

graph IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>

The directed acyclic graph to search.

source TVertex

The start vertex.

Returns

SingleSourceShortestPaths<TVertex, TWeight>

A queryable single-source result carrying longest distances.

Type Parameters

TVertex

The vertex type.

TWeight

The numeric weight type.

Exceptions

ArgumentException

source is not in the graph.

GraphCycleException

The graph contains a cycle.

DagLongestPathsFrom<TVertex, TEdge, TWeight>(IDirectedGraph<TVertex, TEdge>, TVertex, Func<TEdge, TWeight>)

Computes longest paths from source to every reachable vertex of a directed acyclic graph, using weightSelector to read edge weights.

public static SingleSourceShortestPaths<TVertex, TWeight> DagLongestPathsFrom<TVertex, TEdge, TWeight>(this IDirectedGraph<TVertex, TEdge> graph, TVertex source, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed acyclic 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 carrying longest distances.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

ArgumentException

source is not in the graph.

GraphCycleException

The graph contains a cycle.

DagShortestPathsFrom<TVertex, TWeight>(IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>, TVertex)

Computes shortest paths from source using the weights carried by the graph's WeightedEdge<TVertex, TWeight> edges.

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

Parameters

graph IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>

The directed acyclic 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

ArgumentException

source is not in the graph.

GraphCycleException

The graph contains a cycle.

DagShortestPathsFrom<TVertex, TEdge, TWeight>(IDirectedGraph<TVertex, TEdge>, TVertex, Func<TEdge, TWeight>)

Computes shortest paths from source to every reachable vertex of a directed acyclic graph, using weightSelector to read edge weights. Negative weights are supported.

public static SingleSourceShortestPaths<TVertex, TWeight> DagShortestPathsFrom<TVertex, TEdge, TWeight>(this IDirectedGraph<TVertex, TEdge> graph, TVertex source, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed acyclic 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

ArgumentException

source is not in the graph.

GraphCycleException

The graph contains a cycle.