Package com.jgalgo.alg

Interface ChinesePostman

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
<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.
static ChinesePostman	newInstance()	Create a new algorithm object for chinese postman problem.

Method Detail

computeShortestEdgeVisitorCircle

<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

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