I have worked on the Ford-Fulkerson algorithm and have following code.
The code works fine, but I fill I could do more code optimization, I have worked on it for few days.
- Question: Is there any remarks or comments for code improvement?
/**
* src = source
* dst = destination
*/
public class MaxFlowAlgo {
private int vertexTotal;
private int edgeSrcDstDirectionTotal;
private List<Edge> edgeList = new ArrayList<>();
private List<Vertex> vertexList = new ArrayList<>();
private List<Vertex> minCutVertexList = new ArrayList<>();
protected void dataParsing(String folderName, String fileName) throws IOException {
int lineCounter = 0;
int mCounter = 0;
String filePath = folderName + fileName;
File fileObj = new File(filePath);
Scanner input = new Scanner(fileObj);
vertexTotal = Integer.parseInt(input.nextLine());
while (input.hasNext()) {
if (lineCounter < vertexTotal) {
vertexList.add(new Vertex(input.nextLine().trim()));
}
if (lineCounter == vertexTotal) {
edgeSrcDstDirectionTotal = Integer.parseInt(input.nextLine());
mCounter = 0;
}
if ((edgeSrcDstDirectionTotal + vertexTotal) >= lineCounter && lineCounter > vertexTotal) {
Vertex srcVertex = vertexList.get(input.nextInt());
Vertex dstVertex = vertexList.get(input.nextInt());
int capacity = input.nextInt();
if (capacity == -1)
capacity = Integer.MAX_VALUE;
Edge edge = new Edge(srcVertex, dstVertex, capacity, null);
srcVertex.edges.add(edge);
dstVertex.edges.add(edge);
srcVertex.edges.add(edge.edgeBack);
dstVertex.edges.add(edge.edgeBack);
edgeList.add(edge);
edgeList.add(edge.edgeBack);
mCounter++;
}
lineCounter++;
}
}
private List<Edge> bfs(Vertex srcVertex, Vertex sinkVertex) {
boolean hasPathTo = false;
Queue<Vertex> queue = new LinkedList<>();
queue.add(srcVertex);
minCutVertexList.clear();
minCutVertexList.add(srcVertex);
while (queue.size() > 0) {
Vertex currVertex = queue.poll();
for (Edge edge : currVertex.edges) {
Vertex dstVertex = edge.dstVertex;
if (minCutVertexList.contains(dstVertex) || edge.capacityRemain() == 0)
continue;
dstVertex.edgeTo = edge;
minCutVertexList.add(dstVertex);
if (dstVertex.equals(sinkVertex)) {
hasPathTo = true;
break;
}
queue.add(dstVertex);
}
}
List<Edge> edgePathList = new ArrayList<>();
if (hasPathTo) {
Vertex vertex = sinkVertex;
while (!vertex.equals(srcVertex)) {
edgePathList.add(vertex.edgeTo);
vertex = vertex.edgeTo.srcVertex;
}
}
return edgePathList.size() > 0 ? edgePathList : null;
}
protected List<String> fordFulkerson() {
int maxFlow = 0;
Vertex srcVertex = vertexList.get(0);
Vertex sinkVertex = vertexList.get(vertexTotal - 1);
List<String> resultList = new ArrayList<>();
List<Edge> augmentPath;
while ((augmentPath = bfs(srcVertex, sinkVertex)) != null) {
int maxCapacity = Integer.MAX_VALUE;
for (Edge e : augmentPath)
maxCapacity = Math.min(e.capacityRemain(), maxCapacity);
for (Edge e : augmentPath)
e.flowInc(maxCapacity);
//maxFlow results
maxFlow += maxCapacity;
}
//minimum cut results
for (Edge e : edgeList) {
if (minCutVertexList.contains(e.srcVertex) == true && minCutVertexList.contains(e.dstVertex) == false) {
resultList.add(vertexList.indexOf(e.srcVertex) + " " + vertexList.indexOf(e.dstVertex) + " " + e.capacity);
}
}
return resultList;
}
private class Edge {
public Vertex srcVertex;
public Vertex dstVertex;
public Integer capacity = 0;
public Integer flow = 0;
public Edge edgeBack;
public Edge(Vertex srcVertex, Vertex dstVertex, Integer capacity, Edge srcEdge) {
this.srcVertex = srcVertex;
this.dstVertex = dstVertex;
this.capacity = capacity;
if (srcEdge == null)
this.edgeBack = new Edge(dstVertex, srcVertex, capacity, this);
else
this.edgeBack = srcEdge;
}
public void flowInc(int flow) {
this.flow += flow;
this.edgeBack.flow -= flow;
}
public int capacityRemain() {
return capacity - flow;
}
}
private class Vertex {
public String vertexStationName;
public List<Edge> edges = new ArrayList<>();
public Edge edgeTo;
public Vertex(String vertexStationName) {
this.vertexStationName = vertexStationName;
}
}
}