Package com.jgalgo.alg.connect

Interface KVertexConnectedComponentsAlgo

All Known Implementing Classes:

KVertexConnectedComponentsAlgoAbstract, KVertexConnectedComponentsWhiteMoody

public interface KVertexConnectedComponentsAlgo

Finds the k-vertex connected components of a graph.

Given a graph $G = (V, E)$ and an integer $k$, we say that $G$ is k-vertex connected if it has at least $k + 1$ vertices and remains connected after removing any $k - 1$ vertices. If $G$ is a clique of size $k + 1$, then $G$ is k-vertex connected. The k-vertex connected components of $G$ are the maximal k-vertex connected subgraphs of $G$. Note that for a general $k$, the k-vertex connected components of a graph are not disjoint, and their union is not necessarily the entire graph. For $k = 1$, the k-vertex connected components are the (strongly) connected components of $G$. For $k = 2$, the k-vertex connected components are the bi-connected components of $G$. Isolated vertices (with no edges) are considered to be 0-vertex connected components (also can be treated as a clique of size 1).

For k-edge connected components, see KEdgeConnectedComponentsAlgo.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

See Also:

• Wikipedia
• StronglyConnectedComponentsAlgo
• BiConnectedComponentsAlgo
• KEdgeConnectedComponentsAlgo

Method Summary

Modifier and Type	Method	Description
<V, E> List<Set<V>>	findKVertexConnectedComponents(Graph<V,E> g, int k)	Find all k-vertex connected components in a graph.
static KVertexConnectedComponentsAlgo	newInstance()	Create a new k-connected components algorithm object.

Method Details

findKVertexConnectedComponents

<V,
E> List<Set<V>> findKVertexConnectedComponents(Graph<V,E> g,
 int k)

Find all k-vertex connected components in a graph.

If g is an IntGraph, the returned list will be a list of IntSet.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

k - the k value, non negative

Returns:

a list of the k-connected components

Throws:

IllegalArgumentException - if k is negative

newInstance

static KVertexConnectedComponentsAlgo newInstance()

Create a new k-connected components algorithm object.

This is the recommended way to instantiate a new KVertexConnectedComponentsAlgo object. implementations.

Returns:

a default implementation of KVertexConnectedComponentsAlgo