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

Class KConnectivityFlowAlgorithm<V,E>

java.lang.Object
org.jgrapht.alg.connectivity.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 Details

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

    • 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
      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
      Parameters:
      k -
      Returns:
      if the the graph is k vertex connect or not