具有大量节点和边的 Java 中的最大流算法太慢

Question

我最近写了一个Java应用程序，它使用最大流来执行图像分割。当节点数量很少时代码工作正常，但当我使用大量节点时它非常慢。会不会是我的算法实现速度慢，或者当节点和边数很大时，最大流算法速度慢是正常的？下面是与最大流量计算有关的相关代码。这个想法是计算最大流量并获得将源 s 与汇 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?

我认为两者的答案都是肯定的：

根据 MaxFlow Problem 上的维基百科页面，保证终止的解决方案的复杂度都是 O(VE) 或更差。 Edmonds-Karp 算法是 O(VE^2).

（V是顶点数，E是图中的边数。）

简而言之，如果节点或边的数量很大，所有 maxflow 算法都会变慢。

不过，我觉得你的实现也有问题。例如，BFS_ 方法的注释说 "find path from nodeU to nodeV if one exists" 但它所做的是从 nodeU 中找到所有路径。如果您查看它，则未使用 nodeV 参数。

还有很多可以执行的微优化。例如：

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

您正在呼叫 get 两次。第二次调用是不必要的，因为你永远不会调用 `put(e.destination(), false)。并且

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

可以是

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

因为如果你 put 值 true 已经被放置了，这并不重要。

具有大量节点和边的 Java 中的最大流算法太慢

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

java

graph-theory

image-segmentation

max-flow