public class UnweightedFlow<T extends Vertex>
extends java.lang.Object
implements java.io.Serializable
The Class UnweightedFlow network, this class only works for graphs such that do not have a 2-cycle. (A 2-cycle? What is a 2-cycle in an undirected graph? CAC, January 2009) The purpose of this class is to make allow the calculation of an arbitrary number of either edge and vertex disjoint paths on and adjacency list structure.
The algorithm used for calculating edge disjoint paths is similar to the Ford-Fulkerson method of finding max-flow min-cut. The algorithm starts by finding an augmenting path from the source to the sink using BFS, it then stores this path and repeats k times if possible. It then takes these k paths, removes all edges that are reused an even number of times, places them together (since we don't know which remaining edge segments belong together just that the segments all belong to a path), and uses dfs to search for each path between source and sink, leading to edge disjoint paths.
The way the algorithm finds edge disjoint paths is by converting the graph to an alternate form and then running the vertex disjoint algorithm and converting the result (and graph) back. This conversion works as follows: for each vertex V create vertex W, and move all of V's out edges to W, and finally make V adjacent to W (remember we are talking directed graphs here). The resulting edge disjoint paths will include V and W, by storing a list of which vertices were in the original graph we may remove the Ws from the path (and graph) resulting in a set of vertex disjoint paths (and the original graph).
Since typically we want to solve for multiple sources and sinks the conversion also creates a super-source and super-sink allowing the algorithm to work; these are removed from the final product and graph. This class is a factory class because creating the graph is delicate and requires methods that should be held outside of the constructor to function correctly.
| Constructor and Description |
|---|
UnweightedFlow(java.util.Set<T> vertices,
java.util.Set<T> sources,
java.util.Set<T> sinks) |
| Modifier and Type | Method and Description |
|---|---|
java.util.List<Path> |
getVertexDisjointPaths(int n)
The main algorithm.
|
public java.util.List<Path> getVertexDisjointPaths(int n)
n - The number of paths we want to find.