Package org.graph4j.connectivity

Class VertexConnectivityAlgorithm

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.connectivity.VertexConnectivityAlgorithm
public class VertexConnectivityAlgorithm extends GraphAlgorithm
Determines a maximum size set of vertex disjoint paths between two vertices, a minimum size set of vertices whose removal disconnects two vertices, the vertex connectivity number.
Author:
Cristian Frăsinaru

  • Field Summary

    Fields inherited from class org.graph4j.GraphAlgorithm

    directed, graph

  • Constructor Summary

    Constructors
    Constructor
    Description
    VertexConnectivityAlgorithm(Graph graph)
    Creates an algorithm for determining the vertex connectivity of a graph.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    countMaximumDisjointPaths(int source)
    For each target vertex, different from the source, determines the maximum size of a set of vertex disjoint paths between the source and target, without creating the paths - among these, it is returned the smallest value.
    int
    countMaximumDisjointPaths(int source, int target)
    Determines the maximum size of a set of vertex disjoint paths between the source and the target, without creating the paths.
    int
    getConnectivityNumber()
    Computes the vertex connectivity number, that is the minimum size of a set of vertices whose removal disconnects the graph.
    List<Path>
    getMaximumDisjointPaths(int source, int target)
    Computes a maximum size set of vertex disjoint paths between the source and the target.
    VertexSet
    getMinimumCut()
    Computes a minimum vertex cut, that is a set of vertices of minimum size whose removal disconnects the graph.
    VertexSet
    getMinimumCut(int source)
    For each target vertex, different from the source, determines the vertex set of minimum size whose removal disconnects source and target - among these, we return the cutset with minimum size.
    VertexSet
    getMinimumCut(int source, int target)
    Computes the set of vertices of minimum size whose removal disconnects the source and the target.

    Methods inherited from class org.graph4j.GraphAlgorithm

    getGraph

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • VertexConnectivityAlgorithm

      public VertexConnectivityAlgorithm(Graph graph)
      Creates an algorithm for determining the vertex connectivity of a graph.
      Parameters:
      graph - the input graph.

  • Method Details

    • countMaximumDisjointPaths

      public int countMaximumDisjointPaths(int source, int target)
      Determines the maximum size of a set of vertex disjoint paths between the source and the target, without creating the paths. The source and the target must not form an edge. The number is computed by solving the corresponding maximum flow problem.
      Parameters:
      source - the source vertex number.
      target - the target vertex number.
      Returns:
      the maximum size of a set of vertex disjoint paths between the source and the target.

    • countMaximumDisjointPaths

      public int countMaximumDisjointPaths(int source)
      For each target vertex, different from the source, determines the maximum size of a set of vertex disjoint paths between the source and target, without creating the paths - among these, it is returned the smallest value. The number is computed by solving the corresponding maximum flow problems.
      Parameters:
      source - the source vertex number.
      Returns:
      the maximum size of a set of vertex disjoint paths between the source and some other vertex of the graph.

    • getMaximumDisjointPaths

      public List<Path> getMaximumDisjointPaths(int source, int target)
      Computes a maximum size set of vertex disjoint paths between the source and the target. The source and the target must not form an edge.
      Parameters:
      source - the source vertex number.
      target - the target vertex number.
      Returns:
      a maximum size set of vertex disjoint paths between the source and the target.

    • getMinimumCut

      public VertexSet getMinimumCut(int source, int target)
      Computes the set of vertices of minimum size whose removal disconnects the source and the target. The source and the target must not form an edge. The cutset is created by solving the corresponding maximum flow problem.
      Parameters:
      source - the source vertex number.
      target - the target vertex number.
      Returns:
      a set of vertices of minimum size whose removal disconnects the source and the target.

    • getMinimumCut

      public VertexSet getMinimumCut(int source)
      For each target vertex, different from the source, determines the vertex set of minimum size whose removal disconnects source and target - among these, we return the cutset with minimum size.
      Parameters:
      source - the source vertex number.
      Returns:
      a set of vertices of minimum size whose removal disconnects the source from some part of the graph or null if no such set exists.

    • getMinimumCut

      public VertexSet getMinimumCut()
      Computes a minimum vertex cut, that is a set of vertices of minimum size whose removal disconnects the graph. Complete graphs have no vertex cuts.
      Returns:
      a set of vertices of minimum size whose removal disconnects the graph or null if no such set exists.

    • getConnectivityNumber

      public int getConnectivityNumber()
      Computes the vertex connectivity number, that is the minimum size of a set of vertices whose removal disconnects the graph. If the graph is complete, it returns n-1, where n is the number of vertices in the graph.
      Returns:
      the edge connectivity number.