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}