How to use custom edge implementation with EdmondsKarp max flow algorithm

Question

I'm trying to implement and simulate a network where I can try some routing methods.

My problem is that one of my routing methods is require me to calculate MaxFlow/MinCut.

I have a custom implementation for the edges, where I added some new fields like Capacity. Here is my implementation:

import org.jgrapht.graph.DefaultWeightedEdge;

import java.io.Serializable;

public class MyDefaultWeightedEdge extends DefaultWeightedEdge implements Serializable {

    protected int freecapacity;
    protected boolean isFeasable;


    public MyDefaultWeightedEdge(){
        this.isFeasable = true;
    }

    protected int getFreeCapacity(){return this.freecapacity;}

    protected void setFreeCapacity(int i)
    {
        this.freecapacity = i;
    }

    protected boolean getFeasable(){return this.isFeasable;}

    protected void setFeasable(boolean b){this.isFeasable = b;}

    @Override
    protected Object getSource() {
        return super.getSource();
    }

    @Override
    protected Object getTarget() {
        return super.getTarget();
    }

    @Override
    protected double getWeight(){

        System.out.println("getWeight");

        StackTraceElement[] stacktrace = Thread.currentThread().getStackTrace();
        StackTraceElement e = stacktrace[2];//maybe this number needs to be corrected
        String methodName = e.getMethodName();

        if(methodName.equals(""))
        {
            return this.freecapacity;
        }
        else {
            return super.getWeight();
        }


    }

    public String toString() {
        return "(" + this.getSource() + " : " + this.getTarget() + ") " + "Weight " + this.getWeight() + " Capacity " + this.getFreeCapacity();
    }
}

When I try to use EdmondsKarpMFImpl my problem is that the algorithm uses the edgeweight as the capacity.

1. Question: How can I use my implementation of the edge?

2. Question: How can I get all of the edges which are in MinCut/MaxFlow ?

Thanks!

Answer 1

There's a lot of different solutions.

1. Standard approach. If you only have 1 type of weight (e.g. a capacity, or a cost), you could simply use a DefaultWeightedEdge and use the graph's setEdgeWeight and getEdgeWeight methods to define the edge's weight. You are free to interpret this weight in whatever way that fits your application.

public static void exampleNF(){
    //Standard approach
    Graph<Integer, DefaultWeightedEdge> graph = new DefaultUndirectedWeightedGraph<>(DefaultWeightedEdge.class);
    Graphs.addAllVertices(graph, Arrays.asList(1,2,3,4));
    Graphs.addEdge(graph, 1,2,10);
    Graphs.addEdge(graph, 2,3,4);
    Graphs.addEdge(graph, 2,4,3);
    Graphs.addEdge(graph, 1,4,8);
    Graphs.addEdge(graph, 4,3,15);
    MaximumFlowAlgorithm<Integer, DefaultWeightedEdge> mf = new EdmondsKarpMFImpl<>(graph);
    System.out.println(mf.getMaximumFlow(1,3));
}

2. Use an AsWeightedGraph. This is convenient if your graph doesn't have weights, or, if your edges have more than 1 weight (e.g. both a cost and a capacity) and you want to switch between them.

public static void exampleNF2(){
    //Make an unweighted graph weighted using an AsWeightedGraph wrapper
    Graph<Integer, DefaultEdge> graph = new DefaultUndirectedGraph<>(DefaultEdge.class);
    Graphs.addAllVertices(graph, Arrays.asList(1,2,3,4));
    DefaultEdge e1 = graph.addEdge(1,2);
    DefaultEdge e2 = graph.addEdge(2,3);
    DefaultEdge e3 = graph.addEdge(2,4);
    DefaultEdge e4 = graph.addEdge(1,4);
    DefaultEdge e5 = graph.addEdge(4,3);

    Map<DefaultEdge, Double> capacities = Map.of(e1, 10.0, e2, 4.0, e3, 3.0, e4, 8.0, e5, 15.0);
    MaximumFlowAlgorithm<Integer, DefaultEdge> mf = new EdmondsKarpMFImpl<>(new AsWeightedGraph<>(graph, capacities));
    System.out.println(mf.getMaximumFlow(1,3));
}

3. Again using an AsWeightedGraph, but this time using a function as a 'pass-through' to get a specific weight stored on the arcs themselves

public static void exampleNF3(){
    //Using the AsWeightedGraph as a function
    Graph<Integer, MyEdge> graph = new DefaultUndirectedGraph<>(MyEdge.class);
    Graphs.addAllVertices(graph, Arrays.asList(1,2,3,4));
    graph.addEdge(1,2, new MyEdge(10));
    graph.addEdge(2,3, new MyEdge(4));
    graph.addEdge(2,4, new MyEdge(3));
    graph.addEdge(1,4, new MyEdge(8));
        graph.addEdge(4,3, new MyEdge(15));

    MaximumFlowAlgorithm<Integer, MyEdge> mf = new EdmondsKarpMFImpl<>(new AsWeightedGraph<>(graph, e -> e.capacity, false, false));
    System.out.println(mf.getMaximumFlow(1,3));
}

private static class MyEdge {
    private final double capacity;

    public MyEdge(double capacity){
        this.capacity=capacity;
    }
}

4. We could also implement our own custom graph and override the getEdgeWeight and setEdgeWeight methods. In this example, we use the MyEdge class from the previous example.

public static void exampleNF4(){
    //Using a custom graph
    MyGraph graph = new MyGraph(MyEdge.class);
    Graphs.addAllVertices(graph, Arrays.asList(1,2,3,4));
    graph.addEdge(1,2, new MyEdge(10));
    graph.addEdge(2,3, new MyEdge(4));
    graph.addEdge(2,4, new MyEdge(3));
    graph.addEdge(1,4, new MyEdge(8));
    graph.addEdge(4,3, new MyEdge(15));

    MaximumFlowAlgorithm<Integer, MyEdge> mf = new EdmondsKarpMFImpl<>(graph);
    System.out.println(mf.getMaximumFlow(1,3));
}

private static class MyGraph extends SimpleWeightedGraph<Integer, MyEdge>{
    public MyGraph(Class<? extends MyEdge> edgeClass) {
        super(edgeClass);
    }
    @Override
    public double getEdgeWeight(MyEdge e){
        return e.capacity;
    }
}

There's probably more, but this covers quite a range of different approaches already. Personally I would not implement my own graph class unless I need it for something very specific.