Package com.jgalgo.alg.common

Interface IVertexPartition

All Superinterfaces:
VertexPartition<Integer,Integer>
All Known Subinterfaces:
IVertexBiPartition
public interface IVertexPartition extends VertexPartition<Integer,Integer>
A partition of the vertices of an int graph.

This interface is a specification of VertexPartition for IntGraph.

A partition of a set is a division of the set into a number of disjoint subsets, such that their union is the original set. The sets may also be called 'components' or 'blocks'. We use the term 'block' instead of 'set' to avoid confusion with the get/set convention.

The partition represent a mapping from the vertices of a graph to \(B\) blocks, each block is assigned a number in range \([0,B)\). To check to which block a vertex is assigned use vertexBlock(int).

Author:
Barak Ugav

  • Method Details

    • vertexBlock

      int vertexBlock(int vertex)
      Get the block containing a vertex.
      Parameters:
      vertex - a vertex in the graph
      Returns:
      index of the block containing the vertex, in range \([0, blocksNum)\)

    • vertexBlock

      @Deprecated default int vertexBlock(Integer vertex)
      Deprecated.
      Please use vertexBlock(int) instead to avoid un/boxing.
      Get the block containing a vertex.
      Specified by:
      vertexBlock in interface VertexPartition<Integer,Integer>
      Parameters:
      vertex - a vertex in the graph
      Returns:
      index of the block containing the vertex, in range \([0, blocksNum)\)

    • blockVertices

      IntSet blockVertices(int block)
      Description copied from interface: VertexPartition
      Get all the vertices that are part of a block.
      Specified by:
      blockVertices in interface VertexPartition<Integer,Integer>
      Parameters:
      block - index of a block
      Returns:
      the vertices that are part of the blocks

    • blockEdges

      IntSet blockEdges(int block)
      Description copied from interface: VertexPartition
      Get all the edges that are contained in a block.

      An edge \((u,v)\) is contained in a block if both \(u\) and \(v\) are contained in the block.

      Specified by:
      blockEdges in interface VertexPartition<Integer,Integer>
      Parameters:
      block - index of a block
      Returns:
      the edges that are contained in the blocks

    • crossEdges

      IntSet crossEdges(int block1, int block2)
      Description copied from interface: VertexPartition
      Get all the edges that cross between two different 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.

      Specified by:
      crossEdges in interface VertexPartition<Integer,Integer>
      Parameters:
      block1 - the first block
      block2 - the second block
      Returns:
      the set of edges that cross between the two blocks

    • graph

      IntGraph graph()
      Description copied from interface: VertexPartition
      Get the graph that the partition is defined on.
      Specified by:
      graph in interface VertexPartition<Integer,Integer>
      Returns:
      the graph that the partition is defined on

    • blockSubGraph

      default IntGraph blockSubGraph(int block)
      Description copied from interface: VertexPartition
      Create a new graph that contains only the vertices and edges that are contained in a block.

      The returned graph is an induced subgraph of the original graph, namely it contains only the vertices of the block and edges between them.

      The vertex and edge weights are not copied to the new sub graph. For more coping options see VertexPartition.blockSubGraph(int, boolean, boolean).

      Specified by:
      blockSubGraph in interface VertexPartition<Integer,Integer>
      Parameters:
      block - index of a block
      Returns:
      a new graph that contains only the vertices and edges that are contained in the block

    • blockSubGraph

      default IntGraph blockSubGraph(int block, boolean copyVerticesWeights, boolean copyEdgesWeights)
      Description copied from interface: VertexPartition
      Create a new graph that contains only the vertices and edges that are contained in a block with option to copy weights.

      The returned graph is an induced subgraph of the original graph, namely it contains only the vertices of the block and edges between them.

      Specified by:
      blockSubGraph in interface VertexPartition<Integer,Integer>
      Parameters:
      block - index of a block
      copyVerticesWeights - if true the vertices weights are copied to the new graph
      copyEdgesWeights - if true the edges weights are copied to the new graph
      Returns:
      a new graph that contains only the vertices and edges that are contained in the block

    • blocksGraph

      default IntGraph blocksGraph()
      Description copied from interface: VertexPartition
      Create a new graph representing the edges between the blocks.

      Each vertex in the new graph represents a block, and there is an edge between two blocks if there is an edge between two original vertices, each in a different block. The vertices of the new graphs will be numbered from \(0\) to \(B-1\), where \(B\) is the number of blocks in the partition. The edges of the new graph will have the identifiers of the original edges.

      If there are multiple edges between two blocks, multiple parallel edges will be created in the new graph. Original edges between vertices in the same block will be ignored, instead of copied as self edges in the new graph. For more options regarding self and parallel edges see VertexPartition.blocksGraph(boolean, boolean).

      Specified by:
      blocksGraph in interface VertexPartition<Integer,Integer>
      Returns:
      a new graph where each vertex is a block, and there is an edge between two blocks if there is an edge between two original vertices, each in a different block

    • blocksGraph

      IntGraph blocksGraph(boolean parallelEdges, boolean selfEdges)
      Description copied from interface: VertexPartition
      Create a new graph representing the edges between the blocks.

      Each vertex in the new graph represents a block, and there is an edge between two blocks if there is an edge between two original vertices, each in a different block. The vertices of the new graphs will be numbered from \(0\) to \(B-1\), where \(B\) is the number of blocks in the partition. The edges of the new graph will have the identifiers of the original edges.

      Specified by:
      blocksGraph in interface VertexPartition<Integer,Integer>
      Parameters:
      parallelEdges - if true multiple parallel edges will be created between two blocks if there are multiple edges between them, if false only a single edge will be created, with identifier of one arbitrary original edge between the blocks. This is also relevant for self edges, if selfEdges is true.
      selfEdges - if true for each original edge between two vertices in the same block, a self edge will be created in the new graph, if false such edges will be ignored
      Returns:
      a new graph where each vertex is a block, and there is an edge between two blocks if there is an edge between two original vertices, each in a different block

    • fromMap

      static IVertexPartition fromMap(IntGraph g, Int2IntMap map)
      Create a new vertex partition from a vertex-blockIndex map.

      Note that this function does not validate the input, namely it does not check that the block numbers are all the range [0, maxBlockIndex], and that there are no 'empty' blocks.

      Parameters:
      g - the graph
      map - a map from vertex to block index
      Returns:
      a new vertex partition

    • fromMapping

      static IVertexPartition fromMapping(IntGraph g, IntUnaryOperator mapping)
      Create a new vertex partition from a vertex-blockIndex mapping function.

      Note that this function does not validate the input, namely it does not check that the block numbers are all the range [0, maxBlockIndex], and that there are no 'empty' blocks.

      Parameters:
      g - the graph
      mapping - a mapping function that maps from a vertex to block index
      Returns:
      a new vertex partition

    • fromArray

      static IVertexPartition fromArray(IndexGraph g, int[] vertexToBlock, int blocksNum)
      Create a new vertex partition from an array of vertex-blockIndex mapping.

      This function accept index graphs only, as the mapping is done by the index of the vertices.

      Note that this function does not validate the input, namely it does not check that the block numbers are all the range [0, maxBlockIndex], and that there are no 'empty' blocks.

      Parameters:
      g - the graph
      vertexToBlock - an array of size \(n\) where \(n\) is the number of vertices in the graph, in which each element is the block index of the corresponding vertex. The array is not copied, and it is assumed that the caller of this function will not modify the array after calling this function
      blocksNum - the number of blocks
      Returns:
      a new vertex partition

    • isPartition

      static boolean isPartition(IntGraph g, IntUnaryOperator mapping)
      Check if a mapping is a valid partition of the vertices of a graph.

      A valid vertex partition is a mapping from each vertex to an integer number in range [0, numberOfBlocks), in which there are not 'empty blocks', namely at least one vertex is mapped to each block.

      Parameters:
      g - the graph
      mapping - a mapping function that maps from a vertex to block index
      Returns:
      true if the mapping is a valid partition of the vertices of the graph, false otherwise