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.ts.traversal; 018 019import java.util.ArrayDeque; 020import java.util.Collection; 021import java.util.Deque; 022 023import net.automatalib.commons.util.Holder; 024import net.automatalib.ts.TransitionSystem; 025import net.automatalib.util.traversal.TraversalOrder; 026 027 028/** 029 * 030 * @author Malte Isberner <malte.isberner@gmail.com> 031 * 032 */ 033public abstract class TSTraversal { 034 035 public static final int NO_LIMIT = -1; 036 037 038 039 public static <S,I,T,D> 040 boolean depthFirst(TransitionSystem<S, I, T> ts, 041 int limit, 042 Collection<? extends I> inputs, 043 TSTraversalVisitor<S, I, T, D> vis) { 044 Deque<DFRecord<S,I,T,D>> dfsStack = new ArrayDeque<DFRecord<S,I,T,D>>(); 045 046 Holder<D> dataHolder = new Holder<>(); 047 048 // setting the following to false means that the traversal had to be aborted 049 // due to reaching the limit 050 boolean complete = true; 051 int stateCount = 0; 052 053 for(S initS : ts.getInitialStates()) { 054 dataHolder.value = null; 055 TSTraversalAction act = vis.processInitial(initS, dataHolder); 056 switch(act) { 057 case ABORT_INPUT: 058 case ABORT_STATE: 059 case IGNORE: 060 continue; 061 case ABORT_TRAVERSAL: 062 return complete; 063 case EXPLORE: 064 if(stateCount != limit) { 065 dfsStack.push(new DFRecord<S, I, T, D>(initS, inputs, dataHolder.value)); 066 stateCount++; 067 } 068 else 069 complete = false; 070 break; 071 } 072 } 073 074 while(!dfsStack.isEmpty()) { 075 DFRecord<S,I,T,D> current = dfsStack.peek(); 076 077 S source = current.state; 078 D data = current.data; 079 080 if(current.start(ts)) { 081 if(!vis.startExploration(source, data)) { 082 dfsStack.pop(); 083 continue; 084 } 085 } 086 087 if(!current.hasNextTransition()) { 088 dfsStack.pop(); 089 continue; 090 } 091 092 I input = current.input(); 093 T trans = current.transition(); 094 095 S succ = ts.getSuccessor(trans); 096 dataHolder.value = null; 097 TSTraversalAction act = vis.processTransition(source, data, input, trans, succ, dataHolder); 098 099 switch(act) { 100 case ABORT_INPUT: 101 current.advanceInput(ts); 102 break; 103 case ABORT_STATE: 104 dfsStack.pop(); 105 break; 106 case ABORT_TRAVERSAL: 107 return complete; 108 case IGNORE: 109 current.advance(ts); 110 break; 111 case EXPLORE: 112 if(stateCount != limit) { 113 dfsStack.push(new DFRecord<S,I,T,D>(succ, inputs, dataHolder.value)); 114 stateCount++; 115 } 116 else 117 complete = false; 118 break; 119 } 120 } 121 122 return complete; 123 } 124 125 public static <S,I,T,D> 126 boolean depthFirst(TransitionSystem<S, I, T> ts, 127 Collection<? extends I> inputs, 128 TSTraversalVisitor<S, I, T, D> vis) { 129 return depthFirst(ts, NO_LIMIT, inputs, vis); 130 } 131 132 133 /** 134 * Traverses the given transition system in a breadth-first fashion. 135 * The traversal is steered by the specified visitor. 136 * 137 * @param ts the transition system. 138 * @param inputs the input alphabet. 139 * @param vis the visitor. 140 */ 141 public static <S,I,T,D> 142 boolean breadthFirst(TransitionSystem<S, I, T> ts, 143 int limit, 144 Collection<? extends I> inputs, 145 TSTraversalVisitor<S, I, T, D> vis) { 146 Deque<BFSRecord<S,D>> bfsQueue = new ArrayDeque<BFSRecord<S,D>>(); 147 148 // setting the following to false means that the traversal had to be aborted 149 // due to reaching the limit 150 boolean complete = true; 151 int stateCount = 0; 152 153 Holder<D> dataHolder = new Holder<>(); 154 155 for(S initS : ts.getInitialStates()) { 156 dataHolder.value = null; 157 TSTraversalAction act = vis.processInitial(initS, dataHolder); 158 switch(act) { 159 case ABORT_TRAVERSAL: 160 return complete; 161 case EXPLORE: 162 if(stateCount != limit) { 163 bfsQueue.offer(new BFSRecord<S,D>(initS, dataHolder.value)); 164 stateCount++; 165 } 166 else 167 complete = false; 168 break; 169 case ABORT_INPUT: 170 case ABORT_STATE: 171 case IGNORE: 172 } 173 } 174 175 while(!bfsQueue.isEmpty()) { 176 BFSRecord<S,D> current = bfsQueue.poll(); 177 178 S state = current.state; 179 D data = current.data; 180 181 if(!vis.startExploration(state, data)) 182 continue; 183 184inputs_loop: 185 for(I input : inputs) { 186 Collection<T> transitions = ts.getTransitions(state, input); 187 188 if(transitions == null) 189 continue; 190 191 for(T trans : transitions) { 192 S succ = ts.getSuccessor(trans); 193 194 dataHolder.value = null; 195 TSTraversalAction act = vis.processTransition(state, data, input, trans, succ, dataHolder); 196 197 switch(act) { 198 case ABORT_INPUT: 199 continue inputs_loop; 200 case ABORT_STATE: 201 break inputs_loop; 202 case ABORT_TRAVERSAL: 203 return complete; 204 case EXPLORE: 205 if(stateCount != limit) { 206 bfsQueue.offer(new BFSRecord<S,D>(succ, dataHolder.value)); 207 stateCount++; 208 } 209 else 210 complete = false; 211 break; 212 case IGNORE: 213 } 214 } 215 } 216 } 217 218 return complete; 219 } 220 221 public static <S,I,T,D> 222 boolean breadthFirst(TransitionSystem<S, I, T> ts, 223 Collection<? extends I> inputs, 224 TSTraversalVisitor<S, I, T, D> vis) { 225 return breadthFirst(ts, NO_LIMIT, inputs, vis); 226 } 227 228 229 public static <S,I,T,D> 230 boolean traverse(TraversalOrder order, TransitionSystem<S,I,T> ts, int limit, Collection<? extends I> inputs, TSTraversalVisitor<S, I, T, D> vis) { 231 switch(order) { 232 case BREADTH_FIRST: 233 return breadthFirst(ts, limit, inputs, vis); 234 case DEPTH_FIRST: 235 return depthFirst(ts, limit, inputs, vis); 236 default: 237 throw new IllegalArgumentException("Unknown traversal order: " + order); 238 } 239 } 240 241 public static <S,I,T,D> 242 boolean traverse(TraversalOrder order, TransitionSystem<S,I,T> ts, Collection<? extends I> inputs, TSTraversalVisitor<S, I, T, D> vis) { 243 return traverse(order, ts, NO_LIMIT, inputs, vis); 244 } 245 246}