Package com.jgalgo.alg.connect

Class KEdgeConnectedComponentsAlgoAbstract

java.lang.Object
com.jgalgo.alg.connect.KEdgeConnectedComponentsAlgoAbstract
All Implemented Interfaces:
KEdgeConnectedComponentsAlgo
Direct Known Subclasses:
KEdgeConnectedComponentsWang
public abstract class KEdgeConnectedComponentsAlgoAbstract extends Object implements KEdgeConnectedComponentsAlgo
Abstract class for k-edge connected components algorithms.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:
Barak Ugav

  • Constructor Details

    • KEdgeConnectedComponentsAlgoAbstract

      public KEdgeConnectedComponentsAlgoAbstract()
      Default constructor.

  • Method Details

    • computeKEdgeConnectedComponents

      public <V, E> VertexPartition<V,E> computeKEdgeConnectedComponents(Graph<V,E> g, int k)
      Description copied from interface: KEdgeConnectedComponentsAlgo
      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.

      Specified by:
      computeKEdgeConnectedComponents in interface KEdgeConnectedComponentsAlgo
      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