Package com.jgalgo.alg

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 Detail

      • 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,
                                                        Object2BooleanMap<V> 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
        Returns:
        a new vertex bi-partition

      • 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