Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

  • Question1: Is there any remarks or comments for code improvement?
  • Question2: (Optional) Point out places where I can get benefit of using Lambda expression in my code (Note I am still new to Lambda expressions)?
/**
 * 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;
        }
    }

}
share|improve this question
up vote 10 down vote accepted

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.

share|improve this answer
    
Great and useful input thump up. I GO a head fixing it, and let you – maytham-ɯɐɥʇʎɐɯ Oct 2 '15 at 10:54
    
Feedback, I followed your advice and input. It is genius good, every thing is working top now. ;) – maytham-ɯɐɥʇʎɐɯ Oct 2 '15 at 13:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.