如何通过 EdmondsKarp 最大流算法使用自定义边实现

Question

我正在尝试实施和模拟一个可以尝试一些路由方法的网络。

我的问题是我的一种路由方法要求我计算 MaxFlow/MinCut。

我有一个边缘的自定义实现，我在其中添加了一些新字段，例如容量。这是我的实现：

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

当我尝试使用 EdmondsKarpMFImpl 时，我的问题是该算法使用边缘权重作为容量。

问题：如何使用我的边缘实现？
问题：如何获得 MinCut/MaxFlow 中的所有边？

谢谢！

Answer 1

有很多不同的解决方案。

标准方法。如果您只有一种类型的权重（例如容量或成本），您可以简单地使用 DefaultWeightedEdge 并使用图形的 setEdgeWeight 和 getEdgeWeight 方法来定义边的权重。您可以按照适合您的应用的任何方式自由解释此权重。

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

使用 AsWeightedGraph。如果您的图形没有权重，或者如果您的边具有超过 1 个权重（例如，成本和容量）并且您想在它们之间切换，这将很方便。

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

再次使用 AsWeightedGraph，但这次使用函数作为 'pass-through' 来获取存储在弧本身上的特定权重

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

我们还可以实现自己的自定义图表并覆盖 getEdgeWeight 和 setEdgeWeight 方法。在此示例中，我们使用上一个示例中的 MyEdge class。

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

可能还有更多，但这已经涵盖了相当多的不同方法。就我个人而言，我不会实现自己的图表 class 除非我需要它用于非常具体的事情。

如何通过 EdmondsKarp 最大流算法使用自定义边实现

How to use custom edge implementation with EdmondsKarp max flow algorithm

jgrapht

edmonds-karp