Class GraphDistanceExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Distance metrics: eccentricity, diameter, radius, center, periphery, and average path length, computed from Dijkstra single-source runs. The graph must be connected (strongly connected when directed) — infinite distances are rejected up front instead of being encoded as sentinel values. Weighted overloads take a selector; the default counts hops.

public static class GraphDistanceExtensions

Inheritance

object

GraphDistanceExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

AveragePathLength<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets the mean hop count over all ordered vertex pairs.

public static double AveragePathLength<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

Returns

double

The average path length in hops.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

AveragePathLength<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Gets the mean hop count with the per-source sweeps running in parallel.

public static double AveragePathLength<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

double

The average path length in hops.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

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

Gets the mean shortest-path distance over all ordered vertex pairs. A single-vertex graph has no pairs and yields zero.

public static double AveragePathLength<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

double

The average path length.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

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

Gets the mean shortest-path distance, observing cancellationToken between vertices.

public static double AveragePathLength<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

double

The average path length.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token was cancelled.

AveragePathLength<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, ParallelOptions)

Gets the mean shortest-path distance with the per-source sweeps running in parallel. Per-source subtotals are combined in vertex order, so the result can differ from the sequential one by floating-point rounding only.

public static double AveragePathLength<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; must be safe to call concurrently.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

double

The average path length.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

Center<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets the hop-count center.

public static IReadOnlySet<TVertex> Center<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

Returns

IReadOnlySet<TVertex>

The central vertices.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Center<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Gets the hop-count center with the per-vertex sweeps running in parallel.

public static IReadOnlySet<TVertex> Center<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlySet<TVertex>

The central vertices.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

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

Gets the center: the vertices whose eccentricity equals the radius.

public static IReadOnlySet<TVertex> Center<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

IReadOnlySet<TVertex>

The central vertices.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Center<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, ParallelOptions)

Gets the center with the per-vertex sweeps running in parallel.

public static IReadOnlySet<TVertex> Center<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; must be safe to call concurrently.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlySet<TVertex>

The central vertices, identical to the sequential result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

Diameter<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets the hop-count diameter.

public static int Diameter<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

Returns

int

The diameter in hops.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Diameter<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Gets the hop-count diameter with the per-vertex sweeps running in parallel.

public static int Diameter<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

int

The diameter in hops.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

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

Gets the greatest eccentricity: the longest shortest path in the graph.

public static TWeight Diameter<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

TWeight

The diameter.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

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

Gets the diameter, observing cancellationToken between vertices.

public static TWeight Diameter<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

TWeight

The diameter.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token was cancelled.

Diameter<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, ParallelOptions)

Gets the diameter with the per-vertex sweeps running in parallel.

public static TWeight Diameter<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; must be safe to call concurrently.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

TWeight

The diameter, identical to the sequential result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

Eccentricity<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, TVertex)

Gets the hop-count eccentricity of vertex.

public static int Eccentricity<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex vertex) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

vertex TVertex

The vertex whose eccentricity to compute.

Returns

int

The eccentricity in hops.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

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

Gets the greatest shortest-path distance from vertex to any other vertex.

public static TWeight Eccentricity<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, TVertex vertex, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

vertex TVertex

The vertex whose eccentricity to compute.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

TWeight

The eccentricity.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Periphery<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets the hop-count periphery.

public static IReadOnlySet<TVertex> Periphery<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

Returns

IReadOnlySet<TVertex>

The peripheral vertices.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Periphery<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Gets the hop-count periphery with the per-vertex sweeps running in parallel.

public static IReadOnlySet<TVertex> Periphery<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlySet<TVertex>

The peripheral vertices.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

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

Gets the periphery: the vertices whose eccentricity equals the diameter.

public static IReadOnlySet<TVertex> Periphery<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

IReadOnlySet<TVertex>

The peripheral vertices.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Periphery<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, ParallelOptions)

Gets the periphery with the per-vertex sweeps running in parallel.

public static IReadOnlySet<TVertex> Periphery<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; must be safe to call concurrently.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

IReadOnlySet<TVertex>

The peripheral vertices, identical to the sequential result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

Radius<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Gets the hop-count radius.

public static int Radius<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

Returns

int

The radius in hops.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Radius<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Gets the hop-count radius with the per-vertex sweeps running in parallel.

public static int Radius<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

int

The radius in hops.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.

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

Gets the smallest eccentricity.

public static TWeight Radius<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Returns

TWeight

The radius.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

Radius<TVertex, TEdge, TWeight>(IReadOnlyGraph<TVertex, TEdge>, Func<TEdge, TWeight>, ParallelOptions)

Gets the radius with the per-vertex sweeps running in parallel.

public static TWeight Radius<TVertex, TEdge, TWeight>(this IReadOnlyGraph<TVertex, TEdge> graph, Func<TEdge, TWeight> weightSelector, ParallelOptions parallelOptions) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The connected graph to measure; only read, never mutated.

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight; must be safe to call concurrently.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

TWeight

The radius, identical to the sequential result.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Exceptions

InvalidOperationException

The graph is empty or not (strongly) connected.

OperationCanceledException

The token inside the options was cancelled.