Java JUNG EdmondsKarpMaxFlow getting stuck in infinite loop

Question

I am trying to use JUNG's EdmondsKarpMaxFlow object to find the max flow between all node pairs in a directed graph. I created a simple directed graph and ran it on each combination of nodes with no error. Here's the working example for reference: https://pastebin.com/TLsEduxZ

However, when I call the same 'edkAlg.evaluate()' code on a more complex graph, the loop stops on a certain edge/iteration each time.

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

I use custom definitions of Vertices and Edges which behave as expected but simply have more attributes than the trivial example. The code finds max flow between v1 and v2 perfectly fine up to the first 201 iterations, but gets stuck in '.evaluate()' after each time (it uses the same order of pairs each time so it is always stuck on problemNode123 -> problemNode456). Not too sure where I'm going wrong, and there isn't much help online so any pointers are appreciated!

Answer 1

You're not providing quite enough information to be sure, but the problem is almost certainly related to the fact that you haven't defined hashCode() and equals() for your custom node and edge objects.