Class GraphStructureExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Structural queries: density, degree sequence, bipartiteness, and transpose.

public static class GraphStructureExtensions

Inheritance

object

GraphStructureExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

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

Gets the graph's degree sequence in descending order.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

Returns

IReadOnlyList<int>

Every vertex's degree, largest first.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Computes the graph's density: the ratio of existing edges to the maximum possible between distinct vertices (E / V(V-1) directed, 2E / V(V-1) undirected). Graphs with fewer than two vertices have density 0; self-loops and parallel edges can push it above 1.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to measure.

Returns

double

The density.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Finds a bipartition of the graph (edge direction ignored): two vertex sets such that every edge crosses between them.

public static (IReadOnlySet<TVertex> Left, IReadOnlySet<TVertex> Right)? FindBipartition<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to partition.

Returns

(IReadOnlySet<TVertex> Left, IReadOnlySet<TVertex> Right)?

The two sets, or null when the graph is not bipartite.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Determines whether the graph is bipartite (edge direction ignored).

public static bool IsBipartite<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 the vertices admit a proper 2-coloring.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TransitiveClosure<TVertex>(IDirectedGraph<TVertex, Edge<TVertex>>)

Builds the transitive closure of a directed graph with Edge<TVertex> edges.

public static IDirectedGraph<TVertex, Edge<TVertex>> TransitiveClosure<TVertex>(this IDirectedGraph<TVertex, Edge<TVertex>> graph) where TVertex : notnull

Parameters

graph IDirectedGraph<TVertex, Edge<TVertex>>

The directed graph to close.

Returns

IDirectedGraph<TVertex, Edge<TVertex>>

A new directed graph containing the closure.

Type Parameters

TVertex

The vertex type.

TransitiveClosure<TVertex, TEdge>(IDirectedGraph<TVertex, TEdge>, Func<TVertex, TVertex, TEdge>)

Builds the transitive closure of a directed graph: an edge u → v for every non-empty path u → ... → v in the original (so vertices on cycles gain self-loops). Vertices are preserved.

public static IDirectedGraph<TVertex, TEdge> TransitiveClosure<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph, Func<TVertex, TVertex, TEdge> edgeFactory) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to close.

edgeFactory Func<TVertex, TVertex, TEdge>

Builds the closure edge for a (source, target) pair.

Returns

IDirectedGraph<TVertex, TEdge>

A new directed graph containing the closure.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TransitiveClosure<TVertex, TEdge>(IDirectedGraph<TVertex, TEdge>, Func<TVertex, TVertex, TEdge>, CancellationToken)

Builds the transitive closure, observing cancellationToken between source vertices.

public static IDirectedGraph<TVertex, TEdge> TransitiveClosure<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph, Func<TVertex, TVertex, TEdge> edgeFactory, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to close.

edgeFactory Func<TVertex, TVertex, TEdge>

Builds the closure edge for a (source, target) pair.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

IDirectedGraph<TVertex, TEdge>

A new directed graph containing the closure.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

OperationCanceledException

The token was cancelled.

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

Builds the transitive reduction of a directed acyclic graph: the unique minimal edge set with the same reachability. An edge u → v is dropped when v is also reachable through another successor of u. Parallel edges collapse to one; vertices are preserved.

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

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed acyclic graph to reduce.

Returns

IDirectedGraph<TVertex, TEdge>

A new directed graph containing the reduction.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

GraphCycleException

The graph contains a cycle; general graphs have no unique reduction.

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

Builds the transitive reduction of a DAG, observing cancellationToken between vertices.

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

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed acyclic graph to reduce.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

IDirectedGraph<TVertex, TEdge>

A new directed graph containing the reduction.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

Exceptions

GraphCycleException

The graph contains a cycle.

OperationCanceledException

The token was cancelled.

Transpose<TVertex>(IDirectedGraph<TVertex, Edge<TVertex>>)

Builds the transpose of a directed graph with Edge<TVertex> edges.

public static IDirectedGraph<TVertex, Edge<TVertex>> Transpose<TVertex>(this IDirectedGraph<TVertex, Edge<TVertex>> graph) where TVertex : notnull

Parameters

graph IDirectedGraph<TVertex, Edge<TVertex>>

The directed graph to transpose.

Returns

IDirectedGraph<TVertex, Edge<TVertex>>

A new directed graph with all edges reversed.

Type Parameters

TVertex

The vertex type.

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

Builds the transpose of a directed graph with WeightedEdge<TVertex, TWeight> edges, keeping weights.

public static IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>> Transpose<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 graph to transpose.

Returns

IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>

A new directed graph with all edges reversed.

Type Parameters

TVertex

The vertex type.

TWeight

The numeric weight type.

Transpose<TVertex, TEdge>(IDirectedGraph<TVertex, TEdge>, Func<TEdge, TEdge>)

Builds the transpose of a directed graph: same vertices, every edge reversed via reverseEdge. The result preserves the source's parallel-edge policy.

public static IDirectedGraph<TVertex, TEdge> Transpose<TVertex, TEdge>(this IDirectedGraph<TVertex, TEdge> graph, Func<TEdge, TEdge> reverseEdge) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed graph to transpose.

reverseEdge Func<TEdge, TEdge>

Builds the reversed counterpart of an edge.

Returns

IDirectedGraph<TVertex, TEdge>

A new directed graph with all edges reversed.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.