13138848026

Committed 04 Feb 2025 02:53PM UTC coverage: 92.108% (+2.2%) from 89.877%

Build # 13138848026

Build Type

push

github

Committed by

mtf90

Commit Message

[maven-release-plugin] prepare release automatalib-0.12.0

Run Details

16609 of 18032 relevant lines covered (92.11%)

1.7 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-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++;
                    }
                    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-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	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✔
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✔
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 / 13138848026

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