Package com.jgalgo.alg.cycle

Interface MinimumMeanCycle

All Known Implementing Classes:
MinimumMeanCycleAbstract, MinimumMeanCycleDasdanGupta, MinimumMeanCycleHoward
public interface MinimumMeanCycle
Algorithm that find the cycle with the minimum mean weight.

Given a graph \(G\), a cycle in \(G\) is a sequence of edges that form a path, and its first edge source is also its last edge target. Given an edge weight function, we can define for each such cycle its mean weight, by summing its edges weights and dividing by its length (the number of edges in the cycle). Algorithms implementing this interface find the cycle with the minimum mean weight among all the cycles in the given graph.

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

Author:
Barak Ugav

  • Method Details

    • computeMinimumMeanCycle

      <V, E> Path<V,E> computeMinimumMeanCycle(Graph<V,E> g, WeightFunction<E> w)
      Compute the minimum mean cycle in a graph.

      If g is an IntGraph, a IPath object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      w - an edge weight function
      Returns:
      the cycle with the minimum mean weight in the graph, or null if no cycles were found

    • newInstance

      static MinimumMeanCycle newInstance()
      Create a new min mean cycle algorithm object.

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

      Returns:
      a default implementation of MinimumMeanCycle