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 Summary

Modifier and Type	Method	Description
default Set<E>	crossEdges()	Get the edges that cross between the left and right blocks.
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.
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.
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.
boolean	isLeft(V vertex)	Check whether a vertex is contained in the left block (block 0).
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.
default boolean	isRight(V vertex)	Check whether a vertex is contained in the right block (block 1).
default Set<E>	leftEdges()	Get the edges that are contained in the left block.
default Set<V>	leftVertices()	Get the vertices in the 'left' block.
default int	numberOfBlocks()	Get the number of blocks in the partition.
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.
default Set<E>	rightEdges()	Get the edges that are contained in the right block.
default Set<V>	rightVertices()	Get the vertices in the 'right' block.
default int	vertexBlock(V vertex)	Get the block containing a vertex.

Methods inherited from interface com.jgalgo.alg.common.VertexPartition

blockEdges, blocksGraph, blocksGraph, blockSubGraph, blockSubGraph, blockVertices, crossEdges, graph

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,
                                                        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