Package com.jgalgo.alg

Interface MinimumMeanCycle

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. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	MinimumMeanCycle.Builder	A builder for MinimumMeanCycle objects.

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.Builder	newBuilder()	Create a new minimum mean cycle algorithm builder.
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. The MinimumMeanCycle.Builder might support different options to obtain different implementations.

Returns:

a default implementation of MinimumMeanCycle

newBuilder

static MinimumMeanCycle.Builder newBuilder()

Create a new minimum mean cycle algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build MinimumMeanCycle objects