Class GraphCondensationExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Condensation: collapse each strongly connected component to a single vertex, producing a DAG on which DAG-only tools (topological sort, transitive reduction) become applicable to any directed graph.

public static class GraphCondensationExtensions

Inheritance

object

GraphCondensationExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

Condense<TVertex, TEdge>(IDirectedGraph<TVertex, TEdge>)

Builds the condensation of the graph.

public static CondensationResult<TVertex> Condense<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to condense.

Returns

CondensationResult<TVertex>

The condensation DAG plus component lookups. Inter-component edges dedupe; intra-component edges (including self-loops) disappear.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Condense<TVertex, TEdge>(IDirectedGraph<TVertex, TEdge>, CancellationToken)

Builds the condensation, observing cancellationToken between phases.

public static CondensationResult<TVertex> Condense<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to condense.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

CondensationResult<TVertex>

The condensation DAG plus component lookups.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

OperationCanceledException

The token was cancelled.