Module org.jgrapht.core
Package org.jgrapht.alg.connectivity

Class KConnectivityFlowAlgorithm<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    public class KConnectivityFlowAlgorithm<V,​E>
extends Object
    This class implements the computation, for a graph, of both edge connectivity and vertex connectivity . A graph with n vertices is k-edge connected when k is smaller than n and if the size of the smallest subset of edges which disconnects the graph is equal to k. It's the same definition for vertex connectivity, by replacing edges with vertices. This implementation uses a maximum flow algorithm and computes the number of different paths between two vertices with this algorithm. By default, this implementation uses the Edmonds-Karp max-flow algorithm. The algorithms implemented are based on this document . The worst-case complexity depends on the number of calls to this max-flow algorithm. All algorithms make O(n) calls to this flow algorithm. However, this number tries to be as low as possible. For further details on the exact number of calls, see the document on which this implementation is based. This algorithm works with both directed and undirected networks (Only SimpleGraph and SimpleDirectedGraph are tested). The algorithm doesn't have internal synchronization, thus any concurrent network modification has undefined behavior. The inspector methods work in a lazy fashion: no computations are performed unless immediately necessary. Computations are done once and results are cached within this class for future needs. Further improvements of flow-based algorithms can be found in this paper: D. W. Matula, “Determining edge connectivity in O(mn),” Proceedings of the 28th Symp. on Foundations of Computer Science, (1987), pp. 249‐251.
    Author:
    Azim Barhoumi, Paul Enjalbert

    • Constructor Detail

      • KConnectivityFlowAlgorithm

        public KConnectivityFlowAlgorithm​(Graph<V,​E> graph)
        Constructs a k-connectivity algorithm for the given graph. This
        Parameters:
        graph - the input graph

      • KConnectivityFlowAlgorithm

        public KConnectivityFlowAlgorithm​(Graph<V,​E> graph,
                                  Function<Graph<V,​E>,​MaximumFlowAlgorithm<V,​E>> edgeFlowAlgorithmSupplier,
                                  Function<Graph<Integer,​DefaultEdge>,​MaximumFlowAlgorithm<Integer,​DefaultEdge>> vertexFlowAlgorithmSupplier)
        Constructs a k-connectivity algorithm for the given graph. Use algorithms given by the suppliers for edge and vertex flow algorithm A supplier is a function which takes a graph and construct the algorithm which will be used
        Parameters:
        graph - the input graph
        edgeFlowAlgorithmSupplier - edge maximum flow algorithm supplier
        vertexFlowAlgorithmSupplier - vertex maximum flow algorithm supplier

    • Method Detail

      • getEdgeConnectivity

        public int getEdgeConnectivity()
        Computes the edge connectivity of the graph.
        Returns:
        the edge connectivity of the graph

      • getVertexConnectivity

        public int getVertexConnectivity()
        Computes the vertex connectivity of the graph.
        Returns:
        the vertex connectivity of the graph

      • isKEdgeConnected

        public boolean isKEdgeConnected​(int k)
        Return if the graph is k edge connected, use Compute Edge Connectivity Edge methods to have the result
        Parameters:
        k -
        Returns:
        if the the graph is k edge connect or not

      • isKVertexConnected

        public boolean isKVertexConnected​(int k)
        Return if the graph is k vertex connected, use Compute Edge Connectivity Edge methods to have the result
        Parameters:
        k -
        Returns:
        if the the graph is k vertex connect or not