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}