Package com.jgalgo.alg.common

Interface VertexPartition<V,E>

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

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(Object).

Author:
Barak Ugav

  • Method Summary

    Modifier and Type
    Method
    Description
    Set<E>
    blockEdges(int block)
    Get all the edges that are contained in a block.
    default Graph<Integer,E>
    blocksGraph()
    Create a new graph representing the edges between the blocks.
    Graph<Integer,E>
    blocksGraph(boolean parallelEdges, boolean selfEdges)
    Create a new graph representing the edges between the blocks.
    default Graph<V,E>
    blockSubGraph(int block)
    Create a new graph that contains only the vertices and edges that are contained in a block.
    default Graph<V,E>
    blockSubGraph(int block, boolean copyVerticesWeights, boolean copyEdgesWeights)
    Create a new graph that contains only the vertices and edges that are contained in a block with option to copy weights.
    Set<V>
    blockVertices(int block)
    Get all the vertices that are part of a block.
    Set<E>
    crossEdges(int block1, int block2)
    Get all the edges that cross between two different blocks.
    static <V, E> VertexPartition<V,E>
    fromMap(Graph<V,E> g, Object2IntMap<V> map)
    Create a new vertex partition from a vertex-blockIndex map.
    static <V, E> VertexPartition<V,E>
    fromMapping(Graph<V,E> g, ToIntFunction<V> mapping)
    Create a new vertex partition from a vertex-blockIndex mapping function.
    Graph<V,E>
    graph()
    Get the graph that the partition is defined on.
    static <V, E> boolean
    isPartition(Graph<V,E> g, ToIntFunction<V> mapping)
    Check if a mapping is a valid partition of the vertices of a graph.
    int
    numberOfBlocks()
    Get the number of blocks in the partition.
    static <V, E> VertexPartition<V,E>
    partitionFromIndexPartition(Graph<V,E> g, IVertexPartition indexPartition)
    Create a vertex partition view from a vertex partition of the index graph of the given graph.
    int
    vertexBlock(V vertex)
    Get the block containing a vertex.

  • Method Details

    • numberOfBlocks

      int numberOfBlocks()
      Get the number of blocks in the partition.
      Returns:
      the number of blocks in the partition, non negative number

    • vertexBlock

      int vertexBlock(V 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)\)

    • blockVertices

      Set<V> blockVertices(int block)
      Get all the vertices that are part of a block.
      Parameters:
      block - index of a block
      Returns:
      the vertices that are part of the blocks
      Throws:
      IndexOutOfBoundsException - if block is not in range \([0, blocksNum)\)

    • blockEdges

      Set<E> blockEdges(int block)
      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.

      Parameters:
      block - index of a block
      Returns:
      the edges that are contained in the blocks
      Throws:
      IndexOutOfBoundsException - if block is not in range \([0, blocksNum)\)

    • crossEdges

      Set<E> crossEdges(int block1, int block2)
      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.

      Parameters:
      block1 - the first block
      block2 - the second block
      Returns:
      the set of edges that cross between the two blocks

    • graph

      Graph<V,E> graph()
      Get the graph that the partition is defined on.
      Returns:
      the graph that the partition is defined on

    • blockSubGraph

      default Graph<V,E> blockSubGraph(int block)
      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 blockSubGraph(int, boolean, boolean).

      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 Graph<V,E> blockSubGraph(int block, boolean copyVerticesWeights, boolean copyEdgesWeights)
      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.

      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 Graph<Integer,E> blocksGraph()
      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 blocksGraph(boolean, boolean).

      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

      Graph<Integer,E> blocksGraph(boolean parallelEdges, boolean selfEdges)
      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.

      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 <V, E> VertexPartition<V,E> fromMap(Graph<V,E> g, Object2IntMap<V> 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.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      map - a map from vertex to block index
      Returns:
      a new vertex partition

    • fromMapping

      static <V, E> VertexPartition<V,E> fromMapping(Graph<V,E> g, ToIntFunction<V> 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.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      mapping - a mapping function that maps from a vertex to block index
      Returns:
      a new vertex partition

    • partitionFromIndexPartition

      static <V, E> VertexPartition<V,E> partitionFromIndexPartition(Graph<V,E> g, IVertexPartition indexPartition)
      Create a vertex partition view from a vertex 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 partition of the index graph of the given graph
      Returns:
      a vertex partition view

    • isPartition

      static <V, E> boolean isPartition(Graph<V,E> g, ToIntFunction<V> 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.

      Type Parameters:
      V - the vertices type
      E - the edges type
      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