Package com.jgalgo.alg.connect

Class MinimumEdgeCutStAbstract

java.lang.Object

com.jgalgo.alg.connect.MinimumEdgeCutStAbstract

All Implemented Interfaces:

MinimumEdgeCutSt

Direct Known Subclasses:

MaximumFlowAbstract

public abstract class MinimumEdgeCutStAbstract
extends Object
implements MinimumEdgeCutSt

Abstract class for computing the minimum edge cut between two vertices in a graph.

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
MinimumEdgeCutStAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> VertexBiPartition<V,E>	computeMinimumCut(Graph<V,E> g, WeightFunction<E> w, Collection<V> sources, Collection<V> sinks)	Compute the minimum edge-cut in a graph between two sets of vertices.
<V,E> VertexBiPartition<V,E>	computeMinimumCut(Graph<V,E> g, WeightFunction<E> w, V source, V sink)	Compute the minimum edge-cut in a graph between two terminal vertices.

Methods inherited from class java.lang.Object

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

Constructor Detail

MinimumEdgeCutStAbstract

public MinimumEdgeCutStAbstract()

Default constructor.

Method Detail

computeMinimumCut

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

Description copied from interface: MinimumEdgeCutSt

Compute the minimum edge-cut 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 a partition into these two sets.

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

Specified by:

computeMinimumCut in interface MinimumEdgeCutSt

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

source - a special vertex that will be in \(C\)

sink - a special vertex that will be in \(\bar{C}\)

Returns:

the cut that was computed

computeMinimumCut

public <V,E> VertexBiPartition<V,E> computeMinimumCut(Graph<V,E> g,
                                                                  WeightFunction<E> w,
                                                                  Collection<V> sources,
                                                                  Collection<V> sinks)

Description copied from interface: MinimumEdgeCutSt

Compute the minimum edge-cut in a graph between two sets of 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 a partition into these two sets.

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

Specified by:

computeMinimumCut in interface MinimumEdgeCutSt

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

sources - special vertices that will be in \(C\)

sinks - special vertices that will be in \(\bar{C}\)

Returns:

the minimum cut between the two sets