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.Arrays;
035import java.util.LinkedList;
036
037import org.graphstream.graph.Edge;
038import org.graphstream.graph.Node;
039
040public class EdmondsKarpAlgorithm extends FordFulkersonAlgorithm {
041        /*
042         * (non-Javadoc)
043         * 
044         * @see
045         * org.graphstream.algorithm.flow.FordFulkersonAlgorithm#findPath(java.util
046         * .LinkedList, org.graphstream.graph.Node, org.graphstream.graph.Node)
047         */
048        protected double findPath(LinkedList<Node> path, Node source, Node target) {
049                LinkedList<Node> Q = new LinkedList<Node>();
050                Node u;
051                int[] P = new int[source.getGraph().getNodeCount()];
052                double[] M = new double[source.getGraph().getNodeCount()];
053                double r;
054
055                Arrays.fill(P, -1);
056                P[source.getIndex()] = -2;
057                M[source.getIndex()] = Double.MAX_VALUE;
058
059                Q.add(source);
060
061                while (Q.size() > 0) {
062                        u = Q.pop();
063
064                        for (int i = 0; i < u.getDegree(); i++) {
065                                Edge e = u.getEdge(i);
066                                Node v = e.getOpposite(u);
067
068                                r = getCapacity(u, v) - getFlow(u, v);
069
070                                if (r > 0 && P[v.getIndex()] == -1) {
071                                        P[v.getIndex()] = u.getIndex();
072                                        M[v.getIndex()] = Math.min(M[u.getIndex()], r);
073
074                                        if (v != target)
075                                                Q.push(v);
076                                        else {
077                                                u = target;
078
079                                                do {
080                                                        path.addFirst(u);
081                                                        u = flowGraph.getNode(P[u.getIndex()]);
082                                                } while (u != source);
083
084                                                path.addFirst(u);
085                                                return M[target.getIndex()];
086                                        }
087                                }
088                        }
089                }
090
091                return 0;
092        }
093}