Package com.jgalgo.alg.common

Interface VertexBiPartition<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Superinterfaces:
VertexPartition<V,E>
All Known Subinterfaces:
IVertexBiPartition
public interface VertexBiPartition<V,E> extends VertexPartition<V,E>
A partition of the vertices of a graph into two blocks.

This interface is a specific case of VertexPartition where the number of blocks is 2. It can be used to represent a cut, or a bipartite partition of a graph.

The two blocks (or sets) are called left and right. The left block is the block with index 0, and the right block is the block with index 1, and few methods with 'left/right' names are provided for convenience.

Author:
Barak Ugav

  • Method Details

    • numberOfBlocks

      default int numberOfBlocks()
      Description copied from interface: VertexPartition
      Get the number of blocks in the partition.
      Specified by:
      numberOfBlocks in interface VertexPartition<V,E>
      Returns:
      the number of blocks in the partition, non negative number

    • isLeft

      boolean isLeft(V vertex)
      Check whether a vertex is contained in the left block (block 0).
      Parameters:
      vertex - a vertex in the graph
      Returns:
      true if the vertex is contained in the left block, false otherwise

    • isRight

      default boolean isRight(V vertex)
      Check whether a vertex is contained in the right block (block 1).
      Parameters:
      vertex - a vertex in the graph
      Returns:
      true if the vertex is contained in the right block, false otherwise

    • vertexBlock

      default int vertexBlock(V vertex)
      Description copied from interface: VertexPartition
      Get the block containing a vertex.
      Specified by:
      vertexBlock in interface VertexPartition<V,E>
      Parameters:
      vertex - a vertex in the graph
      Returns:
      index of the block containing the vertex, in range \([0, blocksNum)\)

    • leftVertices

      default Set<V> leftVertices()
      Get the vertices in the 'left' block.

      The left block is the block with index 0.

      Returns:
      the vertices in the left block

    • rightVertices

      default Set<V> rightVertices()
      Get the vertices in the 'right' block.

      The right block is the block with index 1.

      Returns:
      the vertices in the right block

    • leftEdges

      default Set<E> leftEdges()
      Get the edges that are contained in the left block.

      The left block is the block with index 0, and edges contained in it are edges with both endpoints in the left block.

      Returns:
      the edges that are contained in the left block

    • rightEdges

      default Set<E> rightEdges()
      Get the edges that are contained in the right block.

      The right block is the block with index 1, and edges contained in it are edges with both endpoints in the right block.

      Returns:
      the edges that are contained in the right block

    • crossEdges

      default Set<E> crossEdges()
      Get the edges that cross between the left and right blocks.

      An edge \((u,v)\) is said to cross between two blocks \(b_1\) and \(b_2\) if \(u\) is contained in \(b_1\) and \(v\) is contained in \(b_2\). Note that if the graph is directed, the cross edges of \((b_1,b_2)\) are different that \((b_2,b_1)\), since the direction of the edge matters. In that case, the edges returned by this functions are edges sourced in the left block and targeted in the right block. To get the edges sourced in the right block and targeted in the left block, use crossEdges(1, 0).

      Returns:
      the edges that cross between the left and right blocks

    • fromMap

      static <V, E> VertexBiPartition<V,E> fromMap(Graph<V,E> g, Map<V,Boolean> map)
      Create a new vertex bi-partition from a vertex-side map.

      Note that this function does not validate the input. For that, see isPartition(Graph, Predicate).

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      map - a map from vertex to either true or false
      Returns:
      a new vertex bi-partition

    • fromMapping

      static <V, E> VertexBiPartition<V,E> fromMapping(Graph<V,E> g, Predicate<V> mapping)
      Create a new vertex bi-partition from a vertex-side mapping function.

      Note that this function does not validate the input. For that, see isPartition(Graph, Predicate).

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      mapping - a mapping function that maps from a vertex to either true or false, where true means the vertex is contained in the left block and false means the vertex is contained in the right block
      Returns:
      a new vertex bi-partition

    • fromWeights

      static <V, E> VertexBiPartition<V,E> fromWeights(Graph<V,E> g, WeightsBool<V> weights)
      Create a new vertex bi-partition from a vertex-side weights container.
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      weights - a weights container that maps from a vertex to either true or false, where true means the vertex is contained in the left block and false means the vertex is contained in the right block
      Returns:
      a new vertex bi-partition

    • partitionFromIndexPartition

      static <V, E> VertexBiPartition<V,E> partitionFromIndexPartition(Graph<V,E> g, IVertexBiPartition indexPartition)
      Create a vertex bi-partition view from a vertex bi-partition of the index graph of the given graph.
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph, must not be an index graph
      indexPartition - the bi-partition of the index graph of the given graph
      Returns:
      a vertex bi-partition view

    • isPartition

      static <V, E> boolean isPartition(Graph<V,E> g, Predicate<V> mapping)
      Check if a mapping is a valid bi-partition of the vertices of a graph.

      A valid vertex bi-partition is a mapping from each vertex to either true or false, in which there are not 'empty blocks', namely at least one vertex is mapped to true and another one is mapped to true.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      mapping - a mapping function that maps from a vertex to either true or false
      Returns:
      true if the mapping is a valid bi-partition of the vertices of the graph, false otherwise