Package com.jgalgo.alg.connect

Class MinimumVertexCutStAbstract

java.lang.Object

com.jgalgo.alg.connect.MinimumVertexCutStAbstract

All Implemented Interfaces:

MinimumVertexCutSt

Direct Known Subclasses:

MinimumVertexCutStEdgeCut

public abstract class MinimumVertexCutStAbstract
extends Object
implements MinimumVertexCutSt

Abstract class for computing the minimum vertex 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
MinimumVertexCutStAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> Set<V>	computeMinimumCut(Graph<V,E> g, WeightFunction<V> w, V source, V sink)	Compute the minimum vertex-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

MinimumVertexCutStAbstract

public MinimumVertexCutStAbstract()

Default constructor.

Method Detail

computeMinimumCut

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

Description copied from interface: MinimumVertexCutSt

Compute the minimum vertex-cut in a graph between two terminal vertices.

Given a graph \(G=(V,E)\), a vertex-cut is a set of vertices whose removal disconnect the source from the sink. Note that connectivity is with respect to direction from the source to the sink, and not the other way around. In undirected graphs the source and sink are interchangeable.

If the source and sink are the same vertex no vertex-cut exists and an exception will be thrown. If the source and sink and an edge exists between them, no vertex-cut exists and null will be returned.

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

Specified by:

computeMinimumCut in interface MinimumVertexCutSt

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - a vertex weight function

source - the source vertex

sink - the sink vertex

Returns:

a set of vertices that form the minimum vertex-cut, or null if an edge exists between the source and the sink and therefore no vertex-cut exists