6
\$\begingroup\$

Solved the ford-fulkerson algorithm, which is too vast to explain it comprehensively here. Check Wikipedia for Ford-Fulkerson and Princeton lecture on Ford-Fulkerson.

Looking for code review, optimizations and best practices. Also I request you avoid mentioning renaming GraphFordFuklerson and unit tests not done in separate files as I am aware it's not good practices, but deliberately done for personal convenience.

/**
 * 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);
    }
}
\$\endgroup\$
2
\$\begingroup\$

Some small remarks:

  • I would change the NullPointerException to IllegalArgumentException when you check for null in the arguments of the method.
  • I would add an addNodes(T ...) convenience method.
  • addNode(T node) javadoc: "returns false if the node is not added". It only does so when the node is already in your Graph. Better to add that to the docs too.
  • What is the use of the synchronized block in the getPath method?
\$\endgroup\$
1
\$\begingroup\$

I don't think your implementation is bad, but I would have done things differently, so here is my implementation. I did not have much time to do it, so it is completely untested and probably not complete.

I am using Java 8, Google guava and I tried to make things as immutable as possible. I also made a bit of code multi-threaded (look for stream().parallel()). The only class that is mutable is Flow and if I had more time, I would look at making it immutable too. (I would have to check if it would impact the performance when the flow values are modified since a new Flow would have to be created each time we change one value in the flow.)

The Java 8 bits might be a bit hard to understand if you have never seen Java 8. However, I think you can look at my "high-level" design (Node, Edge, Graph, Path and Flow) and maybe get some inspiration from that. For example, I did not put the "consumed capacity" in the Edge class, but outside in class Flow.

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));
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.