Алгоритм максимального потока слишком медленный в 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

Может быть, моя реализация алгоритма медленная или это нормально, что алгоритм максимального потока медленнее, когда число узлов и ребер велико?

Я думаю, что ответ «Да» на оба вопроса:

Согласно странице Википедии о проблеме MaxFlow , сложность решений, которые гарантированно прекратятсявсе O(VE) или хуже. Алгоритм Эдмондса-Карпа O(VE^2).

(V - число вершин, E - количество ребер в графе.)

Короче говоря, все алгоритмы maxflow медленны, есликоличество узлов или ребер велико.

Однако я думаю, что в вашей реализации также есть проблемы. Например, комментарий к методу BFS_ гласит «найти путь от nodeU до nodeV, если он существует», но он ищет все пути от 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, когда оно уже введено.