Package org.graph4j.connectivity

Class StoerWagnerMinimumCut1

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.connectivity.StoerWagnerMinimumCut1
public class StoerWagnerMinimumCut1 extends SimpleGraphAlgorithm
Provides a method to find the minimum weighted cut of an undirected graph using the Stoer-Wagner algorithm. An edge cut is a set of edges that, if removed, would disconnect the graph. This implementation uses a binary heap and has time complexity O(|V||E| log|E|). See: Stoer and Wagner minimum cut algorithm.
Author:
Cristian Frăsinaru

  • Constructor Details

    • StoerWagnerMinimumCut1

      public StoerWagnerMinimumCut1(Graph graph)
      Creates an algorithm for computing the minimum weighted cut. If the input graph has no weights on its edges, the algorithm will assume the default value of 1 for each edge.
      Parameters:
      graph - the input graph.

    • StoerWagnerMinimumCut1

      public StoerWagnerMinimumCut1(Graph graph, boolean ignoreWeights)
      Creates an algorithm for computing the minimum weighted/cardinality cut.
      Parameters:
      graph - the input graph.
      ignoreWeights - if true

  • Method Details

    • getMinimumCut

      public EdgeCut getMinimumCut()
      Returns the minimum cut.
      Returns:
      the minimum cut.
      Throws:
      IllegalArgumentException - if the graph contains edges with negative weights.

    • getMinimumCutWeight

      public double getMinimumCutWeight()
      Returns the weight of the minimum cut, that is the sum of the weights of the edges in the cut.
      Returns:
      the weight of the minimum cut.