12651580329

Committed 07 Jan 2025 12:29PM UTC coverage: 91.569% (+0.03%) from 91.542%

Build # 12651580329

Build Type

push

github

Committed by

web-flow

Commit Message

Update dependencies (#85)

* bump basic dependency versions

* bump checkstyle + cleanups

* bump spotbugs + cleanups

* bump pmd + cleanups

* bump checkerframework + cleanups

* some more cleanups

* ExceptionUtil: support nulls

* improve comments

* cleanup naming + formatting

* formatting

* formatting

* do not fail on javadoc warnings

completness of documentation is now checked by checkstyle and we would have to disable failing anyways when moving on to JDK 17

Run Details

192 of 217 new or added lines in 63 files covered. (88.48%)

4 existing lines in 4 files now uncovered.

16573 of 18099 relevant lines covered (91.57%)

1.69 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.35

/util/src/main/java/net/automatalib/util/graph/traversal/GraphTraversal.java

/* Copyright (C) 2013-2024 TU Dortmund University
 * This file is part of AutomataLib, http://www.automatalib.net/.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.automatalib.util.graph.traversal;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.Queue;

import net.automatalib.common.util.Holder;
import net.automatalib.graph.IndefiniteGraph;
import net.automatalib.util.graph.traversal.DFRecord.LastEdge;
import net.automatalib.util.traversal.TraversalOrder;
import org.checkerframework.checker.nullness.qual.NonNull;

public final class GraphTraversal {

    public static final int NO_LIMIT = -1;

    private GraphTraversal() {
        // prevent inheritance
    }

    /**
     * Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param initialNode
     *         the node from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     */
    public static <N, E, D> void breadthFirst(IndefiniteGraph<N, E> graph,
                                              N initialNode,
                                              GraphTraversalVisitor<N, E, D> visitor) {
        breadthFirst(graph, NO_LIMIT, initialNode, visitor);
    }

    /**
     * Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param initialNodes
     *         the nodes from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     */
    public static <N, E, D> void breadthFirst(IndefiniteGraph<N, E> graph,
                                              Collection<? extends N> initialNodes,
                                              GraphTraversalVisitor<N, E, D> visitor) {
        breadthFirst(graph, NO_LIMIT, initialNodes, visitor);
    }

    /**
     * Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param limit
     *         the upper bound on the number of nodes to be visited
     * @param initialNode
     *         the node from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
     */
    public static <N, E, D> boolean breadthFirst(IndefiniteGraph<N, E> graph,
                                                 int limit,
                                                 N initialNode,
                                                 GraphTraversalVisitor<N, E, D> visitor) {
        return breadthFirst(graph, limit, Collections.singleton(initialNode), visitor);
    }

    /**
     * Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param limit
     *         the upper bound on the number of nodes to be visited
     * @param initialNodes
     *         the nodes from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
     */
    public static <N, E, D> boolean breadthFirst(IndefiniteGraph<N, E> graph,
                                                 int limit,
                                                 Collection<? extends N> initialNodes,
                                                 GraphTraversalVisitor<N, E, D> visitor) {

        Queue<BFRecord<N, D>> bfsQueue = new ArrayDeque<>();

        // setting the following to false means that the traversal had to be aborted due to reaching the limit
        boolean complete = true;
        int nodeCount = 0;

        Holder<D> dataHolder = new Holder<>();

        for (N init : initialNodes) {
            dataHolder.value = null;
            GraphTraversalAction act = visitor.processInitial(init, dataHolder);

            switch (act) {
                case IGNORE:
                case ABORT_NODE:
                    continue;
                case ABORT_TRAVERSAL:
                    return complete;
                case EXPLORE:
                    if (nodeCount == limit) {
                        complete = false;
                    } else { // not equals will always be true for negative limit values
                        bfsQueue.add(new BFRecord<>(init, dataHolder.value));
                        nodeCount++;
                    }
                    break;
                default:
                    throw new IllegalArgumentException("Unknown action " + act);
            }
        }

        bfs_loop:
        while (!bfsQueue.isEmpty()) {
            @SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
            @NonNull BFRecord<N, D> current = bfsQueue.poll();

            N currNode = current.node;
            D currData = current.data;

            if (!visitor.startExploration(currNode, currData)) {
                continue;
            }

            Iterator<E> edges = graph.getOutgoingEdgesIterator(currNode);

            while (edges.hasNext()) {
                E edge = edges.next();
                N tgtNode = graph.getTarget(edge);

                dataHolder.value = null;
                GraphTraversalAction act = visitor.processEdge(currNode, currData, edge, tgtNode, dataHolder);

                switch (act) {
                    case IGNORE:
                        continue;
                    case ABORT_NODE:
                        continue bfs_loop;
                    case ABORT_TRAVERSAL:
                        return complete;
                    case EXPLORE:
                        if (nodeCount == limit) {
                            complete = false;
                        } else { // not equals will always be true for negative limit values
                            bfsQueue.offer(new BFRecord<>(tgtNode, dataHolder.value));
                            nodeCount++;
                        }
                        break;
                    default:
                        throw new IllegalArgumentException("Unknown action " + act);
                }
            }

            visitor.finishExploration(currNode, currData);
        }

        return complete;
    }

    /**
     * Returns an {@link Iterable} for the (reachable) nodes of the given graph in breadth-first order.
     *
     * @param graph
     *         the graph
     * @param start
     *         the nodes from which the traversal should start
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return an {@link Iterable} for the (reachable) nodes of the given graph in breadth-first order
     */
    public static <N, E> Iterable<N> breadthFirstOrder(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
        return () -> breadthFirstIterator(graph, start);
    }

    /**
     * Returns an {@link Iterator} for the (reachable) nodes of the given graph in breadth-first order.
     *
     * @param graph
     *         the graph
     * @param start
     *         the nodes from which the traversal should start
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return an {@link Iterator} for the (reachable) nodes of the given graph in breadth-first order
     */
    public static <N, E> Iterator<N> breadthFirstIterator(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
        return new BreadthFirstIterator<>(graph, start);
    }

    /**
     * Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param initialNode
     *         the node from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     */
    public static <N, E, D> void depthFirst(IndefiniteGraph<N, E> graph,
                                            N initialNode,
                                            GraphTraversalVisitor<N, E, D> visitor) {
        depthFirst(graph, NO_LIMIT, initialNode, visitor);
    }

    /**
     * Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param initialNodes
     *         the nodes from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     */
    public static <N, E, D> void depthFirst(IndefiniteGraph<N, E> graph,
                                            Collection<? extends N> initialNodes,
                                            GraphTraversalVisitor<N, E, D> visitor) {
        depthFirst(graph, NO_LIMIT, initialNodes, visitor);
    }

    /**
     * Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param limit
     *         the upper bound on the number of nodes to be visited
     * @param initialNode
     *         the node from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
     */
    public static <N, E, D> boolean depthFirst(IndefiniteGraph<N, E> graph,
                                               int limit,
                                               N initialNode,
                                               GraphTraversalVisitor<N, E, D> visitor) {
        return depthFirst(graph, limit, Collections.singleton(initialNode), visitor);
    }

    /**
     * Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
     *
     * @param graph
     *         the graph
     * @param limit
     *         the upper bound on the number of nodes to be visited
     * @param initialNodes
     *         the nodes from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
     */
    public static <N, E, D> boolean depthFirst(IndefiniteGraph<N, E> graph,
                                               int limit,
                                               Collection<? extends N> initialNodes,
                                               GraphTraversalVisitor<N, E, D> visitor) {

        Deque<DFRecord<N, E, D>> dfsStack = new ArrayDeque<>();
        Holder<D> dataHolder = new Holder<>();

        // setting the following to false means that the traversal had to be aborted due to reaching the limit
        boolean complete = true;
        int nodeCount = 0;

        for (N init : initialNodes) {
            dataHolder.value = null;
            GraphTraversalAction act = visitor.processInitial(init, dataHolder);

            switch (act) {
                case IGNORE:
                case ABORT_NODE:
                    continue;
                case ABORT_TRAVERSAL:
                    return complete;
                case EXPLORE:
                    if (nodeCount == limit) {
                        complete = false;
                    } else {
                        dfsStack.push(new DFRecord<>(init, dataHolder.value));
                        nodeCount++;
                    }
                    break;
                default:
                    throw new IllegalArgumentException("Unknown action " + act);
            }
        }

        while (!dfsStack.isEmpty()) {
            @SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
            @NonNull DFRecord<N, E, D> current = dfsStack.peek();

            N currNode = current.node;
            D currData = current.data;

            if (current.start(graph) && !visitor.startExploration(currNode, currData)) {
                dfsStack.pop();
                continue;
            }

            LastEdge<E, N, D> lastEdge = current.getLastEdge();
            if (lastEdge != null) {
                visitor.backtrackEdge(currNode, currData, lastEdge.edge, lastEdge.node, lastEdge.data);
            }

            if (!current.hasNextEdge()) {
                dfsStack.pop();
                visitor.finishExploration(currNode, currData);
                continue;
            }

            E edge = current.nextEdge();
            N tgt = graph.getTarget(edge);
            GraphTraversalAction act = visitor.processEdge(currNode, currData, edge, tgt, dataHolder);

            switch (act) {
                case IGNORE:
                    continue;
                case ABORT_NODE:
                    dfsStack.pop();
                    continue;
                case ABORT_TRAVERSAL:
                    return complete;
                case EXPLORE:
                    if (nodeCount == limit) {
                        complete = false;
                    } else {
                        D data = dataHolder.value;
                        current.setLastEdge(edge, tgt, data);
                        dfsStack.push(new DFRecord<>(tgt, data));
                        nodeCount++;
                    }
                    break;
                default:
                    throw new IllegalArgumentException("Unknown action " + act);
            }
        }

        return complete;
    }

    /**
     * Returns an {@link Iterable} for the (reachable) nodes of the given graph in depth-first order.
     *
     * @param graph
     *         the graph
     * @param start
     *         the nodes from which the traversal should start
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return an {@link Iterable} for the (reachable) nodes of the given graph in depth-first order
     */
    public static <N, E> Iterable<N> depthFirstOrder(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
        return () -> depthFirstIterator(graph, start);
    }

    /**
     * Returns an {@link Iterator} for the (reachable) nodes of the given graph in depth-first order.
     *
     * @param graph
     *         the graph
     * @param start
     *         the nodes from which the traversal should start
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return an {@link Iterator} for the (reachable) nodes of the given graph in depth-first order
     */
    public static <N, E> Iterator<N> depthFirstIterator(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
        return new DepthFirstIterator<>(graph, start);
    }

    /**
     * Traverses the given graph in a given order. The traversal is steered by the specified visitor.
     *
     * @param order
     *         the order in which the states should be traversed
     * @param graph
     *         the graph
     * @param initialNode
     *         the node from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     */
    public static <N, E, D> void traverse(TraversalOrder order,
                                          IndefiniteGraph<N, E> graph,
                                          N initialNode,
                                          GraphTraversalVisitor<N, E, D> visitor) {
        traverse(order, graph, NO_LIMIT, initialNode, visitor);
    }

    /**
     * Traverses the given graph in a given order. The traversal is steered by the specified visitor.
     *
     * @param order
     *         the order in which the states should be traversed
     * @param graph
     *         the graph
     * @param initialNodes
     *         the nodes from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     */
    public static <N, E, D> void traverse(TraversalOrder order,
                                          IndefiniteGraph<N, E> graph,
                                          Collection<? extends N> initialNodes,
                                          GraphTraversalVisitor<N, E, D> visitor) {
        traverse(order, graph, NO_LIMIT, initialNodes, visitor);
    }

    /**
     * Traverses the given graph in a given order. The traversal is steered by the specified visitor.
     *
     * @param order
     *         the order in which the states should be traversed
     * @param graph
     *         the graph
     * @param limit
     *         the upper bound on the number of nodes to be visited
     * @param initialNode
     *         the node from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
     */
    public static <N, E, D> boolean traverse(TraversalOrder order,
                                             IndefiniteGraph<N, E> graph,
                                             int limit,
                                             N initialNode,
                                             GraphTraversalVisitor<N, E, D> visitor) {
        return traverse(order, graph, limit, Collections.singleton(initialNode), visitor);
    }

    /**
     * Traverses the given graph in a given order. The traversal is steered by the specified visitor.
     *
     * @param order
     *         the order in which the states should be traversed
     * @param graph
     *         the graph
     * @param limit
     *         the upper bound on the number of nodes to be visited
     * @param initialNodes
     *         the nodes from which the traversal should start
     * @param visitor
     *         the visitor
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
     */
    public static <N, E, D> boolean traverse(TraversalOrder order,
                                             IndefiniteGraph<N, E> graph,
                                             int limit,
                                             Collection<? extends N> initialNodes,
                                             GraphTraversalVisitor<N, E, D> visitor) {
        switch (order) {
            case BREADTH_FIRST:
                return breadthFirst(graph, limit, initialNodes, visitor);
            case DEPTH_FIRST:
                return depthFirst(graph, limit, initialNodes, visitor);
            default:
                throw new IllegalArgumentException("Unknown traversal order " + order);
        }
    }

}

1	/* Copyright (C) 2013-2024 TU Dortmund University
2	* This file is part of AutomataLib, http://www.automatalib.net/.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package net.automatalib.util.graph.traversal;
17
18	import java.util.ArrayDeque;
19	import java.util.Collection;
20	import java.util.Collections;
21	import java.util.Deque;
22	import java.util.Iterator;
23	import java.util.Queue;
24
25	import net.automatalib.common.util.Holder;
26	import net.automatalib.graph.IndefiniteGraph;
27	import net.automatalib.util.graph.traversal.DFRecord.LastEdge;
28	import net.automatalib.util.traversal.TraversalOrder;
29	import org.checkerframework.checker.nullness.qual.NonNull;
30
31	public final class GraphTraversal {
32
33	public static final int NO_LIMIT = -1;
34
35	private GraphTraversal() {
36	// prevent inheritance
37	}
38
39	/**
40	* Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
41	*
42	* @param graph
43	* the graph
44	* @param initialNode
45	* the node from which the traversal should start
46	* @param visitor
47	* the visitor
48	* @param <N>
49	* node type
50	* @param <E>
51	* edge type
52	* @param <D>
53	* (user) data type
54	*/
55	public static <N, E, D> void breadthFirst(IndefiniteGraph<N, E> graph,
56	N initialNode,
57	GraphTraversalVisitor<N, E, D> visitor) {
58	breadthFirst(graph, NO_LIMIT, initialNode, visitor);	2✔
59	}	2✔
60
61	/**
62	* Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
63	*
64	* @param graph
65	* the graph
66	* @param initialNodes
67	* the nodes from which the traversal should start
68	* @param visitor
69	* the visitor
70	* @param <N>
71	* node type
72	* @param <E>
73	* edge type
74	* @param <D>
75	* (user) data type
76	*/
77	public static <N, E, D> void breadthFirst(IndefiniteGraph<N, E> graph,
78	Collection<? extends N> initialNodes,
79	GraphTraversalVisitor<N, E, D> visitor) {
80	breadthFirst(graph, NO_LIMIT, initialNodes, visitor);	2✔
81	}	2✔
82
83	/**
84	* Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
85	*
86	* @param graph
87	* the graph
88	* @param limit
89	* the upper bound on the number of nodes to be visited
90	* @param initialNode
91	* the node from which the traversal should start
92	* @param visitor
93	* the visitor
94	* @param <N>
95	* node type
96	* @param <E>
97	* edge type
98	* @param <D>
99	* (user) data type
100	*
101	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
102	*/
103	public static <N, E, D> boolean breadthFirst(IndefiniteGraph<N, E> graph,
104	int limit,
105	N initialNode,
106	GraphTraversalVisitor<N, E, D> visitor) {
107	return breadthFirst(graph, limit, Collections.singleton(initialNode), visitor);	2✔
108	}
109
110	/**
111	* Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
112	*
113	* @param graph
114	* the graph
115	* @param limit
116	* the upper bound on the number of nodes to be visited
117	* @param initialNodes
118	* the nodes from which the traversal should start
119	* @param visitor
120	* the visitor
121	* @param <N>
122	* node type
123	* @param <E>
124	* edge type
125	* @param <D>
126	* (user) data type
127	*
128	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
129	*/
130	public static <N, E, D> boolean breadthFirst(IndefiniteGraph<N, E> graph,
131	int limit,
132	Collection<? extends N> initialNodes,
133	GraphTraversalVisitor<N, E, D> visitor) {
134
135	Queue<BFRecord<N, D>> bfsQueue = new ArrayDeque<>();	2✔
136
137	// setting the following to false means that the traversal had to be aborted due to reaching the limit
138	boolean complete = true;	2✔
139	int nodeCount = 0;	2✔
140
141	Holder<D> dataHolder = new Holder<>();	2✔
142
143	for (N init : initialNodes) {	2✔
144	dataHolder.value = null;	2✔
145	GraphTraversalAction act = visitor.processInitial(init, dataHolder);	2✔
146
147	switch (act) {	2✔
148	case IGNORE:
149	case ABORT_NODE:
150	continue;	2✔
151	case ABORT_TRAVERSAL:
152	return complete;	2✔
153	case EXPLORE:
154	if (nodeCount == limit) {	2✔
155	complete = false;	2✔
156	} else { // not equals will always be true for negative limit values
157	bfsQueue.add(new BFRecord<>(init, dataHolder.value));	2✔
158	nodeCount++;	2✔
159	}
160	break;	2✔
161	default:
162	throw new IllegalArgumentException("Unknown action " + act);	×
163	}
164	}	2✔
165
166	bfs_loop:
167	while (!bfsQueue.isEmpty()) {	2✔
168	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
169	@NonNull BFRecord<N, D> current = bfsQueue.poll();	2✔
170
171	N currNode = current.node;	2✔
172	D currData = current.data;	2✔
173
174	if (!visitor.startExploration(currNode, currData)) {	2✔
175	continue;	×
176	}
177
178	Iterator<E> edges = graph.getOutgoingEdgesIterator(currNode);	2✔
179
180	while (edges.hasNext()) {	2✔
181	E edge = edges.next();	2✔
182	N tgtNode = graph.getTarget(edge);	2✔
183
184	dataHolder.value = null;	2✔
185	GraphTraversalAction act = visitor.processEdge(currNode, currData, edge, tgtNode, dataHolder);	2✔
186
187	switch (act) {	2✔
188	case IGNORE:
189	continue;	2✔
190	case ABORT_NODE:
191	continue bfs_loop;	2✔
192	case ABORT_TRAVERSAL:
193	return complete;	×
194	case EXPLORE:
195	if (nodeCount == limit) {	2✔
NEW 196	complete = false;	×
197	} else { // not equals will always be true for negative limit values
198	bfsQueue.offer(new BFRecord<>(tgtNode, dataHolder.value));	2✔
199	nodeCount++;	2✔
200	}
201	break;	2✔
202	default:
203	throw new IllegalArgumentException("Unknown action " + act);	×
204	}
205	}	2✔
206
207	visitor.finishExploration(currNode, currData);	2✔
208	}	2✔
209
210	return complete;	2✔
211	}
212
213	/**
214	* Returns an {@link Iterable} for the (reachable) nodes of the given graph in breadth-first order.
215	*
216	* @param graph
217	* the graph
218	* @param start
219	* the nodes from which the traversal should start
220	* @param <N>
221	* node type
222	* @param <E>
223	* edge type
224	*
225	* @return an {@link Iterable} for the (reachable) nodes of the given graph in breadth-first order
226	*/
227	public static <N, E> Iterable<N> breadthFirstOrder(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
228	return () -> breadthFirstIterator(graph, start);	2✔
229	}
230
231	/**
232	* Returns an {@link Iterator} for the (reachable) nodes of the given graph in breadth-first order.
233	*
234	* @param graph
235	* the graph
236	* @param start
237	* the nodes from which the traversal should start
238	* @param <N>
239	* node type
240	* @param <E>
241	* edge type
242	*
243	* @return an {@link Iterator} for the (reachable) nodes of the given graph in breadth-first order
244	*/
245	public static <N, E> Iterator<N> breadthFirstIterator(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
246	return new BreadthFirstIterator<>(graph, start);	2✔
247	}
248
249	/**
250	* Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
251	*
252	* @param graph
253	* the graph
254	* @param initialNode
255	* the node from which the traversal should start
256	* @param visitor
257	* the visitor
258	* @param <N>
259	* node type
260	* @param <E>
261	* edge type
262	* @param <D>
263	* (user) data type
264	*/
265	public static <N, E, D> void depthFirst(IndefiniteGraph<N, E> graph,
266	N initialNode,
267	GraphTraversalVisitor<N, E, D> visitor) {
268	depthFirst(graph, NO_LIMIT, initialNode, visitor);	2✔
269	}	2✔
270
271	/**
272	* Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
273	*
274	* @param graph
275	* the graph
276	* @param initialNodes
277	* the nodes from which the traversal should start
278	* @param visitor
279	* the visitor
280	* @param <N>
281	* node type
282	* @param <E>
283	* edge type
284	* @param <D>
285	* (user) data type
286	*/
287	public static <N, E, D> void depthFirst(IndefiniteGraph<N, E> graph,
288	Collection<? extends N> initialNodes,
289	GraphTraversalVisitor<N, E, D> visitor) {
290	depthFirst(graph, NO_LIMIT, initialNodes, visitor);	2✔
291	}	2✔
292
293	/**
294	* Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
295	*
296	* @param graph
297	* the graph
298	* @param limit
299	* the upper bound on the number of nodes to be visited
300	* @param initialNode
301	* the node from which the traversal should start
302	* @param visitor
303	* the visitor
304	* @param <N>
305	* node type
306	* @param <E>
307	* edge type
308	* @param <D>
309	* (user) data type
310	*
311	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
312	*/
313	public static <N, E, D> boolean depthFirst(IndefiniteGraph<N, E> graph,
314	int limit,
315	N initialNode,
316	GraphTraversalVisitor<N, E, D> visitor) {
317	return depthFirst(graph, limit, Collections.singleton(initialNode), visitor);	2✔
318	}
319
320	/**
321	* Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
322	*
323	* @param graph
324	* the graph
325	* @param limit
326	* the upper bound on the number of nodes to be visited
327	* @param initialNodes
328	* the nodes from which the traversal should start
329	* @param visitor
330	* the visitor
331	* @param <N>
332	* node type
333	* @param <E>
334	* edge type
335	* @param <D>
336	* (user) data type
337	*
338	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
339	*/
340	public static <N, E, D> boolean depthFirst(IndefiniteGraph<N, E> graph,
341	int limit,
342	Collection<? extends N> initialNodes,
343	GraphTraversalVisitor<N, E, D> visitor) {
344
345	Deque<DFRecord<N, E, D>> dfsStack = new ArrayDeque<>();	2✔
346	Holder<D> dataHolder = new Holder<>();	2✔
347
348	// setting the following to false means that the traversal had to be aborted due to reaching the limit
349	boolean complete = true;	2✔
350	int nodeCount = 0;	2✔
351
352	for (N init : initialNodes) {	2✔
353	dataHolder.value = null;	2✔
354	GraphTraversalAction act = visitor.processInitial(init, dataHolder);	2✔
355
356	switch (act) {	2✔
357	case IGNORE:
358	case ABORT_NODE:
359	continue;	2✔
360	case ABORT_TRAVERSAL:
361	return complete;	2✔
362	case EXPLORE:
363	if (nodeCount == limit) {	2✔
364	complete = false;	2✔
365	} else {
366	dfsStack.push(new DFRecord<>(init, dataHolder.value));	2✔
367	nodeCount++;	2✔
368	}
369	break;	2✔
370	default:
371	throw new IllegalArgumentException("Unknown action " + act);	×
372	}
373	}	2✔
374
375	while (!dfsStack.isEmpty()) {	2✔
376	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
377	@NonNull DFRecord<N, E, D> current = dfsStack.peek();	2✔
378
379	N currNode = current.node;	2✔
380	D currData = current.data;	2✔
381
382	if (current.start(graph) && !visitor.startExploration(currNode, currData)) {	2✔
383	dfsStack.pop();	×
384	continue;	×
385	}
386
387	LastEdge<E, N, D> lastEdge = current.getLastEdge();	2✔
388	if (lastEdge != null) {	2✔
389	visitor.backtrackEdge(currNode, currData, lastEdge.edge, lastEdge.node, lastEdge.data);	2✔
390	}
391
392	if (!current.hasNextEdge()) {	2✔
393	dfsStack.pop();	2✔
394	visitor.finishExploration(currNode, currData);	2✔
395	continue;	2✔
396	}
397
398	E edge = current.nextEdge();	2✔
399	N tgt = graph.getTarget(edge);	2✔
400	GraphTraversalAction act = visitor.processEdge(currNode, currData, edge, tgt, dataHolder);	2✔
401
402	switch (act) {	2✔
403	case IGNORE:
404	continue;	2✔
405	case ABORT_NODE:
406	dfsStack.pop();	2✔
407	continue;	2✔
408	case ABORT_TRAVERSAL:
409	return complete;	×
410	case EXPLORE:
411	if (nodeCount == limit) {	2✔
NEW 412	complete = false;	×
413	} else {
414	D data = dataHolder.value;	2✔
415	current.setLastEdge(edge, tgt, data);	2✔
416	dfsStack.push(new DFRecord<>(tgt, data));	2✔
417	nodeCount++;	2✔
418	}
419	break;	2✔
420	default:
421	throw new IllegalArgumentException("Unknown action " + act);	×
422	}
423	}	2✔
424
425	return complete;	2✔
426	}
427
428	/**
429	* Returns an {@link Iterable} for the (reachable) nodes of the given graph in depth-first order.
430	*
431	* @param graph
432	* the graph
433	* @param start
434	* the nodes from which the traversal should start
435	* @param <N>
436	* node type
437	* @param <E>
438	* edge type
439	*
440	* @return an {@link Iterable} for the (reachable) nodes of the given graph in depth-first order
441	*/
442	public static <N, E> Iterable<N> depthFirstOrder(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
443	return () -> depthFirstIterator(graph, start);	2✔
444	}
445
446	/**
447	* Returns an {@link Iterator} for the (reachable) nodes of the given graph in depth-first order.
448	*
449	* @param graph
450	* the graph
451	* @param start
452	* the nodes from which the traversal should start
453	* @param <N>
454	* node type
455	* @param <E>
456	* edge type
457	*
458	* @return an {@link Iterator} for the (reachable) nodes of the given graph in depth-first order
459	*/
460	public static <N, E> Iterator<N> depthFirstIterator(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
461	return new DepthFirstIterator<>(graph, start);	2✔
462	}
463
464	/**
465	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
466	*
467	* @param order
468	* the order in which the states should be traversed
469	* @param graph
470	* the graph
471	* @param initialNode
472	* the node from which the traversal should start
473	* @param visitor
474	* the visitor
475	* @param <N>
476	* node type
477	* @param <E>
478	* edge type
479	* @param <D>
480	* (user) data type
481	*/
482	public static <N, E, D> void traverse(TraversalOrder order,
483	IndefiniteGraph<N, E> graph,
484	N initialNode,
485	GraphTraversalVisitor<N, E, D> visitor) {
486	traverse(order, graph, NO_LIMIT, initialNode, visitor);	×
487	}	×
488
489	/**
490	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
491	*
492	* @param order
493	* the order in which the states should be traversed
494	* @param graph
495	* the graph
496	* @param initialNodes
497	* the nodes from which the traversal should start
498	* @param visitor
499	* the visitor
500	* @param <N>
501	* node type
502	* @param <E>
503	* edge type
504	* @param <D>
505	* (user) data type
506	*/
507	public static <N, E, D> void traverse(TraversalOrder order,
508	IndefiniteGraph<N, E> graph,
509	Collection<? extends N> initialNodes,
510	GraphTraversalVisitor<N, E, D> visitor) {
511	traverse(order, graph, NO_LIMIT, initialNodes, visitor);	×
512	}	×
513
514	/**
515	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
516	*
517	* @param order
518	* the order in which the states should be traversed
519	* @param graph
520	* the graph
521	* @param limit
522	* the upper bound on the number of nodes to be visited
523	* @param initialNode
524	* the node from which the traversal should start
525	* @param visitor
526	* the visitor
527	* @param <N>
528	* node type
529	* @param <E>
530	* edge type
531	* @param <D>
532	* (user) data type
533	*
534	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
535	*/
536	public static <N, E, D> boolean traverse(TraversalOrder order,
537	IndefiniteGraph<N, E> graph,
538	int limit,
539	N initialNode,
540	GraphTraversalVisitor<N, E, D> visitor) {
541	return traverse(order, graph, limit, Collections.singleton(initialNode), visitor);	×
542	}
543
544	/**
545	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
546	*
547	* @param order
548	* the order in which the states should be traversed
549	* @param graph
550	* the graph
551	* @param limit
552	* the upper bound on the number of nodes to be visited
553	* @param initialNodes
554	* the nodes from which the traversal should start
555	* @param visitor
556	* the visitor
557	* @param <N>
558	* node type
559	* @param <E>
560	* edge type
561	* @param <D>
562	* (user) data type
563	*
564	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
565	*/
566	public static <N, E, D> boolean traverse(TraversalOrder order,
567	IndefiniteGraph<N, E> graph,
568	int limit,
569	Collection<? extends N> initialNodes,
570	GraphTraversalVisitor<N, E, D> visitor) {
571	switch (order) {	2✔
572	case BREADTH_FIRST:
573	return breadthFirst(graph, limit, initialNodes, visitor);	2✔
574	case DEPTH_FIRST:
575	return depthFirst(graph, limit, initialNodes, visitor);	×
576	default:
577	throw new IllegalArgumentException("Unknown traversal order " + order);	×
578	}
579	}
580
581	}

LearnLib / automatalib / 12651580329

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous