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 Summary

Modifier and Type	Method	Description
<V,E> Path<V,E>	computeMinimumMeanCycle(Graph<V,E> g, WeightFunction<E> w)	Compute the minimum mean cycle in a graph.
static MinimumMeanCycle	newInstance()	Create a new min mean cycle algorithm object.

Method Detail

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