Package com.jgalgo

Interface EulerianTourAlgo

public interface EulerianTourAlgo

Eulerian tour calculation algorithm.

An Eulerian tour is a tour that visits every edge exactly once (allowing for revisiting vertices). For a connected undirected graph, if all vertices have an even degree, an Eulerian cycle will be found. If exactly two vertices have an odd degree, called \(s,t\), an Eulerian tour that start at \(s\) and ends at \(t\) exists. For any other vertices degrees an Eulerian tour does not exists. For a strongly connected directed graph, the in-degree and out-degree of each vertex must be equal for an Eulerian cycle to exists. If exactly one vertex \(s\) has one more out-edge than in-edges, and one vertex \(t\) has one more in-edge than out-edges, an Eulerian tour that start at \(s\) and ends at \(t\) exists.

Author:

Barak Ugav

See Also:

Wikipedia, TSPMetricMSTAppx, TSPMetricMatchingAppx

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	EulerianTourAlgo.Builder	A builder for EulerianTourAlgo objects.

Method Summary

Modifier and Type	Method	Description
Path	computeEulerianTour(Graph g)	Compute an Eulerian tour in the graph that visit all edges exactly once.
static EulerianTourAlgo.Builder	newBuilder()	Create a new Eulerian tour algorithm builder.

Method Detail

computeEulerianTour

Path computeEulerianTour(Graph g)

Compute an Eulerian tour in the graph that visit all edges exactly once.

The graph is assumed to be (strongly) connected. Either a cycle or tour will be found, depending on the vertices degrees.

Parameters:

g - a graph

Returns:

an Eulerian tour that visit all edges of the graph exactly once

Throws:

IllegalArgumentException - if there is no Eulerian tour in the graph

newBuilder

static EulerianTourAlgo.Builder newBuilder()

Create a new Eulerian tour algorithm builder.

This is the recommended way to instantiate a new EulerianTourAlgo object.

Returns:

a new builder that can build EulerianTourAlgo objects