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:

  • 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