Ford-Fulkerson Algorithm: Max flow

Question

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;
 }
 }
}

Answer 1

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 < 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++;
 }

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<Vertex> 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<Edge> 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.

• Maytham Fahmi: Great and useful input thump up. I GO a head fixing it, and let you
• Maytham Fahmi: Feedback, I followed your advice and input. It is genius good, every thing is working top now. ;)

Answer 2

There are a couple of points which the existing answer missed, one of which I consider quite important.

Datatypes

 private List<Edge> edgeList = new ArrayList<>();
 private List<Vertex> vertexList = new ArrayList<>();
 private List<Vertex> minCutVertexList = new ArrayList<>();

Why are these lists?

edgeList is appended to in the parsing stage and iterated over in the output stage, so it could be any Collection. List is as reasonable as any; I personally would use Set, but I can see an argument that List is more efficient.

vertexList is appended to in the parsing stage and looked up by index when parsing the edges, so it has to be a List. But the output stage calls vertexList.indexOf in a loop, and there it would be more efficient to pre-compute a Map<Vertex, Integer> (or to store the index as a field of the Vertex).

minCutVertexList is cleared, added to, and tested for contains. It should be a Set, because List.contains is always going to be a O(n) operation.

Unused variables

I don't see any reads of mCounter or maxFlow except in their self-updates (++ and += respectively). Maybe they were for debugging or you changed your mind about the signatures of the methods, but they can be deleted now.

Style

Style is always disputable, so these are opinions, but I hope that they're at least majority opinions.

• edgeList etc. are a form of Hungarian notation. The IDE will tell us that they're lists (or set, in the case of the min cut vertices, after applying the suggestion above). I would prefer edges, vertices, and either minCutVertices or just minCut.
• Comparisons to Boolean literals are ugly. if (minCutVertexList.contains(e.srcVertex) == true && minCutVertexList.contains(e.dstVertex) == false) could just be if (minCutVertexList.contains(e.srcVertex) && !minCutVertexList.contains(e.dstVertex))