-2

我正在尝试实现 Ford-Fulkerson 的 java 版本。我使用了wikipedia中的 python 实现作为基础：

class Edge(object):
    def __init__(self, u, v, w):
        self.source = u
        self.sink = v  
        self.capacity = w
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity)

class FlowNetwork(object):
    def __init__(self):
        self.adj = {}
        self.flow = {}

    def add_vertex(self, vertex):
        self.adj[vertex] = []

    def get_edges(self, v):
        return self.adj[v]

    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)
        redge = Edge(v,u,0)
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0
        self.flow[redge] = 0

    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and edge not in path:
                result = self.find_path( edge.sink, sink, path + [edge]) 
                if result != None:
                    return result

    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        while path != None:
            residuals = [edge.capacity - self.flow[edge] for edge in path]
            flow = min(residuals)
            for edge in path:
                self.flow[edge] += flow
                self.flow[edge.redge] -= flow
            path = self.find_path(source, sink, [])
        return sum(self.flow[edge] for edge in self.get_edges(source))

这是我的java实现：

import org.junit.Test;

import java.util.*;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

public class MaxFlowTest {

    @Test
    public void maxFlowTest() {
        FlowNetwork unit = new FlowNetwork(Arrays.asList(0, 1, 2, 3, 4, 5));

        unit.addEdge(0, 1, 16);
        unit.addEdge(0, 2, 13);
        unit.addEdge(1, 3, 12);
        unit.addEdge(1, 2, 10);
        unit.addEdge(2, 1, 4);
        unit.addEdge(2, 4, 14);
        unit.addEdge(3, 2, 9);
        unit.addEdge(4, 3, 7);
        unit.addEdge(3, 5, 20);
        unit.addEdge(4, 5, 4);

        assertThat(unit.maxFlow(0, 5), is(23)); //algorithm incorrectly returning 7
    }
}

class FlowNetwork {
    Map<Integer, List<Edge>> edges = new HashMap<>();
    Map<Edge, Integer> flow = new HashMap<>();

    public FlowNetwork(List<Integer> vertices) {
        vertices.forEach(v -> this.edges.put(v, new ArrayList<>()));
    }

    public Integer maxFlow(Integer source, Integer sink) {
        List<Edge> path = null;
        while (! (path=findAugmentedPath(source,sink,new ArrayList<>())).isEmpty()) {
            int flow = path.stream().mapToInt(e -> e.capacity - this.flow.get(e)).min().getAsInt();
            path.forEach(e -> {
                this.flow.put(e, this.flow.get(e) + flow);
                this.flow.put(e.reverseEdge, this.flow.get(e.reverseEdge) - flow);
            });
        }
        return edges.get(source).stream().mapToInt(e -> flow.get(e)).sum();

    }

    List<Edge> findAugmentedPath(Integer source, Integer sink, List<Edge> pathSoFar) {
        if (source == sink) {
            return pathSoFar;
        }
        for (Edge neighbourEdge : this.edges.get(source)) {
            int residual = neighbourEdge.capacity - flow.get(neighbourEdge);
            if (residual > 0 && !pathSoFar.contains(neighbourEdge)) {
                pathSoFar.add(neighbourEdge);
                List<Edge> path = findAugmentedPath(neighbourEdge.b, sink, pathSoFar);
                if (!path.isEmpty()) {
                    return path;
                }
            }
        }
        return Collections.emptyList();
    }


    public void addEdge(int source, int sink, int capacity) {
        Edge edge = new Edge(source, sink, capacity);
        Edge reverseEdge = new Edge(sink, source, 0);

        edge.reverseEdge = reverseEdge;

        reverseEdge.reverseEdge = edge;

        this.edges.get(source).add(edge);
        this.edges.get(sink).add(reverseEdge);

        flow.put(edge, 0);
        flow.put(reverseEdge, 0);
    }
}


class Edge {

    Integer capacity;
    Edge reverseEdge;
    int b;
    int a;

    public Edge(Integer a, Integer b, Integer capacity) {
        this.a = a;
        this.b = b;
        this.capacity = capacity;
    }
}

问题是 java 算法输出 7，而不是测试用例中给出的示例的正确 23。代码运行时没有错误。在调试算法时，我看不到任何不当行为。我不确定它是怎么出错的。

我的问题是，谁能帮助我理解它是如何以及为什么出错的？

如果它有助于此 pdf 中提供示例图的可视化表示： http ://web.stanford.edu/class/cs97si/08-network-flow-problems.pdf

4

1 回答 1

0

我发现了问题...调用 findAugmentedPath 时，我没有创建 pathSoFar 的副本。哎呀！

List<Edge> findAugmentedPath(Integer source, Integer sink, List<Edge> pathSoFar) {
    if (source == sink) {
        return pathSoFar;
    }
    for (Edge neighbourEdge : this.edges.get(source)) {
        int residual = neighbourEdge.capacity - flow.get(neighbourEdge);
        if (residual > 0 && !pathSoFar.contains(neighbourEdge)) {
            List<Edge> pathSoFarCopy = new ArrayList<>(pathSoFar);
            pathSoFarCopy.add(neighbourEdge);
            List<Edge> path = findAugmentedPath(neighbourEdge.b, sink, pathSoFarCopy);
            if (!path.isEmpty()) {
                return path;
            }
        }
    }
    return Collections.emptyList();
}
于 2016-02-15T09:18:28.723 回答