Java JUNG EdmondsKarpMaxFlow застревает в бесконечном цикле - PullRequest
Новая
       115

Java JUNG EdmondsKarpMaxFlow застревает в бесконечном цикле

0 голосов
/ 28 мая 2020

Я пытаюсь использовать объект JUNG EdmondsKarpMaxFlow, чтобы найти максимальный поток между всеми парами узлов в ориентированном графе. Я создал простой ориентированный граф и без ошибок запускал его для каждой комбинации узлов. Вот рабочий пример для справки: https://pastebin.com/TLsEduxZ

Однако, когда я вызываю тот же код edkAlg.evaluate () на более сложном графике, l oop останавливается на каждый раз определенное ребро / итерацию. 

public class SomeClass{
...
...
    MyEdmondsKarpMaxFlow edk = new MyEdmondsKarpMaxFlow(dirGraph);
    edk.runEdk();
}

public class MyEdmondsKarpMaxFlow {

    int edgeFlowMapId = 0;
    protected DirectedSparseMultigraph<GraphElements.MyVertex, GraphElements.MyEdge> dirGraph;
    protected Map<GraphElements.MyEdge, Double> edgeFlowMap = new HashMap<GraphElements.MyEdge, Double>();

    protected Transformer<GraphElements.MyEdge, Double> capTransformer = new Transformer<GraphElements.MyEdge, Double>() {
        public Double transform(GraphElements.MyEdge edge) {
            return edge.getCapacity();
        }
    };

    // This Factory produces new edges for use by the algorithm
    protected Factory<GraphElements.MyEdge> edgeFactory = new Factory<GraphElements.MyEdge>() {
        public GraphElements.MyEdge create() {
           return new GraphElements.MyEdge(Integer.toString(edgeFlowMapId++));
        }
    };

    public MyEdmondsKarpMaxFlow(DirectedSparseMultigraph<GraphElements.MyVertex, GraphElements.MyEdge> dirGraph) {
        this.dirGraph = dirGraph;
    }

    public void runEdk() {
        Collection<GraphElements.MyVertex> vertexCollection = dirGraph.getVertices();

        for (Iterator iterator1 = vertexCollection.iterator(); iterator1.hasNext(); ) {
            GraphElements.MyVertex v1 = (GraphElements.MyVertex) iterator1.next();
            Collection<GraphElements.MyVertex> vertexCollection2 = dirGraph.getVertices();

            for (Iterator iterator2 = vertexCollection2.iterator(); iterator2.hasNext(); ) {
                GraphElements.MyVertex v2 = (GraphElements.MyVertex) iterator2.next();
                if (v1.equals(v2)) continue;
                EdmondsKarpMaxFlow<GraphElements.MyVertex, GraphElements.MyEdge> edkAlg = new EdmondsKarpMaxFlow(dirGraph, v1, v2, capTransformer, edgeFlowMap, edgeFactory);
                edkAlg.evaluate();
                System.out.println("max edk flow between v1 and v2 is : " + edkAlg.getMaxFlow());
            }
        }
        System.out.println("FIN");
    }
}

Я использую пользовательские определения Vertices и Edges, которые ведут себя так, как ожидалось, но просто имеют больше атрибутов, чем в тривиальном примере. Код находит максимальный поток между v1 и v2 отлично до первых 201 итераций, но каждый раз застревает в '.evaluate ()' (он использует один и тот же порядок пар каждый раз, поэтому он всегда застревает на problemNode123 -> проблемаNode456). Не совсем уверен, где я ошибаюсь, и в Интернете не так много помощи, поэтому приветствуются любые указатели!

1 Ответ

0 голосов
/ 31 мая 2020

Вы не предоставляете достаточно информации, чтобы быть уверенным, но проблема почти наверняка связана с тем фактом, что вы не определили hashCode() и equals() для своих настраиваемых узловых и граничных объектов.

...