Package com.jgalgo.alg.connect

Interface KEdgeConnectedComponentsAlgo

All Known Implementing Classes:

KEdgeConnectedComponentsAlgoAbstract, KEdgeConnectedComponentsWang

public interface KEdgeConnectedComponentsAlgo

An algorithm that compute the k-edge connected components of a graph.

Given a graph $G = (V, E)$ and an integer $k$, a k-edge connected component is a maximal subgraph $G' = (V', E')$ of $G$ such that for every pair of vertices $u, v \in V'$ there are at least $k$ edge-disjoint paths between $u$ and $v$ in $G'$. In other words, a k-edge connected component is a subgraph of $G$ in which every pair of vertices remains connected even if we allow to remove $k-1$ edges from the graph. For $k=1$ the problem is identical to finding the strongly connected components of the graph. Note that the k-edge disjoint paths may share vertices.

To compute the edge connectivity between two specific edges, use MinimumEdgeCutSt, as the minimum cardinality edge-cut of a graph is equal to its edge connectivity. To compute the edge connectivity of a graph, use MinimumEdgeCutGlobal, as the minimum global cardinality edge-cut of a graph is equal to its edge connectivity.

For k-vertex connected components, see KVertexConnectedComponentsAlgo.

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

Author:

Barak Ugav

See Also:

• Wikipedia
• KVertexConnectedComponentsAlgo

Method Summary

Modifier and Type	Method	Description
<V, E> VertexPartition<V,E>	computeKEdgeConnectedComponents(Graph<V,E> g, int k)	Compute the k-edge connected components of a graph.
static KEdgeConnectedComponentsAlgo	newInstance()	Create a new k-edge connected components algorithm object.

Method Details

computeKEdgeConnectedComponents

<V,
E> VertexPartition<V,E> computeKEdgeConnectedComponents(Graph<V,E> g,
 int k)

Compute the k-edge connected components of a graph.

The algorithm will return a VertexPartition object that represents the k-edge connected components of the graph. The partition will contain exactly one block for each k-edge connected component. The vertices of each block are the vertices of the component.

If g is an IntGraph, a IVertexPartition object will be returned.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

k - the $k$ parameter, which define the number of edges that must be removed to disconnect each returned connected component

Returns:

a VertexPartition object that represents the k-edge connected components of the graph

newInstance

static KEdgeConnectedComponentsAlgo newInstance()

Create a new k-edge connected components algorithm object.

This is the recommended way to instantiate a new KEdgeConnectedComponentsAlgo object.

Returns:

a default implementation of KEdgeConnectedComponentsAlgo