Ford-Fulkerson算法

Question

解决了福特-富尔克森算法，该算法太庞大，无法在这里全面解释.检查福特-富尔克森维基百科和关于福特-富尔克森的普林斯顿讲座。

寻找代码评审、优化和最佳实践。此外，我还请您避免提及重命名GraphFordFuklerson和单元测试，因为我知道这不是很好的实践，而是为了个人方便，而不是在单独的文件中进行。

/**
 * A duplex edge is two edges(forward and reverse edge) combined into one.
 * In ford-fulkerson algo, we have a concept of forward edge and a reverse edge.
 * 
 * The forward edge is when the "from" node equals "from" node set by constructor
 * and 
 * "to" node equals "to" node set by constructor.
 * 
 * Duplex emulates both these edges by returning different values based on "to" and "from"
 * ie, it behaves as both "forward edge" and "backward egde" based on its input parameters.
 *
 * @param <T>
 */
final class DuplexEdge<T> {
    private final T from;
    private final T to;
    private final double capacity;
    private double consumedCapacity;

    public DuplexEdge (T from, T to, double capacity, double consumedCapacity) {
        if (from == null  || to == null) {
            throw new NullPointerException("Neither from nor to should be null.");
        }

        this.from = from;
        this.to = to;
        this.capacity = capacity;
        this.consumedCapacity = consumedCapacity;
    }


    /**
     * Returns the remaining capacity of that pipe/edge/channel.
     * From `from` and `to` a determination is made if its a forward edge of backward edge.
     * Depending on edge type the capacity is returned.
     * 
     * @param from      the from/source node   
     * @param to        the to node.
     * @return          the remaining capacity on determing if its a forward or reverse edge.
     */
    public double getCapacity(T from, T  to) {
        if (this.from.equals(from) && this.to.equals(to)) {
             return capacity - consumedCapacity;
        } 

        // indicates reverse flow.
        if (this.from.equals(to) && this.to.equals(from)) {
           return consumedCapacity;
        }
        throw new IllegalArgumentException("Both from: " + from + " and to : " + to + " should be part of this edge.");
    } 


    /**
     * Adjusts/modifies the remaining capacity of that pipe/edge/channel.
     * From `from` and `to` a determination is made if its a forward edge of backward edge.
     * Depending on edge type the capacity is adjusted.
     * 
     * @param from      the from/source node   
     * @param to        the to node.
     * @return          the remaining capacity on determing if its a forward or reverse edge.
     */
    public double adjustCapacity(T from, T  to, double consumedCapacity) {
        if (consumedCapacity > getCapacity(from, to)) {
            throw new IllegalArgumentException("The consumedCapacity " + consumedCapacity + " exceeds limit.");
        }

        if (this.from.equals(from) && this.to.equals(to)) {
            this.consumedCapacity = this.consumedCapacity + consumedCapacity;
        }

        // indicates reverse flow.
        if (this.from.equals(to) && this.to.equals(from)) {
            this.consumedCapacity = this.consumedCapacity - consumedCapacity;
        }

        throw new IllegalArgumentException("Both from: " + from + " and to : " + to + " should be part of this edge.");
    }
}

class GraphFordFuklerson<T> implements Iterable<T> {

    /* A map from nodes in the graph to sets of outgoing edges.  Each
     * set of edges is represented by a map from edges to doubles.
     */
    private final Map<T, Map<T, DuplexEdge<T>>> graph;

    public GraphFordFuklerson() {
        graph = new HashMap<T, Map<T, DuplexEdge<T>>>();
    }

    /**
     *  Adds a new node to the graph. If the node already exists then its a
     *  no-op.
     * 
     * @param node  Adds to a graph. If node is null then this is a no-op.
     * @return      true if node is added, false otherwise.
     */
    public boolean addNode(T node) {
        if (node == null) {
            throw new NullPointerException("The input node cannot be null.");
        }
        if (graph.containsKey(node)) return false;

        graph.put(node, new HashMap<T, DuplexEdge<T>>());
        return true;
    }

    /**
     * Given the source and destination node it would add an arc from source 
     * to destination node. If an arc already exists then the value would be 
     * updated the new value.
     *  
     * @param source                    the source node.
     * @param destination               the destination node.
     * @param capacity                    if length if 
     * @throws NullPointerException     if source or destination is null.
     * @throws NoSuchElementException   if either source of destination does not exists. 
     */
    public void addEdge (T source, T destination, double capacity) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        DuplexEdge<T> duplexEdge = new DuplexEdge<T>(source, destination, capacity, 0);

        /* A node would always be added so no point returning true or false */
        graph.get(source).put(destination, duplexEdge);
        graph.get(destination).put(source, duplexEdge);
    }

    /**
     * Removes an edge from the graph.
     * 
     * @param source        If the source node.
     * @param destination   If the destination node.
     * @throws NullPointerException     if either source or destination specified is null
     * @throws NoSuchElementException   if graph does not contain either source or destination
     */
    public void removeEdge (T source, T destination) {
        if (source == null || destination == null) {
            throw new NullPointerException("Source and Destination, both should be non-null.");
        }
        if (!graph.containsKey(source) || !graph.containsKey(destination)) {
            throw new NoSuchElementException("Source and Destination, both should be part of graph");
        }
        graph.get(source).remove(destination);
        graph.get(destination).remove(source);
    }

    /**
     * Given a node, returns the edges going outward that node,
     * as an immutable map.
     * 
     * @param node The node whose edges should be queried.
     * @return An immutable view of the edges leaving that node.
     * @throws NullPointerException   If input node is null.
     * @throws NoSuchElementException If node is not in graph.
     */
    public Map<T, DuplexEdge<T>> edgesFrom(T node) {
        if (node == null) {
            throw new NullPointerException("The node should not be null.");
        }
        Map<T, DuplexEdge<T>> edges = graph.get(node);
        if (edges == null) {
            throw new NoSuchElementException("Source node does not exist.");
        }
        return Collections.unmodifiableMap(edges);
    }

    /**
     * Returns the iterator that travels the nodes of a graph.
     * 
     * @return an iterator that travels the nodes of a graph.
     */
    @Override public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }
}

public final class FordFulkerson<T> {

    private final GraphFordFuklerson<T> graph;


    /**
     * Takes in a graph, which should not be modified by client.
     * However client should note that graph object is going to be changed by 
     * FordFulkerson algorithm.
     * 
     * @param graph the input graph.
     */
    public FordFulkerson (GraphFordFuklerson<T> graph) {
        if (graph == null) {
            throw new NullPointerException("The graph should not be null");
        }
        this.graph = graph;
    }


    private void validate(T source, T destination) {
        if (source == null || destination == null) {
            throw new NullPointerException("Neither source nor destination should be null");
        }

        if (source.equals(destination)) {
            throw new IllegalArgumentException("The source should not be the same as destination.");
        }
    }

    /**
     * Determines the max flow based on ford-fulkerson algorithm.
     * 
     * 
     * @param source            the source node.    
     * @param destination       the destination node
     * @return                  the max-flow
     */
    public double maxFlow(T source, T destination) {
        validate(source, destination);
        double max = 0;
        List<T> nodes = getPath(source, destination);
        while (nodes.size() > 0) {
            double maxCapacity = maxCapacity(nodes);
            max = max + maxCapacity;
            drainCapacity(nodes, maxCapacity);
            nodes = getPath(source, destination);
        }
        return max;
    }

    /**
     * Gets the path from source node to destination node, such that there is 
     * capacity > 0 at each edge from source to destination.
     * 
     * @param source        the source node
     * @param destination   the destination node
     * @return              the path from source to destination, 
     */
    private List<T> getPath(T source, T destination) {
        synchronized (graph) {
            final LinkedHashSet<T> path = new LinkedHashSet<T>();
            depthFind(source, destination, path);
            return new ArrayList<T>(path);
        }
    }

    private boolean depthFind(T current, T destination, LinkedHashSet<T> path) {
        path.add(current);

        if (current.equals(destination)) {
            return true;
        }

        for (Entry<T, DuplexEdge<T>> entry : graph.edgesFrom(current).entrySet()) {
            // if not cycle and if capacity exists.
            if (!path.contains(entry.getKey()) && entry.getValue().getCapacity(current, entry.getKey()) > 0) {
                // if end has been reached.
                if (depthFind(entry.getKey(), destination, path)) {
                    return true;
                }
            }
        }

        path.remove(current);
        return false;
    }

    /**
     * Returns the maximum capacity in the path.
     * Maximum capacity is the minimim capacity available on the path
     * from source to destination
     * 
     * @param nodes     the nodes that contibute a path
     * @return          the max capacity on the path.
     */ 
    private double maxCapacity(List<T> nodes) {
        double maxCapacity = Double.MAX_VALUE;
        for (int i = 0; i < nodes.size() - 1; i++) {
            T source = nodes.get(i);
            T destination = nodes.get(i + 1);

            DuplexEdge<T> duplexEdge = graph.edgesFrom(source).get(destination);
            double capacity = duplexEdge.getCapacity(source, destination);
            if (maxCapacity > capacity) { 
                maxCapacity = capacity;
            }
        }
        return maxCapacity;
    }

    /**
     * Reduces the capacity along the path from source to destination
     * 
     * @param nodes           the nodes that contribute the path
     * @param maxCapacity     the maximum capacity along the path.
     */ 
    private void drainCapacity (List<T> nodes, double maxCapacity) {
        for (int i = 0; i < nodes.size() - 1; i++) {
            T source = nodes.get(i);
            T destination = nodes.get(i + 1);

            DuplexEdge<T> duplexEdge = graph.edgesFrom(source).get(destination);
            duplexEdge.adjustCapacity(source, destination, maxCapacity);
        }
    }


    public static void main(String[] args) {

        final GraphFordFuklerson<String> graph = new GraphFordFuklerson<String>();
        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("D");
        graph.addNode("E");
        graph.addNode("F");
        graph.addNode("G");
        graph.addNode("H");

        graph.addEdge("A", "B", 10);
        graph.addEdge("A", "C", 5);
        graph.addEdge("A", "D", 15);
        graph.addEdge("B", "C", 4);
        graph.addEdge("C", "D", 4);
        graph.addEdge("B", "E", 9);
        graph.addEdge("B", "F", 15);
        graph.addEdge("C", "F", 8);
        graph.addEdge("D", "G", 16);
        graph.addEdge("E", "F", 15);
        graph.addEdge("F", "G", 15);
        graph.addEdge("G", "C",  6);
        graph.addEdge("E", "H", 10);
        graph.addEdge("F", "H", 10);
        graph.addEdge("G", "H", 10);

        FordFulkerson<String> ff = new FordFulkerson<String>(graph);
        double value = ff.maxFlow("A", "H");
        assertEquals(28.0, value, 0);
    }
}

Answer 1

我不认为您的实现是坏的，但我会做不同的事情，所以这里是我的实现。我没有太多的时间去做它，所以它是完全未经测试的，而且可能不完整。

我正在使用Java 8，谷歌番石榴和我试图使事情尽可能不变。我还做了一些多线程代码(查找stream().parallel())。唯一可变的类是Flow，如果我有更多的时间，我也会考虑使它不可变。(当流值被修改时，我必须检查它是否会影响性能，因为每次我们更改流中的一个值时，都必须创建一个新流。)

如果您从未见过Java 8，那么Java 8位可能有点难以理解。然而，我认为您可以看看我的“高级”设计(节点、边缘、图形、路径和流程)，并从中得到一些启示。例如，我没有将“消耗的容量”放在Edge类中，而是放在了类流的外部。

import com.google.common.collect.HashMultimap;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Multimap;

/**
 * Finds the maximum flow in a directed graph with capacity.
 * http://codereview.stackexchange.com/questions/45729
 */
public class FordFulkersonMaximumFlowFinder {

    public static Flow fordFulkersonFindMaximumFlow(Graph graph) {
        Collection<Path> paths = Path.findPathsDepthFirst(graph);
        Flow flow = Flow.createZeroFlow(graph);
        Optional<Path> onePathWithSlackCapacity;
        while ((onePathWithSlackCapacity = findOnePathWithSlackCapacity(paths, flow)).isPresent()) {
            // Note: there is some slight inefficiency here since it would be
            // possible to compute
            // the slack capacity amount while the check for slack capacity is
            // done.
            Stream<Edge> pathEdges = onePathWithSlackCapacity.get().getEdges().stream();
            DoubleStream slackCapacitiesPerEdge = pathEdges.mapToDouble(edge -> (edge.getCapacity() - flow.getFlow(edge)));
            double slackCapacity = slackCapacitiesPerEdge.min().getAsDouble();
            flow.subtractFlow(pathEdges, slackCapacity);
        }
        return flow;
    }

    private static Optional<Path> findOnePathWithSlackCapacity(Collection<Path> paths, Flow flow) {
        // Parallelize code when there are many paths.
        Stream<Path> pathsStream = paths.size() < 2000 ? paths.stream() : paths.stream().parallel();
        return pathsStream.filter(path -> doesPathHaveSlackCapacity(path, flow)).findFirst();
    }

    /**
     * @return true if each and every edge has a capacity which is strictly
     *         greater than the flow on that edge.
     */
    private static boolean doesPathHaveSlackCapacity(Path path, Flow flow) {
        // Note: this could be parallelize using stream().parallel(), but it
        // would slow things down unless the
        // paths are very long.
        return path.getEdges().stream().allMatch(edge -> edge.getCapacity() > flow.getFlow(edge));
    }

    /**
     * Immutable.
     */
    public static class Node {
        private final String name;

        /**
         * Immutable.
         */
        public Node(String name) {
            super();
            this.name = name;
        }

        public String getName() {
            return name;
        }

        @Override
        public String toString() {
            return "Node[" + name + "]";
        }
    }

    /**
     * Immutable.
     */
    public static class Edge {
        private final Node start;
        private final Node end;
        private final double capacity;

        public Edge(Node start, double capacity, Node end) {
            this.start = start;
            this.capacity = capacity;
            this.end = end;
        }

        public Node getStart() {
            return start;
        }

        public Node getEnd() {
            return end;
        }

        public double getCapacity() {
            return capacity;
        }
    }

    /**
     * Immutable.
     */
    public static class Graph {
        private final Multimap<Node, Edge> edges;
        private final Node startNode;
        private final Node endNode;

        public Graph(Node startNode, Node endNode, Collection<Edge> allEdges) {
            // TODO should check no incoming edge on startNode, no outgoing edge
            // on endNode and no cycles.
            // Also, check that it is connected, from start to end.
            this.startNode = startNode;
            this.endNode = endNode;
            edges = HashMultimap.create();
            {
                allEdges.stream().forEach(edge -> edges.put(edge.getStart(), edge));
            }
        }

        public Node getStartNode() {
            return startNode;
        }

        public Node getEndNode() {
            return endNode;
        }

        public Set<Node> getAllNodes() {
            return edges.keySet();
        }

        /**
         * @return empty collection if the node does not exist in the graph.
         */
        public Collection<Edge> getEdgesFrom(Node node) {
            return edges.get(node);
        }
    }

    /**
     * Immutable.
     */
    public static class Path {
        public static final Path EMPTY = new Path(ImmutableList.of());
        private ImmutableList<Edge> edges;

        public Path(List<Edge> edges) {
            this.edges = ImmutableList.copyOf(edges);
        }

        public ImmutableList<Edge> getEdges() {
            return edges;
        }

        public Path createNewPathAdding(Edge edge) {
            return new Path(ImmutableList.<Edge> builder().addAll(edges).add(edge).build());
        }

        public static Collection<Path> findPathsDepthFirst(Graph graph) {
            return findPathsDepthFirstRecursive(graph.getStartNode(), Path.EMPTY, graph);
        }

        public static Collection<Path> findPathsDepthFirstRecursive(Node currentNode, Path pathSoFar, Graph graph) {
            if (currentNode.equals(graph.getEndNode()))
                return Arrays.asList(pathSoFar);
            if (pathSoFar.getEdges().stream().anyMatch(edge -> currentNode.equals(edge.getStart())))
                throw new IllegalStateException("Holy Molly!  There's a cycle.");
            Stream<Path> paths = graph.getEdgesFrom(currentNode).stream().flatMap(edge -> {
                Node nextNode = edge.getEnd();
                Path nextPathSoFar = pathSoFar.createNewPathAdding(edge);
                return findPathsDepthFirstRecursive(nextNode, nextPathSoFar, graph).stream();
            });
            return paths.collect(Collectors.toList());
        }
    }

    /**
     * Mutable.
     */
    // TODO make immutable? Subtract would take a collection of edges and one
    // value. Is Guava ImmutableMap efficient enough for creating new
    // ImmutableMaps when subtracting?
    public static class Flow {
        private final Map<Edge, Double> edgeFlows = new HashMap<>();

        private Flow() {
        }

        public static Flow createZeroFlow(Graph graph) {
            Flow zeroFlow = new Flow();
            {
                graph.edges.values().stream().forEach(edge -> zeroFlow.edgeFlows.put(edge, 0.0));
            }
            return zeroFlow;
        }

        public double getFlow(Edge edge) {
            return edgeFlows.get(edge);
        }

        public void setFlow(Edge edge, double flowValue) {
            edgeFlows.put(edge, flowValue);
        }

        public void subtractFlow(Stream<Edge> pathEdges, double amountToSubtract) {
            pathEdges.forEach(edge -> edgeFlows.put(edge, edgeFlows.get(edge) - amountToSubtract));
        }
    }
}