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.networksimplex; 033 034import java.util.HashMap; 035import java.util.Iterator; 036import java.util.Map; 037import java.util.NoSuchElementException; 038import java.util.Stack; 039 040import org.graphstream.algorithm.Dijkstra; 041import org.graphstream.graph.Edge; 042import org.graphstream.graph.Graph; 043import org.graphstream.graph.Node; 044import org.graphstream.graph.Path; 045 046public class DynamicOneToAllShortestPath extends NetworkSimplex { 047 protected String sourceId; 048 049 public DynamicOneToAllShortestPath(String costName) { 050 super(null, null, costName); 051 } 052 053 public String getSource() { 054 return sourceId; 055 } 056 057 public void setSource(String sourceId) { 058 this.sourceId = sourceId; 059 if (nodes != null) 060 for (NSNode node : nodes.values()) 061 changeSupply(node, node.id.equals(sourceId) ? nodes.size() - 1 062 : -1); 063 } 064 065 @Override 066 protected void cloneGraph() { 067 super.cloneGraph(); 068 for (NSNode node : nodes.values()) 069 node.supply = node.id.equals(sourceId) ? nodes.size() - 1 : -1; 070 } 071 072 /** 073 * NS is much slower than Dijkstra when starting from a big graph. 074 * The idea is to call Dijkstra and then to construct the initial BFS from it. 075 * This method should be called just after {@link #createInitialBFS()}. 076 */ 077 protected void bfsFromDijkstra() { 078 // first check if we can apply Dijkstra 079 if (nodes.get(sourceId) == null) 080 return; 081 for (NSArc arc : arcs.values()) 082 if (arc.cost.isNegative()) 083 return; 084 085 // instantiate and compute Dijkstra 086 Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.EDGE, null, costName); 087 dijkstra.init(graph); 088 dijkstra.setSource(graph.getNode(sourceId)); 089 dijkstra.compute(); 090 091 // init 092 Map<NSNode, NSNode> last = new HashMap<NSNode, NSNode>(4 * (nodes.size() + 1) / 3 + 1); 093 last.put(root, root); 094 root.thread = root; 095 for (NSNode node : nodes.values()) { 096 last.put(node, node); 097 node.artificialArc.status = ArcStatus.NONBASIC_LOWER; 098 node.artificialArc.flow = 0; 099 node.thread = node; 100 } 101 102 // restore parent and thread 103 for (NSNode node : nodes.values()) { 104 Node gNode = graph.getNode(node.id); 105 Node gParent = dijkstra.getParent(gNode); 106 NSNode parent = gParent == null ? root : nodes.get(gParent.getId()); 107 node.parent = parent; 108 NSArc arc = node.artificialArc; 109 if (gParent != null) { 110 Edge gEdge = dijkstra.getEdgeFromParent(gNode); 111 if (gEdge.getSourceNode() == gParent) 112 arc = arcs.get(gEdge.getId()); 113 else 114 arc = arcs.get(PREFIX + "REVERSE_" + gEdge.getId()); 115 } 116 node.arcToParent = arc; 117 arc.status = ArcStatus.BASIC; 118 nonBasicArcs.remove(arc); 119 NSNode nodeLast = last.get(node); 120 nodeLast.thread = parent.thread; 121 parent.thread = node; 122 for (NSNode x = parent; last.get(x) == parent; x = x.parent) 123 last.put(x, nodeLast); 124 } 125 last.clear(); 126 dijkstra.clear(); 127 128 // compute depths, potentials, flows and objective value 129 for (NSNode node = root.thread; node != root; node = node.thread) { 130 node.depth = node.parent.depth + 1; 131 node.computePotential(); 132 for (NSNode x = node; x != root; x = x.parent) 133 x.arcToParent.flow++; 134 } 135 NSArc arc = nodes.get(sourceId).arcToParent; 136 arc.flow = nodes.size() - arc.flow; 137 138 objectiveValue.set(0); 139 for (NSNode node = root.thread; node != root; node = node.thread) 140 objectiveValue.plusTimes(node.arcToParent.flow, node.arcToParent.cost); 141 } 142 143 144 145 @Override 146 public void init(Graph graph) { 147 // Do not call super.init(graph), make BFS from Dijkstra before start listening 148 this.graph = graph; 149 cloneGraph(); 150 createInitialBFS(); 151 bfsFromDijkstra(); 152 graph.addSink(this); 153 } 154 155 @Override 156 public void nodeAdded(String sourceId, long timeId, String nodeId) { 157 NSNode node = new NSNode(graph.getNode(nodeId)); 158 if (nodeId.equals(this.sourceId)) { 159 node.supply = nodes.size(); 160 addNode(node); 161 } else { 162 node.supply = -1; 163 addNode(node); 164 NSNode source = nodes.get(this.sourceId); 165 if (source != null) 166 changeSupply(source, nodes.size() - 1); 167 } 168 } 169 170 @Override 171 public void nodeRemoved(String sourceId, long timeId, String nodeId) { 172 removeNode(nodes.get(nodeId)); 173 if (!nodeId.equals(this.sourceId)) { 174 NSNode source = nodes.get(this.sourceId); 175 if (source != null) 176 changeSupply(source, nodes.size() - 1); 177 } 178 } 179 180 // Iterators 181 182 protected class NodeIterator<T extends Node> implements Iterator<T> { 183 protected NSNode nextNode; 184 185 protected NodeIterator(NSNode target) { 186 if (target.id.equals(sourceId) || target.parent != root) 187 nextNode = target; 188 else 189 nextNode = root; 190 } 191 192 public boolean hasNext() { 193 return nextNode != root; 194 } 195 196 public T next() { 197 if (nextNode == root) 198 throw new NoSuchElementException(); 199 T node = graph.getNode(nextNode.id); 200 nextNode = nextNode.parent; 201 return node; 202 } 203 204 public void remove() { 205 throw new UnsupportedOperationException( 206 "This iterator does not support remove"); 207 } 208 } 209 210 protected class EdgeIterator<T extends Edge> implements Iterator<T> { 211 protected NSNode nextNode; 212 213 protected EdgeIterator(NSNode target) { 214 nextNode = target; 215 } 216 217 public boolean hasNext() { 218 return nextNode.parent != root; 219 } 220 221 public T next() { 222 if (nextNode.parent == root) 223 throw new NoSuchElementException(); 224 T edge = graph.getEdge(nextNode.arcToParent.getOriginalId()); 225 nextNode = nextNode.parent; 226 return edge; 227 } 228 229 public void remove() { 230 throw new UnsupportedOperationException( 231 "This iterator does not support remove"); 232 } 233 } 234 235 public long getPathLength(Node node) { 236 NSNode nsNode = nodes.get(node.getId()); 237 if (nsNode.id.equals(sourceId)) 238 return 0; 239 if (nsNode.parent == root) 240 return Long.MAX_VALUE; 241 return -nsNode.potential.small; 242 } 243 244 /** 245 * This iterator traverses the nodes on the shortest path from the source 246 * node to a given target node. The nodes are traversed in reverse order: 247 * the target node first, then its predecessor, ... and finally the source 248 * node. If there is no path from the source to the target, no nodes are 249 * traversed. This iterator does not support 250 * {@link java.util.Iterator#remove()}. 251 * 252 * @param target 253 * a node 254 * @return an iterator on the nodes of the shortest path from the source to 255 * the target 256 * @see #getPathNodes(Node) 257 * @complexity Each call of {@link java.util.Iterator#next()} of this 258 * iterator takes O(1) time 259 */ 260 public <T extends Node> Iterator<T> getPathNodesIterator(Node target) { 261 return new NodeIterator<T>(nodes.get(target.getId())); 262 } 263 264 /** 265 * An iterable view of the nodes on the shortest path from the source node 266 * to a given target node. Uses {@link #getPathNodesIterator(Node)}. 267 * 268 * @param target 269 * a node 270 * @return an iterable view of the nodes on the shortest path from the 271 * source to the target 272 * @see #getPathNodesIterator(Node) 273 */ 274 public <T extends Node> Iterable<T> getPathNodes(final Node target) { 275 return new Iterable<T>() { 276 public Iterator<T> iterator() { 277 return getPathNodesIterator(target); 278 } 279 }; 280 } 281 282 /** 283 * This iterator traverses the edges on the shortest path from the source 284 * node to a given target node. The edges are traversed in reverse order: 285 * first the edge between the target and its predecessor, ... and finally 286 * the edge between the source end its successor. If there is no path from 287 * the source to the target or if he source and the target are the same 288 * node, no edges are traversed. This iterator does not support 289 * {@link java.util.Iterator#remove()}. 290 * 291 * @param target 292 * a node 293 * @return an iterator on the edges of the shortest path from the source to 294 * the target 295 * @see #getPathEdges(Node) 296 * @complexity Each call of {@link java.util.Iterator#next()} of this 297 * iterator takes O(1) time 298 */ 299 public <T extends Edge> Iterator<T> getPathEdgesIterator(Node target) { 300 return new EdgeIterator<T>(nodes.get(target.getId())); 301 } 302 303 /** 304 * An iterable view of the edges on the shortest path from the source node 305 * to a given target node. Uses {@link #getPathEdgesIterator(Node)}. 306 * 307 * @param target 308 * a node 309 * @return an iterable view of the edges on the shortest path from the 310 * source to the target 311 * @see #getPathEdgesIterator(Node) 312 */ 313 public <T extends Edge> Iterable<T> getPathEdges(final Node target) { 314 return new Iterable<T>() { 315 public Iterator<T> iterator() { 316 return getPathEdgesIterator(target); 317 } 318 319 }; 320 } 321 322 /** 323 * Returns the shortest path from the source node to a given target node. If 324 * there is no path from the source to the target returns an empty path. 325 * This method constructs a {@link org.graphstream.graph.Path} object which 326 * consumes heap memory proportional to the number of edges and nodes in the 327 * path. When possible, prefer using {@link #getPathNodes(Node)} and 328 * {@link #getPathEdges(Node)} which are more memory- and time-efficient. 329 * 330 * @param target 331 * a node 332 * @return the shortest path from the source to the target 333 * @complexity O(<em>p</em>) where <em>p</em> is the number of the nodes in 334 * the path 335 */ 336 public Path getPath(Node target) { 337 Path path = new Path(); 338 if (getPathLength(target) == Long.MAX_VALUE) 339 return path; 340 Stack<Edge> stack = new Stack<Edge>(); 341 for (Edge e : getPathEdges(target)) 342 stack.push(e); 343 path.setRoot(graph.getNode(sourceId)); 344 while (!stack.isEmpty()) 345 path.add(stack.pop()); 346 return path; 347 } 348}