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}