Class GraphConnectivityExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Connectivity queries: connected components (edge direction ignored), weak connectivity for directed graphs, and strongly connected components via an iterative Tarjan algorithm.

public static class GraphConnectivityExtensions

Inheritance

object

GraphConnectivityExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

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

Computes the biconnected components of an undirected graph: maximal edge sets in which any two edges lie on a common simple cycle. Every non-loop edge belongs to exactly one component; bridges form single-edge components, self-loops belong to none, and articulation points are exactly the vertices appearing in more than one component.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The undirected graph to partition.

Returns

IReadOnlyList<IReadOnlyList<TEdge>>

One edge list per biconnected component.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

graph is directed.

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

Computes the connected components of the graph, ignoring edge direction (for directed graphs this is weak connectivity).

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to partition.

Returns

IReadOnlyList<IReadOnlySet<TVertex>>

One vertex set per component.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Finds the articulation points (cut vertices) of an undirected graph: vertices whose removal increases the number of connected components.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The undirected graph to inspect.

Returns

IReadOnlySet<TVertex>

The articulation points.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

graph is directed.

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

Finds the bridges of an undirected graph: edges whose removal increases the number of connected components. A parallel edge pair is never a bridge; self-loops are ignored.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The undirected graph to inspect.

Returns

IReadOnlyList<TEdge>

The bridge edges.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

graph is directed.

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

Determines whether the graph is connected when edge direction is ignored. The empty graph is trivially connected.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to inspect.

Returns

bool

true if there is at most one component.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Computes the strongly connected components of a directed graph using Tarjan's algorithm (iterative, stack-safe on deep graphs). Components are emitted in reverse topological order of the condensation.

public static IReadOnlyList<IReadOnlySet<TVertex>> StronglyConnectedComponents<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to partition.

Returns

IReadOnlyList<IReadOnlySet<TVertex>>

One vertex set per strongly connected component.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Computes the 2-edge-connected components of an undirected graph: the connected components that remain after removing all bridges. Every vertex belongs to exactly one component; vertices attached only by bridges (or isolated) form singleton components.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The undirected graph to partition.

Returns

IReadOnlyList<IReadOnlySet<TVertex>>

One vertex set per 2-edge-connected component.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

ArgumentException

graph is directed.

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

Computes the weakly connected components of a directed graph: the connected components after forgetting edge direction.

public static IReadOnlyList<IReadOnlySet<TVertex>> WeaklyConnectedComponents<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to partition.

Returns

IReadOnlyList<IReadOnlySet<TVertex>>

One vertex set per component.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.