Package com.jgalgo.alg.connect

Class MinimumVertexCutAllStAbstract

java.lang.Object

com.jgalgo.alg.connect.MinimumVertexCutAllStAbstract

All Implemented Interfaces:

MinimumVertexCutAllSt

Direct Known Subclasses:

MinimumVertexCutAllStEdgeCut

public abstract class MinimumVertexCutAllStAbstract
extends Object
implements MinimumVertexCutAllSt

Abstract class for computing all minimum vertex cuts 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
MinimumVertexCutAllStAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> Iterator<Set<V>>	minimumCutsIter(Graph<V,E> g, WeightFunction<V> w, V source, V sink)	Iterate over all the minimum vertex-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.MinimumVertexCutAllSt

allMinimumCuts

Constructor Detail

MinimumVertexCutAllStAbstract

public MinimumVertexCutAllStAbstract()

Default constructor.

Method Detail

minimumCutsIter

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

Description copied from interface: MinimumVertexCutAllSt

Iterate over all the minimum vertex-cuts 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, an iterator of IntSet objects will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

Specified by:

minimumCutsIter in interface MinimumVertexCutAllSt

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:

an iterator over the sets of vertices that form the minimum vertex-cuts, or null if an edge exists between the source and the sink and therefore no vertex-cut exists