Поиск набора ребер MinCut в алгоритме сетевого потока с предварительным потоком - PullRequest
Новая
       25

Поиск набора ребер MinCut в алгоритме сетевого потока с предварительным потоком

2 голосов
/ 11 ноября 2011

У меня есть реализация алгоритма потока потока предварительной подачи, который возвращает максимальный поток сети потока.Что мне нужно, это определить набор насыщенных ребер, которые образуют разрез на графике.

В моей текущей реализации я ищу насыщенные передние ребра с пустыми задними ребрами на графике, для которых расстояние от ребраИсточник до краевой цели больше или равен единице (т. е. источник имеет большую высоту, чем цель).Если в графе есть только один возможный набор ребер, удовлетворяющий минимальному разрезу, алгоритм работает нормально, но если алгоритм может найти более одного разреза в графе, он возвращает все насыщенные ребра в графе.Я скопировал мой код ниже.Любая помощь высоко ценится. 

public Set<Edge> cutEdges(){
    for (String v_name : vertices.keySet()){
        int v_id = vertices.get(v_name);
        ArrayList<Edge> veList = residual_edges.get(v_id);
        for (Edge ve : veList){
            boolean reverseFound = false;
            EdgeData vinfo = (EdgeData) ve.getData();
            if (vinfo.getAvailable() == 0){
                Vertex temp1 = ve.getFirstEndpoint();
                Vertex temp2 = ve.getSecondEndpoint();
                int u_id = (v_id != vertices.get(temp1.getName().toString()) ? 
                        vertices.get(temp2.getName().toString()) : vertices.get(temp1.getName().toString()));
                ArrayList<Edge> ueList = residual_edges.get(u_id);
                for (Edge ue : ueList){
                    EdgeData uinfo = (EdgeData) ue.getData();
                    if (ue.getFirstEndpoint().getName().toString().equals(temp2.getName().toString()) && 
                            ue.getSecondEndpoint().getName().toString().equals(temp1.getName().toString())){                            
                        if (((VertexData)ue.getFirstEndpoint().getData()).getPreflowHeight() - 
                                ((VertexData)ue.getSecondEndpoint().getData()).getPreflowHeight() >= 1){
                            if (uinfo.getFlow() == 0)
                            continue;
                        }
                        reverseFound = true;
                        break;
                    }
                }
                if (!reverseFound){
                    if (((VertexData)temp1.getData()).getPreflowHeight() - 
                            ((VertexData)temp2.getData()).getPreflowHeight() >= 1)
                        cut_edges.add(ve);
                }
            }
        }
    }
    return cut_edges;
}

1 Ответ

1 голос
/ 10 декабря 2011

Я скопирую свой ответ из вопроса Как найти минимальный разрез на графике с использованием алгоритма максимального потока? :

Из исходной вершины выполнитепоиск в глубину вдоль ребер, которые все еще имеют остаточную емкость (то есть ненасыщенные ребра).Разрез состоит из всех ребер, которые были «видны» (т. Е. Попадают в посещенную вершину), но не были пройдены, поскольку они насыщены.Как вы заметили, могут быть другие насыщенные края, которые не являются частью минимального среза.

...