19566384231

Committed 21 Nov 2025 09:41AM UTC coverage: 92.565% (+0.4%) from 92.206%

Build # 19566384231

Build Type

push

github

Committed by

web-flow

Commit Message

Bump Java Version to 17/25 (#97)

* initial refactorings for Java 25 compatibility

spotbugs + pmd-plugin still need new releases that work on Java 25

* update CI config

* JDK builds pass

updates to the analysis plugins required some adjustments

* utilize Java 17 features

* fix documentation

* cleanups

* fix visibility issues

* potential fix for breaking GUI tests

* example: fix GUI tests

* cleanups

* jung: do not run GUI tests for now

* Revert "jung: do not run GUI tests for now"

This reverts commit 6a6645488.

* jung: found workaround for crashing JVM

* jacoco: correctly track coverage in GUI tests

* Revert "jung: found workaround for crashing JVM"

This reverts commit d99704042.

* Reapply "jung: do not run GUI tests for now"

This reverts commit 176cece7f.

* jung: add note

Run Details

145 of 153 new or added lines in 51 files covered. (94.77%)

1 existing line in 1 file now uncovered.

16496 of 17821 relevant lines covered (92.56%)

1.72 hits per line

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

87.74

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

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of AutomataLib <https://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++;
                    }
            }
        }

        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++;
                        }
                }
            }

            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++;
                    }
            }
        }

        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++;
                    }
            }
        }

        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) {
        return switch (order) {
            case BREADTH_FIRST -> breadthFirst(graph, limit, initialNodes, visitor);
            case DEPTH_FIRST -> depthFirst(graph, limit, initialNodes, visitor);
        };
    }

}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of AutomataLib <https://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	}
161	}	2✔
162
163	bfs_loop:
164	while (!bfsQueue.isEmpty()) {	2✔
165	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
166	@NonNull BFRecord<N, D> current = bfsQueue.poll();	2✔
167
168	N currNode = current.node;	2✔
169	D currData = current.data;	2✔
170
171	if (!visitor.startExploration(currNode, currData)) {	2✔
172	continue;	×
173	}
174
175	Iterator<E> edges = graph.getOutgoingEdgesIterator(currNode);	2✔
176
177	while (edges.hasNext()) {	2✔
178	E edge = edges.next();	2✔
179	N tgtNode = graph.getTarget(edge);	2✔
180
181	dataHolder.value = null;	2✔
182	GraphTraversalAction act = visitor.processEdge(currNode, currData, edge, tgtNode, dataHolder);	2✔
183
184	switch (act) {	2✔
185	case IGNORE:
186	continue;	2✔
187	case ABORT_NODE:
188	continue bfs_loop;	2✔
189	case ABORT_TRAVERSAL:
190	return complete;	×
191	case EXPLORE:
192	if (nodeCount == limit) {	2✔
193	complete = false;	×
194	} else { // not equals will always be true for negative limit values
195	bfsQueue.offer(new BFRecord<>(tgtNode, dataHolder.value));	2✔
196	nodeCount++;	2✔
197	}
198	}
199	}	2✔
200
201	visitor.finishExploration(currNode, currData);	2✔
202	}	2✔
203
204	return complete;	2✔
205	}
206
207	/**
208	* Returns an {@link Iterable} for the (reachable) nodes of the given graph in breadth-first order.
209	*
210	* @param graph
211	* the graph
212	* @param start
213	* the nodes from which the traversal should start
214	* @param <N>
215	* node type
216	* @param <E>
217	* edge type
218	*
219	* @return an {@link Iterable} for the (reachable) nodes of the given graph in breadth-first order
220	*/
221	public static <N, E> Iterable<N> breadthFirstOrder(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
222	return () -> breadthFirstIterator(graph, start);	2✔
223	}
224
225	/**
226	* Returns an {@link Iterator} for the (reachable) nodes of the given graph in breadth-first order.
227	*
228	* @param graph
229	* the graph
230	* @param start
231	* the nodes from which the traversal should start
232	* @param <N>
233	* node type
234	* @param <E>
235	* edge type
236	*
237	* @return an {@link Iterator} for the (reachable) nodes of the given graph in breadth-first order
238	*/
239	public static <N, E> Iterator<N> breadthFirstIterator(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
240	return new BreadthFirstIterator<>(graph, start);	2✔
241	}
242
243	/**
244	* Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
245	*
246	* @param graph
247	* the graph
248	* @param initialNode
249	* the node from which the traversal should start
250	* @param visitor
251	* the visitor
252	* @param <N>
253	* node type
254	* @param <E>
255	* edge type
256	* @param <D>
257	* (user) data type
258	*/
259	public static <N, E, D> void depthFirst(IndefiniteGraph<N, E> graph,
260	N initialNode,
261	GraphTraversalVisitor<N, E, D> visitor) {
262	depthFirst(graph, NO_LIMIT, initialNode, visitor);	2✔
263	}	2✔
264
265	/**
266	* Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
267	*
268	* @param graph
269	* the graph
270	* @param initialNodes
271	* the nodes from which the traversal should start
272	* @param visitor
273	* the visitor
274	* @param <N>
275	* node type
276	* @param <E>
277	* edge type
278	* @param <D>
279	* (user) data type
280	*/
281	public static <N, E, D> void depthFirst(IndefiniteGraph<N, E> graph,
282	Collection<? extends N> initialNodes,
283	GraphTraversalVisitor<N, E, D> visitor) {
284	depthFirst(graph, NO_LIMIT, initialNodes, visitor);	2✔
285	}	2✔
286
287	/**
288	* Traverses the given graph in a depth-first fashion. The traversal is steered by the specified visitor.
289	*
290	* @param graph
291	* the graph
292	* @param limit
293	* the upper bound on the number of nodes to be visited
294	* @param initialNode
295	* the node from which the traversal should start
296	* @param visitor
297	* the visitor
298	* @param <N>
299	* node type
300	* @param <E>
301	* edge type
302	* @param <D>
303	* (user) data type
304	*
305	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
306	*/
307	public static <N, E, D> boolean depthFirst(IndefiniteGraph<N, E> graph,
308	int limit,
309	N initialNode,
310	GraphTraversalVisitor<N, E, D> visitor) {
311	return depthFirst(graph, limit, Collections.singleton(initialNode), visitor);	2✔
312	}
313
314	/**
315	* Traverses the given graph in a breadth-first fashion. The traversal is steered by the specified visitor.
316	*
317	* @param graph
318	* the graph
319	* @param limit
320	* the upper bound on the number of nodes to be visited
321	* @param initialNodes
322	* the nodes from which the traversal should start
323	* @param visitor
324	* the visitor
325	* @param <N>
326	* node type
327	* @param <E>
328	* edge type
329	* @param <D>
330	* (user) data type
331	*
332	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
333	*/
334	public static <N, E, D> boolean depthFirst(IndefiniteGraph<N, E> graph,
335	int limit,
336	Collection<? extends N> initialNodes,
337	GraphTraversalVisitor<N, E, D> visitor) {
338
339	Deque<DFRecord<N, E, D>> dfsStack = new ArrayDeque<>();	2✔
340	Holder<D> dataHolder = new Holder<>();	2✔
341
342	// setting the following to false means that the traversal had to be aborted due to reaching the limit
343	boolean complete = true;	2✔
344	int nodeCount = 0;	2✔
345
346	for (N init : initialNodes) {	2✔
347	dataHolder.value = null;	2✔
348	GraphTraversalAction act = visitor.processInitial(init, dataHolder);	2✔
349
350	switch (act) {	2✔
351	case IGNORE:
352	case ABORT_NODE:
353	continue;	2✔
354	case ABORT_TRAVERSAL:
355	return complete;	2✔
356	case EXPLORE:
357	if (nodeCount == limit) {	2✔
358	complete = false;	2✔
359	} else {
360	dfsStack.push(new DFRecord<>(init, dataHolder.value));	2✔
361	nodeCount++;	2✔
362	}
363	}
364	}	2✔
365
366	while (!dfsStack.isEmpty()) {	2✔
367	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
368	@NonNull DFRecord<N, E, D> current = dfsStack.peek();	2✔
369
370	N currNode = current.node;	2✔
371	D currData = current.data;	2✔
372
373	if (current.start(graph) && !visitor.startExploration(currNode, currData)) {	2✔
374	dfsStack.pop();	×
375	continue;	×
376	}
377
378	LastEdge<E, N, D> lastEdge = current.getLastEdge();	2✔
379	if (lastEdge != null) {	2✔
380	visitor.backtrackEdge(currNode, currData, lastEdge.edge, lastEdge.node, lastEdge.data);	2✔
381	}
382
383	if (!current.hasNextEdge()) {	2✔
384	dfsStack.pop();	2✔
385	visitor.finishExploration(currNode, currData);	2✔
386	continue;	2✔
387	}
388
389	E edge = current.nextEdge();	2✔
390	N tgt = graph.getTarget(edge);	2✔
391	GraphTraversalAction act = visitor.processEdge(currNode, currData, edge, tgt, dataHolder);	2✔
392
393	switch (act) {	2✔
394	case IGNORE:
395	continue;	2✔
396	case ABORT_NODE:
397	dfsStack.pop();	2✔
398	continue;	2✔
399	case ABORT_TRAVERSAL:
400	return complete;	×
401	case EXPLORE:
402	if (nodeCount == limit) {	2✔
403	complete = false;	×
404	} else {
405	D data = dataHolder.value;	2✔
406	current.setLastEdge(edge, tgt, data);	2✔
407	dfsStack.push(new DFRecord<>(tgt, data));	2✔
408	nodeCount++;	2✔
409	}
410	}
411	}	2✔
412
413	return complete;	2✔
414	}
415
416	/**
417	* Returns an {@link Iterable} for the (reachable) nodes of the given graph in depth-first order.
418	*
419	* @param graph
420	* the graph
421	* @param start
422	* the nodes from which the traversal should start
423	* @param <N>
424	* node type
425	* @param <E>
426	* edge type
427	*
428	* @return an {@link Iterable} for the (reachable) nodes of the given graph in depth-first order
429	*/
430	public static <N, E> Iterable<N> depthFirstOrder(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
431	return () -> depthFirstIterator(graph, start);	2✔
432	}
433
434	/**
435	* Returns an {@link Iterator} for the (reachable) nodes of the given graph in depth-first order.
436	*
437	* @param graph
438	* the graph
439	* @param start
440	* the nodes from which the traversal should start
441	* @param <N>
442	* node type
443	* @param <E>
444	* edge type
445	*
446	* @return an {@link Iterator} for the (reachable) nodes of the given graph in depth-first order
447	*/
448	public static <N, E> Iterator<N> depthFirstIterator(IndefiniteGraph<N, E> graph, Collection<? extends N> start) {
449	return new DepthFirstIterator<>(graph, start);	2✔
450	}
451
452	/**
453	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
454	*
455	* @param order
456	* the order in which the states should be traversed
457	* @param graph
458	* the graph
459	* @param initialNode
460	* the node from which the traversal should start
461	* @param visitor
462	* the visitor
463	* @param <N>
464	* node type
465	* @param <E>
466	* edge type
467	* @param <D>
468	* (user) data type
469	*/
470	public static <N, E, D> void traverse(TraversalOrder order,
471	IndefiniteGraph<N, E> graph,
472	N initialNode,
473	GraphTraversalVisitor<N, E, D> visitor) {
474	traverse(order, graph, NO_LIMIT, initialNode, visitor);	×
475	}	×
476
477	/**
478	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
479	*
480	* @param order
481	* the order in which the states should be traversed
482	* @param graph
483	* the graph
484	* @param initialNodes
485	* the nodes from which the traversal should start
486	* @param visitor
487	* the visitor
488	* @param <N>
489	* node type
490	* @param <E>
491	* edge type
492	* @param <D>
493	* (user) data type
494	*/
495	public static <N, E, D> void traverse(TraversalOrder order,
496	IndefiniteGraph<N, E> graph,
497	Collection<? extends N> initialNodes,
498	GraphTraversalVisitor<N, E, D> visitor) {
499	traverse(order, graph, NO_LIMIT, initialNodes, visitor);	×
500	}	×
501
502	/**
503	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
504	*
505	* @param order
506	* the order in which the states should be traversed
507	* @param graph
508	* the graph
509	* @param limit
510	* the upper bound on the number of nodes to be visited
511	* @param initialNode
512	* the node from which the traversal should start
513	* @param visitor
514	* the visitor
515	* @param <N>
516	* node type
517	* @param <E>
518	* edge type
519	* @param <D>
520	* (user) data type
521	*
522	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
523	*/
524	public static <N, E, D> boolean traverse(TraversalOrder order,
525	IndefiniteGraph<N, E> graph,
526	int limit,
527	N initialNode,
528	GraphTraversalVisitor<N, E, D> visitor) {
529	return traverse(order, graph, limit, Collections.singleton(initialNode), visitor);	×
530	}
531
532	/**
533	* Traverses the given graph in a given order. The traversal is steered by the specified visitor.
534	*
535	* @param order
536	* the order in which the states should be traversed
537	* @param graph
538	* the graph
539	* @param limit
540	* the upper bound on the number of nodes to be visited
541	* @param initialNodes
542	* the nodes from which the traversal should start
543	* @param visitor
544	* the visitor
545	* @param <N>
546	* node type
547	* @param <E>
548	* edge type
549	* @param <D>
550	* (user) data type
551	*
552	* @return {@code false} if the number of explored nodes reached {@code limit}, {@code true} otherwise
553	*/
554	public static <N, E, D> boolean traverse(TraversalOrder order,
555	IndefiniteGraph<N, E> graph,
556	int limit,
557	Collection<? extends N> initialNodes,
558	GraphTraversalVisitor<N, E, D> visitor) {
559	return switch (order) {	2✔
560	case BREADTH_FIRST -> breadthFirst(graph, limit, initialNodes, visitor);	2✔
NEW 561	case DEPTH_FIRST -> depthFirst(graph, limit, initialNodes, visitor);	×
562	};
563	}
564
565	}

LearnLib / automatalib / 19566384231

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