001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.util.graphs.traversal; 018 019import java.util.ArrayDeque; 020import java.util.Collection; 021import java.util.Collections; 022import java.util.Deque; 023import java.util.Iterator; 024import java.util.Queue; 025 026import net.automatalib.commons.util.Holder; 027import net.automatalib.commons.util.Triple; 028import net.automatalib.graphs.IndefiniteGraph; 029import net.automatalib.util.traversal.TraversalOrder; 030 031 032public abstract class GraphTraversal { 033 034 035 public static <N,E,D> 036 boolean traverse(TraversalOrder order, 037 IndefiniteGraph<N,E> graph, 038 int limit, 039 Collection<? extends N> initialNodes, 040 GraphTraversalVisitor<N, E, D> vis) { 041 switch(order) { 042 case BREADTH_FIRST: 043 return breadthFirst(graph, limit, initialNodes, vis); 044 case DEPTH_FIRST: 045 return depthFirst(graph, limit, initialNodes, vis); 046 default: 047 throw new IllegalArgumentException("Unknown traversal order " + order); 048 } 049 } 050 051 public static <N,E,D> 052 boolean traverse(TraversalOrder order, 053 IndefiniteGraph<N,E> graph, 054 int limit, 055 N initialNode, 056 GraphTraversalVisitor<N,E,D> vis) { 057 return traverse(order, graph, limit, Collections.singleton(initialNode), vis); 058 } 059 060 public static <N,E,D> 061 boolean traverse(TraversalOrder order, 062 IndefiniteGraph<N,E> graph, 063 N initialNode, 064 GraphTraversalVisitor<N,E,D> vis) { 065 return traverse(order, graph, -1, Collections.singleton(initialNode), vis); 066 } 067 068 public static <N,E,D> 069 boolean traverse(TraversalOrder order, 070 IndefiniteGraph<N,E> graph, 071 Collection<? extends N> initialNodes, 072 GraphTraversalVisitor<N,E,D> vis) { 073 return traverse(order, graph, -1, initialNodes, vis); 074 } 075 076 077 public static <N,E,D> 078 boolean breadthFirst(IndefiniteGraph<N, E> graph, int limit, Collection<? extends N> initialNodes, GraphTraversalVisitor<N, E, D> vis) { 079 080 Queue<BFRecord<N,D>> bfsQueue = new ArrayDeque<BFRecord<N,D>>(); 081 082 // setting the following to false means that the traversal had to be aborted 083 // due to reaching the limit 084 boolean complete = true; 085 int nodeCount = 0; 086 087 Holder<D> dataHolder = new Holder<>(); 088 089 for(N init : initialNodes) { 090 dataHolder.value = null; 091 GraphTraversalAction act = vis.processInitial(init, dataHolder); 092 093 switch(act) { 094 case IGNORE: 095 case ABORT_NODE: 096 continue; 097 case ABORT_TRAVERSAL: 098 return complete; 099 case EXPLORE: 100 if(nodeCount != limit) { // not equals will always be true for negative limit values 101 bfsQueue.offer(new BFRecord<N,D>(init, dataHolder.value)); 102 nodeCount++; 103 } 104 else 105 complete = false; 106 break; 107 } 108 } 109 110 111bfs_loop: 112 while(!bfsQueue.isEmpty()) { 113 BFRecord<N,D> current = bfsQueue.poll(); 114 115 N currNode = current.node; 116 D currData = current.data; 117 118 if(!vis.startExploration(currNode, currData)) 119 continue; 120 121 Collection<E> edges = graph.getOutgoingEdges(currNode); 122 123 if(edges == null) 124 continue; 125 126 for(E edge : edges) { 127 128 N tgtNode = graph.getTarget(edge); 129 130 dataHolder.value = null; 131 GraphTraversalAction act = vis.processEdge(currNode, currData, edge, tgtNode, dataHolder); 132 133 134 switch(act) { 135 case IGNORE: 136 continue; 137 case ABORT_NODE: 138 continue bfs_loop; 139 case ABORT_TRAVERSAL: 140 return complete; 141 case EXPLORE: 142 if(nodeCount != limit) { // not equals will always be true for negative limit values 143 bfsQueue.offer(new BFRecord<N,D>(tgtNode, dataHolder.value)); 144 nodeCount++; 145 } 146 else 147 complete = false; 148 } 149 } 150 151 vis.finishExploration(currNode, currData); 152 } 153 154 return complete; 155 } 156 157 public static <N,E,D> 158 boolean breadthFirst(IndefiniteGraph<N,E> graph, int limit, N initialNode, GraphTraversalVisitor<N, E, D> visitor) { 159 return breadthFirst(graph, limit, Collections.singleton(initialNode), visitor); 160 } 161 162 public static <N,E,D> 163 boolean breadthFirst(IndefiniteGraph<N,E> graph, Collection<? extends N> initialNodes, GraphTraversalVisitor<N, E, D> visitor) { 164 return breadthFirst(graph, -1, initialNodes, visitor); 165 } 166 167 public static <N,E,D> 168 boolean breadthFirst(IndefiniteGraph<N,E> graph, N initialNode, GraphTraversalVisitor<N, E, D> visitor) { 169 return breadthFirst(graph, -1, Collections.singleton(initialNode), visitor); 170 } 171 172 173 174 175 public static <N,E,D> 176 boolean depthFirst(IndefiniteGraph<N,E> graph, int limit, Collection<? extends N> initialNodes, 177 GraphTraversalVisitor<N, E, D> vis) { 178 179 // setting the following to false means that the traversal had to be aborted 180 // due to reaching the limit 181 boolean complete = true; 182 183 int nodeCount = 0; 184 185 186 Deque<DFRecord<N,E,D>> dfsStack 187 = new ArrayDeque<DFRecord<N,E,D>>(); 188 189 Holder<D> dataHolder = new Holder<>(); 190 191 for(N init : initialNodes) { 192 193 dataHolder.value = null; 194 GraphTraversalAction act = vis.processInitial(init, dataHolder); 195 196 switch(act) { 197 case IGNORE: 198 case ABORT_NODE: 199 continue; 200 case ABORT_TRAVERSAL: 201 return complete; 202 case EXPLORE: 203 if(nodeCount != limit) { 204 dfsStack.push(new DFRecord<N,E,D>(init, dataHolder.value)); 205 nodeCount++; 206 } 207 else 208 complete = false; 209 break; 210 } 211 } 212 213 214 while(!dfsStack.isEmpty()) { 215 DFRecord<N,E,D> current = dfsStack.peek(); 216 217 N currNode = current.node; 218 D currData = current.data; 219 220 if(current.start(graph)) { 221 if(!vis.startExploration(currNode, currData)) { 222 dfsStack.pop(); 223 continue; 224 } 225 } 226 227 Triple<E,N,D> lastEdge = current.getLastEdge(); 228 if(lastEdge != null) { 229 vis.backtrackEdge(currNode, currData, lastEdge.getFirst(), 230 lastEdge.getSecond(), lastEdge.getThird()); 231 } 232 233 if(!current.hasNextEdge()) { 234 dfsStack.pop(); 235 vis.finishExploration(currNode, currData); 236 continue; 237 } 238 239 E edge = current.nextEdge(); 240 241 N tgt = graph.getTarget(edge); 242 243 GraphTraversalAction act = vis.processEdge(currNode, currData, edge, tgt, dataHolder); 244 245 switch(act) { 246 case IGNORE: 247 continue; 248 case ABORT_NODE: 249 dfsStack.pop(); 250 continue; 251 case ABORT_TRAVERSAL: 252 return complete; 253 case EXPLORE: 254 if(nodeCount != limit) { 255 D data = dataHolder.value; 256 current.setLastEdge(edge, tgt, data); 257 dfsStack.push(new DFRecord<N,E,D>(tgt, data)); 258 nodeCount++; 259 } 260 else 261 complete = false; 262 break; 263 } 264 } 265 266 return complete; 267 } 268 269 public static <N,E,D> 270 boolean depthFirst(IndefiniteGraph<N,E> graph, N initNode, 271 GraphTraversalVisitor<N, E, D> vis) { 272 return depthFirst(graph, -1, initNode, vis); 273 } 274 275 public static <N,E,D> 276 boolean depthFirst(IndefiniteGraph<N,E> graph, int limit, N initNode, 277 GraphTraversalVisitor<N, E, D> vis) { 278 return depthFirst(graph, Collections.singleton(initNode), vis); 279 } 280 281 public static <N,E,D> 282 boolean depthFirst(IndefiniteGraph<N,E> graph, Collection<? extends N> initialNodes, 283 GraphTraversalVisitor<N, E, D> vis) { 284 return depthFirst(graph, -1, initialNodes, vis); 285 } 286 287 288 289 290 291 public static <N,E,D> 292 boolean dfs(IndefiniteGraph<N, E> graph, int limit, Collection<? extends N> initialNodes, DFSVisitor<? super N, ? super E, D> visitor) { 293 GraphTraversalVisitor<N, E, DFSData<D>> traversalVisitor 294 = new DFSTraversalVisitor<N, E, D>(graph, visitor); 295 return depthFirst(graph, limit, initialNodes, traversalVisitor); 296 } 297 298 public static <N,E,D> 299 boolean dfs(IndefiniteGraph<N, E> graph, N initialNode, DFSVisitor<? super N, ? super E, D> visitor) { 300 return dfs(graph, -1, Collections.singleton(initialNode), visitor); 301 } 302 303 public static <N,E,D> 304 boolean dfs(IndefiniteGraph<N, E> graph, Collection<? extends N> initialNodes, DFSVisitor<? super N, ? super E, D> visitor) { 305 return dfs(graph, -1, initialNodes, visitor); 306 } 307 308 309 public static <N,E> Iterator<N> bfIterator(IndefiniteGraph<N,E> graph, Collection<? extends N> start) { 310 return new BreadthFirstIterator<>(graph, start); 311 } 312 313 public static <N,E> Iterable<N> breadthFirstOrder( 314 final IndefiniteGraph<N,E> graph, 315 final Collection<? extends N> start) { 316 317 return new Iterable<N>() { 318 @Override 319 public Iterator<N> iterator() { 320 return bfIterator(graph, start); 321 } 322 }; 323 } 324 325 public static <N,E> Iterator<N> dfIterator(IndefiniteGraph<N,E> graph, Collection<? extends N> start) { 326 return new DepthFirstIterator<>(graph, start); 327 } 328 329 public static <N,E> Iterable<N> depthFirstOrder( 330 final IndefiniteGraph<N,E> graph, 331 final Collection<? extends N> start) { 332 333 return new Iterable<N>() { 334 @Override 335 public Iterator<N> iterator() { 336 return dfIterator(graph, start); 337 } 338 }; 339 } 340 341 private GraphTraversal() {} // prevent inheritance 342 343}