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}