Package com.jgalgo

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.

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
Path	computeMinimumMeanCycle(Graph g, WeightFunction w)	Compute the minimum mean cycle in a graph.
static MinimumMeanCycle.Builder	newBuilder()	Create a new minimum mean cycle algorithm builder.

Method Detail

computeMinimumMeanCycle

Path computeMinimumMeanCycle(Graph g,
                             WeightFunction w)

Compute the minimum mean cycle in a graph.

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

newBuilder

static MinimumMeanCycle.Builder newBuilder()

Create a new minimum mean cycle algorithm builder.

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

Returns:

a new builder that can build MinimumMeanCycle objects