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 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