Package com.jgalgo.alg.connect

Class MinimumVertexCutAllStEdgeCut

java.lang.Object

com.jgalgo.alg.connect.MinimumVertexCutAllStAbstract

com.jgalgo.alg.connect.MinimumVertexCutAllStEdgeCut

All Implemented Interfaces:

MinimumVertexCutAllSt

public class MinimumVertexCutAllStEdgeCut
extends MinimumVertexCutAllStAbstract

All Minimum Vertex-Cuts algorithm with terminal vertices (source-sink, S-T) using All Minimum Edge-Cuts algorithm.

An auxiliary graph is constructed from the original graph $G=(V,E)$ by replacing each vertex $v$ with two vertices $v_0$ and $v_1$ connected with an edge $(v_0,v_1)$, and each edge $e=(u,v)$ with an edge with either one or two edges. If the original graph is directed, then the edge $(u,v)$ is replaced with the edge $(u_1,v_0)$. If the original graph is undirected, then the edge $(u,v)$ is replaced with the edges $(u_1,v_0)$ and $(v_1,u_0)$. The edges connecting the vertices $v_0$ and $v_1$ are weighted with the weight of the vertex $v$ in the original graph. The edges connecting the vertices $u_1$ and $v_0$ are weighted with a large enough weight such that the minimum edge-cut in the auxiliary graph will not contain any of these edges. The minimum edge-cuts in the auxiliary graph is computed using the MinimumEdgeCutAllSt algorithm. The minimum vertex-cuts in the original graph is the set of vertices corresponding to the edges in the minimum edge-cuts in the auxiliary graph.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
MinimumVertexCutAllStEdgeCut()	Create a new instance of the algorithm.

Method Summary

Methods inherited from class com.jgalgo.alg.connect.MinimumVertexCutAllStAbstract

minimumCutsIter

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

MinimumVertexCutAllStEdgeCut

public MinimumVertexCutAllStEdgeCut()

Create a new instance of the algorithm.

Please prefer using MinimumVertexCutAllSt.newInstance() to get a default implementation for the MinimumVertexCutAllSt interface.