Package org.graph4j.connectivity

Class EdgeConnectivityAlgorithm

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.connectivity.EdgeConnectivityAlgorithm

public class EdgeConnectivityAlgorithm
extends GraphAlgorithm

Determines a maximum size set of edge disjoint paths between two vertices, a minimum size set of edges whose removal disconnects two vertices, the minimum cardinality edge cut and the edge connectivity number.

Author:

Cristian Frăsinaru

See Also:

• StoerWagnerMinimumCut

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
EdgeConnectivityAlgorithm(Graph graph)	Creates an algorithm for determining the edge connectivity of a graph.

Method Summary

Modifier and Type	Method	Description
int	countMaximumDisjointPaths(int source, int target)	Determines the maximum size of a set of edge disjoint paths between the source and the target without creating the paths.
int	getConnectivityNumber()	Computes the edge connectivity number, that is the minimum size of a set of edges whose removal disconnects the graph.
List<Path>	getMaximumDisjointPaths(int source, int target)	Computes a maximum size set of edge disjoint paths between the source and the target.
EdgeCut	getMinimumCut()	Computes a set of edges of minimum size whose removal disconnects the graph.
EdgeCut	getMinimumCut(int source, int target)	Computes a minimum cardinality edge cut, that is a set of edges 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

EdgeConnectivityAlgorithm

public EdgeConnectivityAlgorithm(Graph graph)

Creates an algorithm for determining the edge 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 edge disjoint paths between the source and the target without creating the paths. 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 edge disjoint paths between the source and the target.

getMinimumCut

public EdgeCut getMinimumCut(int source,
 int target)

Computes a minimum cardinality edge cut, that is a set of edges of minimum size whose removal disconnects the source and the target. The cut is created by solving the corresponding maximum flow problem.

Parameters:

source - the source vertex number.

target - the target vertex number.

Returns:

the minimum cut whose removal disconnects the source and the target.

getMaximumDisjointPaths

public List<Path> getMaximumDisjointPaths(int source,
 int target)

Computes a maximum size set of edge disjoint paths between the source and the target.

Parameters:

source - the source vertex number.

target - the target vertex number.

Returns:

a maximum size set of edge disjoint paths between the source and the target.

getMinimumCut

public EdgeCut getMinimumCut()

Computes a set of edges of minimum size whose removal disconnects the graph.

Returns:

a set of edges of minimum size whose removal disconnects the graph.

getConnectivityNumber

public int getConnectivityNumber()

Computes the edge connectivity number, that is the minimum size of a set of edges whose removal disconnects the graph.

Returns:

the edge connectivity number.