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.List;
035
036import org.graphstream.graph.Edge;
037import org.graphstream.graph.Graph;
038import org.graphstream.graph.Node;
039
040/**
041 * Base for flow algorithms. Provides features to handle capacities and flows.
042 */
043public abstract class FlowAlgorithmBase implements FlowAlgorithm {
044        /**
045         * Graph used by the algorithm.
046         */
047        protected Graph flowGraph;
048        /**
049         * Edge count. Size of arrays (capacities and flows) is defined as twice
050         * this value.
051         */
052        protected int n;
053        /**
054         * Capacities of edges.
055         */
056        protected double[] capacities;
057        /**
058         * Current flows of edges.
059         */
060        protected double[] flows;
061        /**
062         * Id of the source.
063         */
064        protected String sourceId;
065        /**
066         * Id of the sink.
067         */
068        protected String sinkId;
069        /**
070         * Maximum flow computed by the algorithm.
071         */
072        protected double maximumFlow;
073
074        protected String capacityAttribute;
075
076        protected FlowAlgorithmBase() {
077                flowGraph = null;
078                capacityAttribute = null;
079        }
080
081        /**
082         * Check if arrays are large enought to support computation.
083         */
084        protected void checkArrays() {
085                n = flowGraph.getEdgeCount();
086
087                if (capacities == null || capacities.length < 2 * n) {
088                        capacities = new double[2 * n];
089                        flows = new double[2 * n];
090                }
091        }
092
093        /*
094         * (non-Javadoc)
095         * 
096         * @see org.graphstream.algorithm.flow.FlowAlgorithm#getFlowSourceId()
097         */
098        public String getFlowSourceId() {
099                return sourceId;
100        }
101
102        /*
103         * (non-Javadoc)
104         * 
105         * @see org.graphstream.algorithm.flow.FlowAlgorithm#getFlowSinkId()
106         */
107        public String getFlowSinkId() {
108                return sinkId;
109        }
110
111        /*
112         * (non-Javadoc)
113         * 
114         * @see
115         * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph)
116         */
117        public void init(Graph graph) {
118                flowGraph = graph;
119                checkArrays();
120        }
121
122        /*
123         * (non-Javadoc)
124         * 
125         * @see
126         * org.graphstream.algorithm.flow.FlowAlgorithm#init(org.graphstream.graph
127         * .Graph, java.lang.String, java.lang.String)
128         */
129        public void init(Graph g, String sourceId, String sinkId) {
130                init(g);
131
132                this.sourceId = sourceId;
133                this.sinkId = sinkId;
134        }
135
136        /*
137         * (non-Javadoc)
138         * 
139         * @see org.graphstream.algorithm.flow.FlowAlgorithm#getMaximumFlow()
140         */
141        public double getMaximumFlow() {
142                return maximumFlow;
143        }
144
145        /**
146         * Shortcut to {@link #getFlow(Node, Node)}.
147         * 
148         * @param uIndex
149         *            index of source
150         * @param vIndex
151         *            index of target
152         * @return flow of (u,v)
153         */
154        public double getFlow(int uIndex, int vIndex) {
155                Node u = flowGraph.getNode(uIndex);
156                Node v = flowGraph.getNode(vIndex);
157
158                return getFlow(u, v);
159        }
160
161        /**
162         * Shortcut to {@link #getFlow(Node, Node)}.
163         * 
164         * @param uId
165         *            id of source
166         * @param vId
167         *            id of target
168         * @return flow of (u,v)
169         */
170        public double getFlow(String uId, String vId) {
171                Node u = flowGraph.getNode(uId);
172                Node v = flowGraph.getNode(vId);
173
174                return getFlow(u, v);
175        }
176
177        /*
178         * (non-Javadoc)
179         * 
180         * @see
181         * org.graphstream.algorithm.flow.FlowAlgorithm#getFlow(org.graphstream.
182         * graph.Node, org.graphstream.graph.Node)
183         */
184        public double getFlow(Node u, Node v) {
185                Edge e = u.getEdgeBetween(v);
186
187                if (e.getSourceNode() == u)
188                        return flows[e.getIndex()];
189                else
190                        return flows[e.getIndex() + n];
191        }
192
193        /**
194         * Shortcut to {@link #setFlow(Node, Node, double)}.
195         * 
196         * @param uIndex
197         *            index of u
198         * @param vIndex
199         *            index of v
200         * @param flow
201         *            new float of (u,v)
202         */
203        public void setFlow(int uIndex, int vIndex, double flow) {
204                Node u = flowGraph.getNode(uIndex);
205                Node v = flowGraph.getNode(vIndex);
206
207                setFlow(u, v, flow);
208        }
209
210        /**
211         * Shortcut to {@link #setFlow(Node, Node, double)}.
212         * 
213         * @param uId
214         *            id of u
215         * @param vId
216         *            id of v
217         * @param flow
218         *            new float of (u,v)
219         */
220        public void setFlow(String uId, String vId, double flow) {
221                Node u = flowGraph.getNode(uId);
222                Node v = flowGraph.getNode(vId);
223
224                setFlow(u, v, flow);
225        }
226
227        /*
228         * (non-Javadoc)
229         * 
230         * @see
231         * org.graphstream.algorithm.flow.FlowAlgorithm#setFlow(org.graphstream.
232         * graph.Node, org.graphstream.graph.Node, double)
233         */
234        public void setFlow(Node u, Node v, double flow) {
235                Edge e = u.getEdgeBetween(v);
236
237                if (e.getSourceNode() == u)
238                        flows[e.getIndex()] = flow;
239                else
240                        flows[e.getIndex() + n] = flow;
241        }
242
243        /**
244         * Shortcut {@link #getCapacity(Node, Node)}.
245         * 
246         * @param uIndex
247         *            index of u
248         * @param vIndex
249         *            index of v
250         * @return capacity of (u,v).
251         */
252        public double getCapacity(int uIndex, int vIndex) {
253                Node u = flowGraph.getNode(uIndex);
254                Node v = flowGraph.getNode(vIndex);
255
256                return getCapacity(u, v);
257        }
258
259        /**
260         * Shortcut {@link #getCapacity(Node, Node)}.
261         * 
262         * @param uId
263         *            id of u
264         * @param vId
265         *            id of v
266         * @return capacity of (u,v).
267         */
268        public double getCapacity(String uId, String vId) {
269                Node u = flowGraph.getNode(uId);
270                Node v = flowGraph.getNode(vId);
271
272                return getCapacity(u, v);
273        }
274
275        /*
276         * (non-Javadoc)
277         * 
278         * @see
279         * org.graphstream.algorithm.flow.FlowAlgorithm#getCapacity(org.graphstream
280         * .graph.Node, org.graphstream.graph.Node)
281         */
282        public double getCapacity(Node u, Node v) {
283                Edge e = u.getEdgeBetween(v);
284
285                if (e == null)
286                        System.err.printf("no edge between %s and %s\n", u.getId(), v
287                                        .getId());
288
289                if (e.getSourceNode() == u)
290                        return capacities[e.getIndex()];
291                else
292                        return capacities[e.getIndex() + n];
293        }
294
295        /**
296         * Shortcut to {@link #setCapacity(Node, Node, double)}.
297         * 
298         * @param uIndex
299         *            index of u
300         * @param vIndex
301         *            index of v
302         * @param capacity
303         *            new capacity of (u,v)
304         */
305        public void setCapacity(int uIndex, int vIndex, double capacity) {
306                Node u = flowGraph.getNode(uIndex);
307                Node v = flowGraph.getNode(vIndex);
308
309                setCapacity(u, v, capacity);
310        }
311
312        /**
313         * Shortcut to {@link #setCapacity(Node, Node, double)}.
314         * 
315         * @param uId
316         *            id of u
317         * @param vId
318         *            id of v
319         * @param capacity
320         *            new capacity of (u,v)
321         */
322        public void setCapacity(String uId, String vId, double capacity) {
323                Node u = flowGraph.getNode(uId);
324                Node v = flowGraph.getNode(vId);
325
326                setCapacity(u, v, capacity);
327        }
328
329        /*
330         * (non-Javadoc)
331         * 
332         * @see
333         * org.graphstream.algorithm.flow.FlowAlgorithm#setCapacity(org.graphstream
334         * .graph.Node, org.graphstream.graph.Node, double)
335         */
336        public void setCapacity(Node u, Node v, double capacity) {
337                Edge e = u.getEdgeBetween(v);
338
339                if (e.getSourceNode() == u)
340                        capacities[e.getIndex()] = capacity;
341                else
342                        capacities[e.getIndex() + n] = capacity;
343        }
344
345        /*
346         * (non-Javadoc)
347         * 
348         * @see
349         * org.graphstream.algorithm.flow.FlowAlgorithm#setCapacityAttribute(java
350         * .lang.String)
351         */
352        public void setCapacityAttribute(String attribute) {
353                capacityAttribute = attribute;
354        }
355
356        /*
357         * (non-Javadoc)
358         * 
359         * @see org.graphstream.algorithm.flow.FlowAlgorithm#getCapacityAttribute()
360         */
361        public String getCapacityAttribute() {
362                return capacityAttribute;
363        }
364
365        public void setAllCapacities(double value) {
366                for (int i = 0; i < 2 * n; i++)
367                        capacities[i] = value;
368        }
369
370        /**
371         * Load capacities from edge attributes. Should be called between
372         * {@link #init(Graph, String, String)} and {@link #compute()}.
373         */
374        protected void loadCapacitiesFromAttribute() {
375                if (capacityAttribute == null)
376                        return;
377
378                Edge e;
379
380                for (int i = 0; i < n; i++) {
381                        capacities[i] = 0.0;
382                        capacities[i + n] = 0.0;
383
384                        e = flowGraph.getEdge(i);
385
386                        if (e.hasNumber(capacityAttribute)) {
387                                capacities[i] = e.getNumber(capacityAttribute);
388                        } else if (e.hasVector(capacityAttribute)) {
389                                List<? extends Number> capVect = flowGraph.getEdge(i)
390                                                .getVector(capacityAttribute);
391
392                                if (capVect.size() > 0)
393                                        capacities[i] = capVect.get(0).doubleValue();
394                                if (capVect.size() > 1)
395                                        capacities[i + n] = capVect.get(1).doubleValue();
396                        } else if (e.hasArray(capacityAttribute)) {
397                                Object[] capArray = e.getArray(capacityAttribute);
398
399                                if (capArray.length > 0)
400                                        capacities[i] = ((Number) capArray[0]).doubleValue();
401                                if (capArray.length > 1)
402                                        capacities[i + n] = ((Number) capArray[1]).doubleValue();
403                        } else if (e.hasAttribute(capacityAttribute))
404                                System.err.printf("unknown capacity type \"%s\"\n", e
405                                                .getAttribute(capacityAttribute).getClass());
406                }
407        }
408}