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:

  • 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