001/*
002 * Copyright 2006 - 2013
003 *     Stefan Balev     <stefan.balev@graphstream-project.org>
004 *     Julien Baudry    <julien.baudry@graphstream-project.org>
005 *     Antoine Dutot    <antoine.dutot@graphstream-project.org>
006 *     Yoann Pigné      <yoann.pigne@graphstream-project.org>
007 *     Guilhelm Savin   <guilhelm.savin@graphstream-project.org>
008 * 
009 * This file is part of GraphStream <http://graphstream-project.org>.
010 * 
011 * GraphStream is a library whose purpose is to handle static or dynamic
012 * graph, create them from scratch, file or any source and display them.
013 * 
014 * This program is free software distributed under the terms of two licenses, the
015 * CeCILL-C license that fits European law, and the GNU Lesser General Public
016 * License. You can  use, modify and/ or redistribute the software under the terms
017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
019 * the Free Software Foundation, either version 3 of the License, or (at your
020 * option) any later version.
021 * 
022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
024 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
025 * 
026 * You should have received a copy of the GNU Lesser General Public License
027 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
028 * 
029 * The fact that you are presently reading this means that you have had
030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
031 */
032package org.graphstream.algorithm.flow;
033
034import java.util.LinkedList;
035
036import org.graphstream.graph.Edge;
037import org.graphstream.graph.ElementNotFoundException;
038import org.graphstream.graph.Node;
039
040/**
041 * The Ford-Fulkerson algorithm to compute maximum flow.
042 * 
043 * @reference Ford, L. R.; Fulkerson, D. R. (1956).
044 *            "Maximal flow through a network". Canadian Journal of Mathematics
045 *            8: 399–404
046 * @complexity O(Ef), where E is the number of edges in the graph and f is the
047 *             maximum flow in the graph
048 */
049public class FordFulkersonAlgorithm extends FlowAlgorithmBase {
050        /*
051         * (non-Javadoc)
052         * 
053         * @see org.graphstream.algorithm.Algorithm#compute()
054         */
055        public void compute() {
056                Node source = flowGraph.getNode(sourceId);
057                Node sink = flowGraph.getNode(sinkId);
058
059                if (source == null)
060                        throw new ElementNotFoundException("node \"%s\"", sourceId);
061
062                if (sink == null)
063                        throw new ElementNotFoundException("node \"%s\"", sinkId);
064
065                checkArrays();
066                loadCapacitiesFromAttribute();
067
068                for (int i = 0; i < flowGraph.getEdgeCount(); i++) {
069                        Edge e = flowGraph.getEdge(i);
070
071                        setFlow(e.getNode0(), e.getNode1(), 0);
072                        setFlow(e.getNode1(), e.getNode0(), 0);
073                }
074
075                double minCf;
076                LinkedList<Node> path = new LinkedList<Node>();
077
078                while ((minCf = findPath(path, source, sink)) > 0) {
079                        for (int i = 1; i < path.size(); i++) {
080                                Node u = path.get(i - 1);
081                                Node v = path.get(i);
082
083                                setFlow(u, v, getFlow(u, v) + minCf);
084                                setFlow(v, u, getFlow(v, u) - minCf);
085                        }
086
087                        path.clear();
088                }
089
090                double flow = 0;
091
092                for (int i = 0; i < source.getDegree(); i++)
093                        flow += getFlow(source, source.getEdge(i).getOpposite(source));
094
095                maximumFlow = flow;
096        }
097
098        protected double findPath(LinkedList<Node> path, Node source, Node target) {
099                path.addLast(source);
100                
101                if (source == target)
102                        return Double.MAX_VALUE;
103
104                double minCf;
105
106                for (int i = 0; i < source.getDegree(); i++) {
107                        Edge e = source.getEdge(i);
108                        Node o = e.getOpposite(source);
109
110                        if (getCapacity(source, o) - getFlow(source, o) > 0
111                                        && !path.contains(o)) {
112                                if ((minCf = findPath(path, o, target)) > 0)
113                                        return Math.min(minCf,
114                                                        getCapacity(source, o) - getFlow(source, o));
115                        }
116                }
117                
118                path.removeLast();
119                return 0;
120        }
121}