Package com.jgalgo.alg.cycle

Interface ChinesePostman

All Known Implementing Classes:

ChinesePostmanAbstract, ChinesePostmanImpl

public interface ChinesePostman

An algorithm for the chinese postman problem.

The chinese postman problem is to find a closed path that visits all edges in the graph at least once, with minimum weight sum with respect to a given edge weight function.

The problem can be solved in polynomial time.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

Method Summary

Modifier and Type	Method	Description
default <V,E> Path<V,E>	computeShortestEdgeVisitorCircle(Graph<V,E> g, WeightFunction<E> w)	Compute the shortest circuit that visits all edges in the graph at least once.
<V,E> Optional<Path<V,E>>	computeShortestEdgeVisitorCircleIfExist(Graph<V,E> g, WeightFunction<E> w)	Compute the shortest circuit that visits all edges in the graph at least once, if it exist.
static ChinesePostman	newInstance()	Create a new algorithm object for chinese postman problem.

Method Detail

computeShortestEdgeVisitorCircle

default <V,E> Path<V,E> computeShortestEdgeVisitorCircle(Graph<V,E> g,
                                                                     WeightFunction<E> w)

Compute the shortest circuit that visits all edges in the graph at least once.

If g is IntGraph, the returned object is IPath. If g is IntGraph, prefer to pass IWeightFunction for best performance.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

Returns:

a closed path that visits all edges in the graph, with minimum weight sum with respect to the given edge weight function

Throws:

IllegalArgumentException - if no solution exists, that is if the graph is not strongly connected

computeShortestEdgeVisitorCircleIfExist

<V,E> Optional<Path<V,E>> computeShortestEdgeVisitorCircleIfExist(Graph<V,E> g,
                                                                              WeightFunction<E> w)

Compute the shortest circuit that visits all edges in the graph at least once, if it exist.

If g is IntGraph, the returned object is an optional of IPath. If g is IntGraph, prefer to pass IWeightFunction for best performance.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

Returns:

an optional of closed path that visits all edges in the graph, with minimum weight sum with respect to the given edge weight function, or empty if no solution exists (the graph is not strongly connected)

newInstance

static ChinesePostman newInstance()

Create a new algorithm object for chinese postman problem.

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

Returns:

a default implementation of ChinesePostman