Class EulerianTrailAlgorithm<TVertex, TEdge>

Algorithm that find Eulerian path in a graph.

Inheritance
System.Object
AlgorithmBase<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>
RootedAlgorithmBase<TVertex, IMutableVertexAndEdgeListGraph<TVertex, TEdge>>
EulerianTrailAlgorithm<TVertex, TEdge>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: QuikGraph.Algorithms
Assembly: QuikGraph.dll
Syntax
public sealed class EulerianTrailAlgorithm<TVertex, TEdge> : RootedAlgorithmBase<TVertex, IMutableVertexAndEdgeListGraph<TVertex, TEdge>>, IAlgorithm<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent, ITreeBuilderAlgorithm<TVertex, TEdge> where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex

Vertex type.
TEdge

Edge type.

Constructors

| Improve this Doc View Source

EulerianTrailAlgorithm(IAlgorithmComponent, IMutableVertexAndEdgeListGraph<TVertex, TEdge>)

Initializes a new instance of the EulerianTrailAlgorithm<TVertex, TEdge> class.

Declaration
public EulerianTrailAlgorithm(IAlgorithmComponent host, IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph)
Parameters
Type Name Description
IAlgorithmComponent host

Host to use if set, otherwise use this reference.
IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
| Improve this Doc View Source

EulerianTrailAlgorithm(IMutableVertexAndEdgeListGraph<TVertex, TEdge>)

Initializes a new instance of the EulerianTrailAlgorithm<TVertex, TEdge> class.

Declaration
public EulerianTrailAlgorithm(IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph)
Parameters
Type Name Description
IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.

Properties

| Improve this Doc View Source

Circuit

Circuit.

Declaration
public TEdge[] Circuit { get; }
Property Value
Type Description
TEdge[]

Methods

| Improve this Doc View Source

AddTemporaryEdges(EdgeFactory<TVertex, TEdge>)

Adds temporary edges to the graph to make all vertex even.

Declaration
public TEdge[] AddTemporaryEdges(EdgeFactory<TVertex, TEdge> edgeFactory)
Parameters
Type Name Description
EdgeFactory<TVertex, TEdge> edgeFactory

Edge factory method.
Returns
Type Description
TEdge[]

Temporary edges list.
Exceptions
Type Condition
System.ArgumentNullException

edgeFactory is null.
System.InvalidOperationException

Number of odd vertices is not even, failed to add temporary edge to VisitedGraph, or failed to compute eulerian trail.
| Improve this Doc View Source

ComputeEulerianPathCount(IVertexAndEdgeListGraph<TVertex, TEdge>)

Computes the number of Eulerian trails in the graph.

Declaration
public static int ComputeEulerianPathCount(IVertexAndEdgeListGraph<TVertex, TEdge> graph)
Parameters
Type Name Description
IVertexAndEdgeListGraph<TVertex, TEdge> graph

Graph to visit.
Returns
Type Description
System.Int32

Number of Eulerian trails.
Exceptions
Type Condition
System.ArgumentNullException

graph is null.
| Improve this Doc View Source

InternalCompute()

Algorithm compute step.

Declaration
protected override void InternalCompute()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IMutableVertexAndEdgeListGraph<TVertex, TEdge>>.InternalCompute()
| Improve this Doc View Source

RemoveTemporaryEdges()

Removes temporary edges.

Declaration
public void RemoveTemporaryEdges()
| Improve this Doc View Source

Trails()

Computes the set of Eulerian trails that traverse the edge set.

Declaration
public IEnumerable<ICollection<TEdge>> Trails()
Returns
Type Description
System.Collections.Generic.IEnumerable<System.Collections.Generic.ICollection<TEdge>>

Eulerian trail set.
Remarks

This method returns a set of disjoint Eulerian trails. This set of trails spans the entire set of edges.

| Improve this Doc View Source

Trails(TVertex)

Computes a set of Eulerian trails, starting at startingVertex that spans the entire graph.

Declaration
public IEnumerable<ICollection<TEdge>> Trails(TVertex startingVertex)
Parameters
Type Name Description
TVertex startingVertex

Starting vertex.
Returns
Type Description
System.Collections.Generic.IEnumerable<System.Collections.Generic.ICollection<TEdge>>

Eulerian trail set, all starting at startingVertex.
Remarks

This method computes a set of Eulerian trails starting at startingVertex that spans the entire graph. The algorithm outline is as follows:

The algorithms iterates through the Eulerian circuit of the augmented graph (the augmented graph is the graph with additional edges to make the number of odd vertices even).

If the current edge is not temporary, it is added to the current trail.

If the current edge is temporary, the current trail is finished and added to the trail collection. The shortest path between the start vertex startingVertex and the target vertex of the temporary edge is then used to start the new trail. This shortest path is computed using the BreadthFirstSearchAlgorithm<TVertex, TEdge>.

Exceptions
Type Condition
System.ArgumentNullException

startingVertex is null.
System.InvalidOperationException

Eulerian trail not computed yet.

Events

| Improve this Doc View Source

CircuitEdge

Fired when an edge is added to the circuit.

Declaration
public event EdgeAction<TVertex, TEdge> CircuitEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

TreeEdge

Fired when an edge is encountered.

Declaration
public event EdgeAction<TVertex, TEdge> TreeEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

VisitEdge

Fired when an edge is visited.

Declaration
public event EdgeAction<TVertex, TEdge> VisitEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>

Implements

Extension Methods