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; 033 034import java.util.ArrayList; 035import java.util.List; 036 037import org.graphstream.graph.Edge; 038import org.graphstream.graph.Graph; 039import org.graphstream.graph.Node; 040import org.graphstream.graph.Path; 041 042/** 043 * Implementation of the Bellman-Ford algorithm that computes single-source 044 * shortest paths in a weighted digraph 045 * <p> 046 * The Bellman-Ford algorithm computes single-source shortest paths in a 047 * weighted digraph (where some of the edge weights may be negative). Dijkstra's 048 * algorithm accomplishes the same problem with a lower running time, but 049 * requires edge weights to be non-negative. Thus, Bellman-Ford is usually used 050 * only when there are negative edge weights (from the <a 051 * href="http://en.wikipedia.org/wiki/Bellman-Ford_algorithm">Wikipedia</a>). 052 * </p> 053 * 054 * <h2>Example</h2> 055 * <pre> 056 * import java.io.IOException; 057 * import java.io.StringReader; 058 * 059 * import org.graphstream.algorithm.BellmanFord; 060 * import org.graphstream.graph.Graph; 061 * import org.graphstream.graph.implementations.DefaultGraph; 062 * import org.graphstream.stream.file.FileSourceDGS; 063 * 064 * public class BellmanFordTest { 065 * 066 * // B-(1)-C 067 * // / \ 068 * // (1) (10) 069 * // / \ 070 * // A F 071 * // \ / 072 * // (1) (1) 073 * // \ / 074 * // D-(1)-E 075 * static String my_graph = 076 * "DGS004\n" 077 * + "my 0 0\n" 078 * + "an A \n" 079 * + "an B \n" 080 * + "an C \n" 081 * + "an D \n" 082 * + "an E \n" 083 * + "an F \n" 084 * + "ae AB A B weight:1 \n" 085 * + "ae AD A D weight:1 \n" 086 * + "ae BC B C weight:1 \n" 087 * + "ae CF C F weight:10 \n" 088 * + "ae DE D E weight:1 \n" 089 * + "ae EF E F weight:1 \n" 090 * ; 091 * 092 * public static void main(String[] args) throws IOException { 093 * Graph graph = new DefaultGraph("Bellman-Ford Test"); 094 * StringReader reader = new StringReader(my_graph); 095 * 096 * FileSourceDGS source = new FileSourceDGS(); 097 * source.addSink(graph); 098 * source.readAll(reader); 099 * 100 * BellmanFord bf = new BellmanFord("weight","A"); 101 * bf.init(graph); 102 * bf.compute(); 103 * 104 * System.out.println(bf.getShortestPath(graph.getNode("F"))); 105 * } 106 * } 107 * </pre> 108 * <h3>Warning</h3> 109 * <p> 110 * This Implementation is only a stub. For the moment only attributes located on 111 * the edges are supported. If you need more features, consider using the 112 * Dijkstra implementation. If you really need that algorithm, please contact 113 * the team members through the mailing list. 114 * </p> 115 * 116 * @reference Bellman, Richard "On a routing problem", Quarterly of Applied 117 * Mathematics 16: 87–90. 1958. 118 * 119 * @complexity O(VxE) time, where V and E are the number of vertices and edges 120 * respectively. 121 * 122 * @author Antoine Dutot 123 * @author Yoann Pigné 124 * 125 */ 126public class BellmanFord implements Algorithm { 127 128 /** 129 * The graph to be computed for shortest path. 130 */ 131 protected Graph graph; 132 133 /** 134 * ID of the source node. 135 */ 136 protected String source_id; 137 138 protected Node source; 139 140 /** 141 * object-level unique string that identifies tags of this instance on a 142 * graph. 143 */ 144 protected String identifier; 145 146 /** 147 * Name of attribute used to get weight of edges. 148 */ 149 protected String weightAttribute; 150 151 /** 152 * Build a new BellmanFord algorithm giving the name of the weight attribute 153 * for edges. 154 * 155 * @param attribute 156 * weight attribute of edges 157 */ 158 public BellmanFord(String attribute) { 159 this(attribute, null); 160 } 161 162 /** 163 * Same that {@link #BellmanFord(String)} but setting the id of the source 164 * node. 165 * 166 * @param attribute 167 * weight attribute of edges 168 * @param sourceNode 169 * id of the source node 170 */ 171 public BellmanFord(String attribute, String sourceNode) { 172 this.identifier = this.toString() + "/BellmanFord"; 173 this.source_id = sourceNode; 174 this.weightAttribute = attribute; 175 } 176 177 /** 178 * Set the id of the node used as source. 179 * 180 * @param nodeId 181 * id of the source node 182 */ 183 public void setSource(String nodeId) { 184 if((source_id == null || ! source_id.equals(nodeId)) && graph!=null){ 185 source = graph.getNode(nodeId); 186 } 187 this.source_id = nodeId; 188 } 189 190 /** 191 * Get the id of node used as source. 192 * 193 * @return id of the source node 194 */ 195 public String getSource() { 196 return source_id; 197 } 198 199 /** 200 * Constructs all the possible shortest paths from the source node to the 201 * destination (end). Warning: this construction is VERY HEAVY ! 202 * 203 * @param end 204 * The destination to which shortest paths are computed. 205 * @return a list of shortest paths given with 206 * {@link org.graphstream.graph.Path} objects. 207 */ 208 public List<Path> getPathSetShortestPaths(Node end) { 209 ArrayList<Path> paths = new ArrayList<Path>(); 210 pathSetShortestPath_facilitate(end, new Path(), paths); 211 return paths; 212 } 213 214 @SuppressWarnings("unchecked") 215 private void pathSetShortestPath_facilitate(Node current, Path path, 216 List<Path> paths) { 217 Node source = graph.getNode(this.source_id); 218 219 if (current != source) { 220 Node next = null; 221 ArrayList<? extends Edge> predecessors = (ArrayList<? extends Edge>) current 222 .getAttribute(identifier+".predecessors"); 223 while (current != source && predecessors.size() == 1) { 224 Edge e = predecessors.get(0); 225 next = e.getOpposite(current); 226 path.add(current, e); 227 current = next; 228 predecessors = (ArrayList<? extends Edge>) current 229 .getAttribute(identifier+".predecessors"); 230 } 231 if (current != source) { 232 for (Edge e : predecessors) { 233 Path p = path.getACopy(); 234 p.add(current, e); 235 pathSetShortestPath_facilitate(e.getOpposite(current), p, 236 paths); 237 238 } 239 } 240 } 241 if (current == source) { 242 paths.add(path); 243 } 244 } 245 246 /* 247 * (non-Javadoc) 248 * 249 * @see 250 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 251 */ 252 public void init(Graph graph) { 253 this.graph = graph; 254 if (getSource() != null){ 255 source = graph.getNode(getSource()); 256 } 257 } 258 259 260 261 /** 262 * Set the unique identifier for this instance. 263 * 264 * @see #getIdentifier() 265 * 266 * @param identifier 267 * the unique identifier to set 268 */ 269 public void setIdentifier(String identifier) { 270 this.identifier = identifier; 271 } 272 273 /** 274 * The unique identifier of this instance. Used to tag attributes in the graph. 275 * @return the unique identifier of this graph. 276 */ 277 public String getIdentifier() { 278 return this.identifier; 279 } 280 281 /** 282 * Returns the value of the shortest path between the source node and the 283 * given target according to the attribute specified in the constructor. If 284 * <code>target</code> is not in the same connected component as the source 285 * node, then the method returns <code>Double.POSITIVE_INFINITY</code> 286 * (Infinity). 287 * 288 * @param target 289 * The endpoint of the path to compute from the source node given 290 * in the constructor. 291 * @return A numerical value that represent the distance of the shortest 292 * path. 293 */ 294 public double getShortestPathValue(Node target) { 295 Double d = target.getAttribute(identifier+".distance"); 296 if (d != null) 297 return d; 298 return Double.POSITIVE_INFINITY; 299 } 300 301 /** 302 * Returns the shortest path between the source node and one given target. 303 * If multiple shortest paths exist, one of them is returned at random. 304 * 305 * @param target 306 * the target of the shortest path starting at the source node 307 * given in the constructor. 308 * @return A {@link org.graphstream.graph.Path} object that constrains the 309 * list of nodes and edges that constitute it. 310 */ 311 @SuppressWarnings("unchecked") 312 public Path getShortestPath(Node target) { 313 Path p = new Path(); 314 if (target == source ) { 315 return p; 316 } 317 boolean noPath = false; 318 Node v = target; 319 while (v != source && !noPath) { 320 ArrayList<? extends Edge> list = (ArrayList<? extends Edge>) v 321 .getAttribute(identifier+".predecessors"); 322 if (list == null) { 323 noPath = true; 324 } else { 325 Edge parentEdge = list.get(0); 326 p.add(v, parentEdge); 327 v = parentEdge.getOpposite(v); 328 } 329 } 330 return p; 331 } 332 333 334 335 336 337 338 /* 339 * (non-Javadoc) 340 * 341 * @see org.graphstream.algorithm.Algorithm#compute() 342 */ 343 @SuppressWarnings("unchecked") 344 public void compute() { 345 Node source = graph.getNode(this.source_id); 346 347 // Step 1: Initialize graph 348 349 350 for (Node n : graph) { 351 if (n == source) 352 n.addAttribute(identifier+".distance", 0.0); 353 else 354 n.addAttribute(identifier+".distance", Double.POSITIVE_INFINITY); 355 356 //n.addAttribute(identifier+".predecessors",(Object)null); 357 } 358 359 360 // Step 2: relax edges repeatedly 361 362 for (int i = 0; i < graph.getNodeCount(); i++) { 363 for (Edge e : graph.getEachEdge()) { 364 Node n0 = e.getNode0(); 365 Node n1 = e.getNode1(); 366 Double d0 = (Double) n0.getAttribute(identifier+".distance"); 367 Double d1 = (Double) n1.getAttribute(identifier+".distance"); 368 369 Double we = (Double) e.getAttribute(weightAttribute); 370 if (we == null) 371 throw new NumberFormatException( 372 "org.graphstream.algorithm.BellmanFord: Problem with attribute \"" 373 + weightAttribute + "\" on edge " + e); 374 375 if (d0 != null) { 376 if (d1 == null || d1 >= d0 + we) { 377 n1.addAttribute(identifier+".distance", d0 + we); 378 ArrayList<Edge> predecessors = (ArrayList<Edge>) n1 379 .getAttribute(identifier+".predecessors"); 380 381 if (d1 != null && d1 == d0 + we) { 382 if (predecessors == null) { 383 predecessors = new ArrayList<Edge>(); 384 } 385 } else { 386 predecessors = new ArrayList<Edge>(); 387 } 388 if (!predecessors.contains(e)) { 389 predecessors.add(e); 390 } 391 392 n1.addAttribute(identifier+".predecessors", 393 predecessors); 394 } 395 } 396 } 397 } 398 399 // Step 3: check for negative-weight cycles 400 401 for (Edge e : graph.getEachEdge()) { 402 Node n0 = e.getNode0(); 403 Node n1 = e.getNode1(); 404 Double d0 = (Double) n0.getAttribute(identifier+".distance"); 405 Double d1 = (Double) n1.getAttribute(identifier+".distance"); 406 407 Double we = (Double) e.getAttribute(weightAttribute); 408 409 if (we == null) { 410 throw new NumberFormatException( 411 String.format( 412 "%s: Problem with attribute \"%s\" on edge \"%s\"", 413 BellmanFord.class.getName(), weightAttribute, 414 e.getId())); 415 } 416 417 if (d1 > d0 + we) { 418 throw new NumberFormatException( 419 String.format( 420 "%s: Problem: negative weight, cycle detected on edge \"%s\"", 421 BellmanFord.class.getName(), e.getId())); 422 } 423 } 424 } 425}