Package com.jgalgo.alg

Interface KEdgeConnectedComponentsAlgo

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. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

See Also:

Wikipedia, KVertexConnectedComponentsAlgo

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	KEdgeConnectedComponentsAlgo.Builder	A builder for KEdgeConnectedComponentsAlgo objects.

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.Builder	newBuilder()	Create a new k-edge connected components algorithm builder.
static KEdgeConnectedComponentsAlgo	newInstance()	Create a new k-edge connected components algorithm object.

Method Detail

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. The KEdgeConnectedComponentsAlgo.Builder might support different options to obtain different implementations.

Returns:

a default implementation of KEdgeConnectedComponentsAlgo

newBuilder

static KEdgeConnectedComponentsAlgo.Builder newBuilder()

Create a new k-edge connected components algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build KEdgeConnectedComponentsAlgo objects