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 Detail

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