更新Ford-Fulkerson中的图表

Question

我正在实现Fulkerson算法，但是在增强阶段之后，我在更新图表时遇到了一些问题。我想我的数据结构并不能让这件事变得简单。

为了表示该图形，我使用以下方法：

private Map<Vertex, ArrayList<Edge>> outgoingEdges;

也就是说，我在每个顶点上都会关联到它的传出边列表。

为了管理后向边，我为图中的每个边关联了一个“相反”的边。

任何建议都会受到赞赏。

public class FF {

    /**
     * Associates each Vertex with his list of outgoing edges
     */
    private Map<Vertex, ArrayList<Edge>> outgoingEdges;

    public FF() {
        outgoingEdges = new HashMap<Vertex, ArrayList<Edge>>();
    }

    /**
     * Returns the nodes of the graph
     */ 
    public Collection<Vertex> getNodes() {
        return outgoingEdges.keySet();
    }

    /**
     * Returns the outgoing edges of a node
     */
    public Collection<Edge> getIncidentEdges(Vertex v) {
        return outgoingEdges.get(v);
    }

    /**
     * Adds a new edge to the graph
     */
    public void insertEdge(Vertex source, Vertex destination, float capacity) throws Exception {
        if (!(outgoingEdges.containsKey(source) && outgoingEdges.containsKey(destination)))
            throw new Exception("Unable to add the edge");

        Edge e = new Edge(source, destination, capacity);
        Edge opposite = new Edge(destination, source, capacity);
        outgoingEdges.get(source).add(e);
        outgoingEdges.get(destination).add(opposite);
        e.setOpposite(opposite);
        opposite.setOpposite(e);
    }

    /**
     * Adds a new node to the graph
     */
    public void insertNode(Vertex v) {
        if (!outgoingEdges.containsKey(v))
            outgoingEdges.put(v, new ArrayList<Edge>());
    }

    /**
     * Ford-Fulkerson algorithm
     * 
     * @return max flow
     */
    public int fordFulkerson(Vertex source, Vertex destination) {
        List<Edge> path = new ArrayList<Edge>();
        int maxFlow = 0;
        while(bfs(source, destination, path)) {
            // finds the bottleneck
            float minCap = bottleneck(path);
            // updates the maxFlow
            maxFlow += minCap;            
            // updates the graph <-- this updates only the local list path, not the graph!
            for(Edge e : path) {
                try {
                    e.addFlow(minCap);
                    e.getOpposite().addFlow(-minCap);
                } catch (Exception e1) {
                    e1.printStackTrace();
                }
            }
            path.clear();
        }
        return maxFlow;
    } 

    /**
     * @param Path of which we have to find the bottleneck
     * @return bottleneck of the path
     */
    private float bottleneck(List<Edge> path) {
        float min = Integer.MAX_VALUE;
        for(Edge e : path) {
            float capacity = e.getCapacity();
            if(capacity <= min) {
                min = capacity;
            }
        }
        return min;
    }

    /**
     * BFS to obtain a path from the source to the destination
     * 
     * @param source 
     * @param destination
     * @param path
     * @return
     */
    private boolean bfs(Vertex source, Vertex destination, List<Edge> path) {
        Queue<Vertex> queue = new LinkedList<Vertex>();
        List<Vertex> visited = new ArrayList<Vertex>(); // list of visited vertexes
        queue.add(source);
        //source.setVisited(true);
        visited.add(source);
        while(!queue.isEmpty()) {
            Vertex d = queue.remove();
            if(!d.equals(destination)) {
                ArrayList<Edge> d_outgoingEdges = outgoingEdges.get(d);
                for(Edge e : d_outgoingEdges) {
                    if(e.getCapacity() - e.getFlow() > 0) { // there is still available flow
                        Vertex u = e.getDestination();
                        if(!visited.contains(u)) {
                            //u.setVisited(true);
                            visited.add(u);
                            queue.add(u);
                            path.add(e);
                        }
                    }
                }
            }
        }
        if(visited.contains(destination)) {
            return true;
        }
        return false;
    }
}

边缘

public class Edge {

    private Vertex source;
    private Vertex destination;
    private float flow;
    private final float capacity;
    private Edge opposite;

    public Edge(Vertex source, Vertex destination, float capacity) {
        this.source = source;
        this.destination = destination;
        this.capacity = capacity;
    }

    public Edge getOpposite() {
        return opposite;
    }

    public void setOpposite(Edge e) {
        opposite = e;
    }

    public void setSource(Vertex v) {
        source = v;
    }

    public void setDestination(Vertex v) {
        destination = v;
    }

    public void addFlow(float f) throws Exception {
        if(flow == capacity) {
            throw new Exception("Unable to add flow");
        }
        flow += f;
    }

    public Vertex getSource() {
        return source;
    }

    public Vertex getDestination() {
        return destination;
    }

    public float getFlow() {
        return flow;
    }

    public float getCapacity() {
        return capacity;
    }

    public boolean equals(Object o) {
        Edge e = (Edge)o;
        return e.getSource().equals(this.getSource()) &&       e.getDestination().equals(this.getDestination());
    }
}

顶点

public class Vertex {

    private String label;

    public Vertex(String label) {
        this.label = label;
    }

    public boolean isVisited() {
        return visited;
    }

    public String getLabel() {
        return label;
    }

    public boolean equals(Object o) {
        Vertex v = (Vertex)o;
        return v.getLabel().equals(this.getLabel());
    }
}

Answer 1

尽管严格地说，这个问题可以被认为是“非主题”(因为您主要是在寻找调试帮助)，但这是您的第一个问题之一，因此有一些一般性的提示：

当你在这里发问的时候，把这里的人看作是志愿者。让轻松让他们回答这个问题。在这种情况下:您应该创建一个MCVE，这样人们就可以快速地复制和粘贴您的代码(最好是在单个代码块中)并运行程序，而无需付出任何努力。例如，您应该包括一个测试类，包含一个main方法，如下所示：

public class FFTest
{
    /**
     *     B---D
     *    / \ / \
     *   A   .   F
     *    \ / \ /
     *     C---E
     */
    public static void main(String[] args) throws Exception
    {
        FF ff = new FF();

        Vertex vA = new Vertex("A");
        Vertex vB = new Vertex("B");
        Vertex vC = new Vertex("C");
        Vertex vD = new Vertex("D");
        Vertex vE = new Vertex("E");
        Vertex vF = new Vertex("F");
        ff.insertNode(vA);
        ff.insertNode(vB);
        ff.insertNode(vC);
        ff.insertNode(vD);
        ff.insertNode(vE);
        ff.insertNode(vF);

        ff.insertEdge(vA, vB, 3.0f);
        ff.insertEdge(vA, vC, 2.0f);
        ff.insertEdge(vB, vD, 1.0f);
        ff.insertEdge(vB, vE, 4.0f);
        ff.insertEdge(vC, vD, 2.0f);
        ff.insertEdge(vC, vE, 1.0f);
        ff.insertEdge(vD, vF, 2.0f);
        ff.insertEdge(vE, vF, 1.0f);

        float result = ff.fordFulkerson(vA, vF);
        System.out.println(result);
    }
}

(无论如何，在写问题时，您应该已经创建了这样一个测试类！)

您应该清楚地表明，您是而不是，使用StackOverflow作为“神奇的问题解决机器”。在本例中:我已经提到您应该包括调试输出。如果您用以下方法扩展了您的FF类.

private static void printPath(List<Edge> path)
{
    System.out.println("Path: ");
    for (int i=0; i<path.size(); i++)
    {
        Edge e = path.get(i);
        System.out.println(
            "Edge "+e+
            " flow "+e.getFlow()+
            " cap "+e.getCapacity());
    }
}

它可以在主循环中调用如下所示：

    while(bfs(source, destination, path)) {
        ...
        System.out.println("Before updating with "+minCap);
        printPath(path);

        // updates the maxFlow
        ....

        System.out.println("After  updating with "+minCap);
        printPath(path);

        ...
    }

那么您就已经注意到代码的主要问题：.

bfs方法是错误的！您是，而不是，正确地重构引导您到达目标顶点的路径。相反，您将每个已访问的顶点添加到路径中。您必须跟踪用于到达特定节点的边缘，当您到达目标顶点时，必须向后移动。

一个快速和肮脏的方法可以粗略地(！)看上去像这样：

private boolean bfs(Vertex source, Vertex destination, List<Edge> path) {
    Queue<Vertex> queue = new LinkedList<Vertex>();
    List<Vertex> visited = new ArrayList<Vertex>(); // list of visited vertexes
    queue.add(source);
    visited.add(source);
    Map<Vertex, Edge> predecessorEdges = new HashMap<Vertex, Edge>();
    while(!queue.isEmpty()) {
        Vertex d = queue.remove();
        if(!d.equals(destination)) {
            ArrayList<Edge> d_outgoingEdges = outgoingEdges.get(d);
            for(Edge e : d_outgoingEdges) {
                if(e.getCapacity() - e.getFlow() > 0) { // there is still available flow
                    Vertex u = e.getDestination();
                    if(!visited.contains(u)) {
                        visited.add(u);
                        queue.add(u);
                        predecessorEdges.put(u, e);
                    }
                }
            }
        }
        else
        {
            constructPath(destination, predecessorEdges, path);
            return true;
        }
    }
    return false;
}

private void constructPath(Vertex destination,
    Map<Vertex, Edge> predecessorEdges, List<Edge> path)
{
    Vertex v = destination;
    while (true)
    {
        Edge e = predecessorEdges.get(v);
        if (e == null)
        {
            return;
        }
        path.add(0, e);
        v = e.getSource();
    }
}

(你应该总是独立地测试这样一种中心方法。您本可以轻松地创建一个小型测试程序来计算多条路径，并且您很快就会发现这些路径是错误的--因此，福特富尔克森( Ford Fulkerson )根本无法正常工作。

进一步评论：

每当重写equals方法时，还必须重写hashCode方法。有些规则适用于这里，您应该绝对是指Object#equals和Object#hashCode。

另外重写toString方法通常是有益的，这样您就可以轻松地将对象打印到控制台。

在您的示例中，这些方法可以为Vertex实现如下

@Override
public int hashCode()
{
    return getLabel().hashCode();
}

@Override
public boolean equals(Object o) {
    Vertex v = (Vertex)o;
    return v.getLabel().equals(this.getLabel());
}

@Override
public String toString()
{
    return getLabel();
}

对于Edge

@Override
public String toString()
{
    return "("+getSource()+","+getDestination()+")";
}

@Override
public int hashCode()
{
    return source.hashCode() ^ destination.hashCode();
}

@Override
public boolean equals(Object o) {
    Edge e = (Edge)o;
    return e.getSource().equals(this.getSource()) &&       
        e.getDestination().equals(this.getDestination());
}

边的容量是float值，因此产生的流也应该是float值。

通过上面提到的修改，程序运行并打印一个“可信”的结果。我让没有来验证它的正确性。但这是你的任务，现在应该容易多了。

不，索诺·特德斯科。