Class GraphEulerianExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Eulerian trails: paths and circuits that use every edge exactly once. Existence follows the classic degree conditions (balanced in/out degrees for directed graphs; zero or two odd-degree vertices for undirected ones) plus a single edge-bearing component; construction is an iterative Hierholzer walk. Multigraphs are fully supported — parallel edges are tracked by instance, which is exactly the Königsberg setting.

public static class GraphEulerianExtensions

Inheritance

object

GraphEulerianExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

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

Finds an Eulerian circuit, or null when none exists.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to traverse.

Returns

IReadOnlyList<TEdge>

The circuit's edge sequence (empty for edgeless graphs), or null.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Finds an Eulerian path, or null when none exists.

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

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to traverse.

Returns

IReadOnlyList<TEdge>

The trail's edge sequence (empty for edgeless graphs), or null.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Determines whether the graph has an Eulerian circuit (a closed trail using every edge once). Edgeless graphs trivially do.

public static bool HasEulerianCircuit<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 an Eulerian circuit exists.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

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

Determines whether the graph has an Eulerian path (a trail using every edge once; circuits count). Edgeless graphs trivially do.

public static bool HasEulerianPath<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 an Eulerian path exists.

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.