Max flow algorithm too slow in Java with large number of nodes and edges

Question

I have recently written a Java application that uses maximum flow to perform image segmentation. The code works fine when the number of nodes is small but it is extremely slow when I use a large number of nodes. Could it be that my implementation of the algorithm is slow or is it normal that max flow algorithm is slower when the number of nodes and edges are large? Below is the relevant code relating to the calculation of the max flow. The idea is to calculate the max flow and also get a cut that separates the source s from the sink t

// find path from nodeU to nodeV if one exists
public Map<Integer, Edge> BFS_(Integer nodeU, Integer nodeV)
{
    Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
    Map<Integer, Edge> path = new HashMap<Integer, Edge>();

    Queue<Integer> queue = new LinkedList<Integer>();

    queue.add(nodeU);
    visited.putIfAbsent(nodeU, true);
    path.putIfAbsent(nodeU, null);

    while( !queue.isEmpty() )
    {
        Integer cur = queue.poll();
        Set<Edge> neighbors = this.outgoing(cur);
        Iterator<Edge> iter = neighbors.iterator();

        while( iter.hasNext() )
        {
            Edge e = iter.next();
            // if not null
            if( visited.get(e.destination()) == null || visited.get(e.destination()) == false )
            {
                visited.putIfAbsent(e.destination(), true);
                path.putIfAbsent(e.destination(), e);
                queue.add(e.destination());
            }
        }
    }

    return path;
}

// find edges that link nodeU to nodeV and make a path
public Solution makePath(Map<Integer, Edge> in, Integer nodeU, Integer nodeV)
{
    Solution path = null;
    Integer parent = nodeV;

    path = new Solution();

    path.edges = new HashSet<Edge>();
    path.minflow = Integer.MAX_VALUE;

    Edge e = null;
    while( ( e = in.get(parent) ) != null )
    {
        if( e.flow() > 0 && e.flow() < path.minflow )
        {
            path.minflow = e.flow();
        }
        path.edges.add(e);
        parent = e.source();
    }

    if( path.edges.size() == 0 )
    {
        return null;
    }

    return path;
}

// make residual graph
 public Graph residualGraph()
 {
    Iterator<Edge> iter = this.edges.iterator();
    Set<Edge> back_edges = new HashSet<Edge>();
    Set<Edge> to_remove = new HashSet<Edge>();
    Integer forward_flow, backward_flow;

    while( iter.hasNext() )
    {
        Edge cur = iter.next();
        Edge backward_edge = new Edge(cur).reverse();
        // backward edge = f(e) > 0
        backward_flow = cur.flow();
        if( backward_flow > 0 )
        {
            // add forward and backward edges
            //this.addEdge(backward_edge);
            backward_edge.flow(backward_flow);
            back_edges.add(backward_edge);
        }
        // forward flow = c(e) - f(e) > 0
        forward_flow = cur.capacity() - cur.flow();
        // if forward flow is zero, remove edge
        if( forward_flow <= 0 )
        {
            //this.removeEdge(cur);
            to_remove.add(cur);
        }
        else
        {
            // modify forward edge in residual graph to contain flow it can send
            cur.flow(forward_flow);
        }
    }

    this.edges.removeAll(to_remove);
    this.edges.addAll(back_edges);

    return this;
}

// calculate max flow 
public Graph edmondsKarp(Integer nodeU, Integer nodeV)
{
    // create residual graph
    Graph h = new DirectedGraph(this);
    Graph r = new DirectedGraph(h);

    r.residualGraph();

    // run bfs on residual graph and while a path exists
    // keep augmenting the flow through the path
    Map<Integer, Edge> bfs = r.BFS_(nodeU, nodeV);

    Solution path = null;

    while( ( path = this.makePath(bfs, nodeU, nodeV) ) != null )
    {
        if( path.minflow > 0 )
        {
            h.updateNetwork(path.edges, path.minflow);
        }

        r = new DirectedGraph(h);
        r.residualGraph();
        bfs = r.BFS_(nodeU, nodeV);
    }

    // found max flow here
    // sum of outgoing flow from source = sum of incoming flow in sink
    Integer sumU = 0, sumV = 0;
    Iterator<Edge> s_edges = h.outgoing(nodeU).iterator();
    Iterator<Edge> t_edges = h.incoming(nodeV).iterator();

    while( s_edges.hasNext() )
    {
        Edge e = s_edges.next();

        sumU += e.flow();
    }

    while( t_edges.hasNext() )
    {
        Edge e = t_edges.next();

        sumV += e.flow();
    }

    System.out.println("t_edges: " + h.incoming(nodeV) + ", " + h.incoming(nodeV).size());

    if( !sumU.equals(sumV) )
    {
        Logger logger = Logger.getLogger(this.getClass().getName());

        logger.warning("flow in " + sumU + " not equal to flow out " + sumV);
    }

    h.maxflow = sumU;

    return h;
}

Answer 1

Could it be that my implementation of the algorithm is slow or is it normal that max flow algorithm is slower when the number of nodes and edges are large?

I think that the answer is Yes to both:

According to the Wikipedia page on the MaxFlow Problem, the complexity of solutions that are guaranteed to terminate are all O(VE) or worse. The Edmonds-Karp algorithm is O(VE^2).

(V is the number of vertices and E is the number of edges in the graph.)

In short all maxflow algorithms are slow if the number of nodes or edges is large.

However, I think there are also problems in your implementation. For example, the comment on BFS_ method says "find path from nodeU to nodeV if one exists" but what it is doing is to find all paths from nodeU. If you look at it, the nodeV argument isn't used.

And there are lots of micro-optimizations that could be performed. For example:

if( visited.get(e.destination()) == null || visited.get(e.destination()) == false )
{
    visited.putIfAbsent(e.destination(), true);
    path.putIfAbsent(e.destination(), e);
    queue.add(e.destination());
}

You are calling get twice. The second call is unnecessary because you never call `put(e.destination(), false). And

visited.putIfAbsent(e.destination(), true);

can be

visited.put(e.destination(), true);

because it doesn't matter if you put the value true when it has already been put.