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 Details

    • 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