Package com.jgalgo.alg.connect

Class MinimumEdgeCutAllStAbstract

java.lang.Object

com.jgalgo.alg.connect.MinimumEdgeCutAllStAbstract

All Implemented Interfaces:

MinimumEdgeCutAllSt

Direct Known Subclasses:

MinimumEdgeCutAllStPicardQueyranne

public abstract class MinimumEdgeCutAllStAbstract
extends Object
implements MinimumEdgeCutAllSt

Abstract class for computing all minimum edge cuts between two terminal nodes.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
MinimumEdgeCutAllStAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V, E> Iterator<VertexBiPartition<V,E>>	minimumCutsIter(Graph<V,E> g, WeightFunction<E> w, V source, V sink)	Iterate over all the minimum edge-cuts in a graph between two terminal vertices.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.jgalgo.alg.connect.MinimumEdgeCutAllSt

allMinimumCuts

Constructor Details

MinimumEdgeCutAllStAbstract

public MinimumEdgeCutAllStAbstract()

Default constructor.

Method Details

minimumCutsIter

public <V,
E> Iterator<VertexBiPartition<V,E>> minimumCutsIter(Graph<V,E> g,
 WeightFunction<E> w,
 V source,
 V sink)

Description copied from interface: MinimumEdgeCutAllSt

Iterate over all the minimum edge-cuts in a graph between two terminal vertices.

Given a graph \(G=(V,E)\), an edge-cut is a partition of \(V\) into twos sets \(C, \bar{C} = V \setminus C\). The return value of this function is an iterator over all the partitions to these two sets with minimum weight.

If g is an IntGraph, the returned iterator will iterate over IVertexBiPartition objects. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

Specified by:

minimumCutsIter in interface MinimumEdgeCutAllSt

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

source - the source vertex

sink - the sink vertex

Returns:

an iterator over all the minimum edge-cuts