Ford-Fulkerson Algorithm: Max flow

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 edgeList = new ArrayList<>();
private List vertexList = new ArrayList<>();
private List 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 = 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 bfs(Vertex srcVertex, Vertex sinkVertex) {
boolean hasPathTo = false;
Queue queue = new LinkedList<>();
queue.add(srcVertex);
minCutVertexList.clear();
minCutVertexList.add(srcVertex);

while (queue.size() > 0) {
Vertex currVerte

Input Parsing.

You declare a Scanner to process your input, but then you don't use it very effectively. Your code:

input = new Scanner(fileObj);
    vertexTotal = Integer.parseInt(input.nextLine());
    while (input.hasNext()) {
        if (lineCounter = 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++;
    }

would be better as:

input = new Scanner(fileObj);
    vertexTotal = input.nextInt();
    for (int i = 0; i < vertexTotal; i++) {
        vertexList.add(new Vertex(scanner.nextLine().trim());
    }
    edgeSrcDstDirectionTotal = input.nextInt();
    for (int i = 0; i < edgeSrcDstDirectionTotal; i++) {
        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);
    }

General

In general, I am impressed with your code. It is neat, variable names are good, the logic is well structured, and I can mostly follow it without having to run it. This is a good thing. Some smallish items have impressed me too:

• you are using interfaces for variables, and not their concrete implementations. Code like Queue queue = new LinkedList<>(); is good. It is common to see people making the queue a LinkedList, which is an anti-pattern you have avoided.

• your variables have great names,a nd are self-documenting.

• your generics all appear to be "right".

On the other hand, you have a number of items that are small, but wrong too:

• size() is an anti-pattern in a loop condition. Your code while (queue.size() > 0) { should instead be: while (!queue.isEmpty()) {

-
Even 1-liner if-blocks should have braces - it prevents maintenance bugs later. This code:

if (minCutVertexList.contains(dstVertex) || edge.capacityRemain() == 0)
            continue;

should be:

if (minCutVertexList.contains(dstVertex) || edge.capacityRemain() == 0) {
            continue;
        }

While we are on it, you may improve performance if you put the capacity-check first.

-
The complete while-loop in the bfs method should be a function, and it should return true. The break condition should instead be return true. Then your code becomes:

if(!hasPathTo(sinkVertex)) {
    return null;
}
List edgePathList = new ArrayList<>();
Vertex vertex = sinkVertex;
while (!vertex.equals(srcVertex)) {
    edgePathList.add(vertex.edgeTo);
    vertex = vertex.edgeTo.srcVertex;
}
return edgePathList;

-
Your Edge and Vertex classes should both be static - it will save having a pointer back to the outer class that you never use.

StackExchange Code Review Q#106335, answer score: 10