Source code

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.graphs.IndefiniteGraph;
028import net.automatalib.util.graphs.traversal.DFRecord.LastEdge;
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                        LastEdge<E,N,D> lastEdge = current.getLastEdge();
228                        if(lastEdge != null) {
229                                vis.backtrackEdge(currNode, currData, lastEdge.edge,
230                                                lastEdge.node, lastEdge.data);
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}