Package com.jgalgo

Interface Cut

  • public interface Cut
    A cut that partition the vertices of a graph into two sets.

    Given a graph \(G=(V,E)\), a cut is a partition of \(V\) into two sets \(C, \bar{C} = V \setminus C\). Given a weight function, the weight of a cut \((C,\bar{C})\) is the weight sum of all edges \((u,v)\) such that \(u\) is in \(C\) and \(v\) is in \(\bar{C}\). When we say 'the cut' we often mean the first set \(C\).

    Author:
    Barak Ugav
    See Also:
    MinimumCutST

    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      boolean containsVertex​(int vertex)
      Check whether a vertex is in the cut.
      it.unimi.dsi.fastutil.ints.IntCollection edges()
      Get the collection of all the edges that cross the cut.
      it.unimi.dsi.fastutil.ints.IntCollection vertices()
      Get the collection of all the vertices in the cut.
      double weight​(WeightFunction w)
      Get the weight of the cut with respect to the given weight function.

    • Method Detail

      • containsVertex

        boolean containsVertex​(int vertex)
        Check whether a vertex is in the cut.

        When we say 'the cut' we mean the first set \(C\) out of the cut partition into two sets \(C, \bar{C} = V \setminus C\).

        Parameters:
        vertex - a vertex identifier
        Returns:
        true if vertex is in the first set of the partition, \(C\)

      • vertices

        it.unimi.dsi.fastutil.ints.IntCollection vertices()
        Get the collection of all the vertices in the cut.

        When we say 'the cut' we mean the first set \(C\) out of the cut partition into two sets \(C, \bar{C} = V \setminus C\).

        Returns:
        a collection of all the vertices of the first set of the partition, \(C\)

      • edges

        it.unimi.dsi.fastutil.ints.IntCollection edges()
        Get the collection of all the edges that cross the cut.

        Given a cut \(C, \bar{C} = V \setminus C\), the edges that cross the cut are edges \((u,v)\) such that \(u\) is in \(C\) and \(v\) is in \(\bar{C}\).

        Returns:
        a collection of all the edges that cross the cut partition

      • weight

        double weight​(WeightFunction w)
        Get the weight of the cut with respect to the given weight function.

        Given a weight function, the weight of a cut \((C,\bar{C})\) is the weight sum of all edges \((u,v)\) such that \(u\) is in \(C\) and \(v\) is in \(\bar{C}\).

        Parameters:
        w - an edge weight function
        Returns:
        the sum of edge weights \((u,v)\) such that \(u\) is in \(C\) and \(v\) is in \(\bar{C}\)