12019076191

Committed 25 Nov 2024 09:09PM UTC coverage: 90.741%. Remained the same

Build # 12019076191

Build Type

push

github

Committed by

mtf90

Commit Message

add KTS abstraction

Run Details

15994 of 17626 relevant lines covered (90.74%)

1.68 hits per line

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

89.71

/util/src/main/java/net/automatalib/util/graph/sssp/DijkstraSSSP.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.sssp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import net.automatalib.common.smartcollection.BinaryHeap;
import net.automatalib.common.smartcollection.ElementReference;
import net.automatalib.common.smartcollection.SmartDynamicPriorityQueue;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.graph.Graph;
import net.automatalib.graph.concept.EdgeWeights;
import net.automatalib.util.graph.Graphs;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.checkerframework.checker.nullness.qual.PolyNull;

/**
 * Implementation of Dijkstra's algorithm for the single-source shortest path problem, as described in <a
 * href="https://doi.org/10.1007/BF01386390">A note on two problems in connexion with graphs</a>.
 *
 * @param <N>
 *         node class
 * @param <E>
 *         edge class
 */
public class DijkstraSSSP<N, E> implements SSSPResult<N, E> {

    private final Graph<N, E> graph;
    private final N init;
    private final EdgeWeights<E> edgeWeights;
    private final MutableMapping<N, @Nullable Record<N, E>> records;

    /**
     * Constructor.
     *
     * @param graph
     *         the graph in which to search for shortest paths
     * @param init
     *         the initial node
     * @param edgeWeights
     *         the edge weights
     */
    public DijkstraSSSP(Graph<N, E> graph, N init, EdgeWeights<E> edgeWeights) {
        this.graph = graph;
        this.init = init;
        this.edgeWeights = edgeWeights;
        this.records = graph.createStaticNodeMapping();
    }

    /**
     * Search for the shortest paths from a single source node in a graph.
     *
     * @param graph
     *         the graph in which to perform the search
     * @param init
     *         the initial (source) node
     * @param edgeWeights
     *         the edge weights
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return the single-source shortest path results
     */
    public static <N, E> SSSPResult<N, E> findSSSP(Graph<N, E> graph, N init, EdgeWeights<E> edgeWeights) {
        DijkstraSSSP<N, E> dijkstra = new DijkstraSSSP<>(graph, init, edgeWeights);
        dijkstra.findSSSP();
        return dijkstra;
    }

    /**
     * Start the search. This method may only be invoked once.
     */
    public void findSSSP() {
        Record<N, E> initRec = new Record<>(init, 0.0f);
        if (records.put(init, initRec) != null) {
            throw new IllegalStateException("Search has already been performed!");
        }

        SmartDynamicPriorityQueue<Record<N, E>> pq = BinaryHeap.create(graph.size());
        initRec.ref = pq.referencedAdd(initRec);

        while (!pq.isEmpty()) {
            // Remove node with minimum distance
            Record<N, E> rec = pq.extractMin();
            float dist = rec.dist;

            N node = rec.node;

            // edge scanning
            for (E edge : graph.getOutgoingEdges(node)) {
                float w = edgeWeights.getEdgeWeight(edge);
                float newDist = dist + w;

                N tgt = graph.getTarget(edge);
                Record<N, E> tgtRec = records.get(tgt);
                if (tgtRec == null) {
                    // node has not been visited before, add a record
                    // and add it to the queue
                    tgtRec = new Record<>(tgt, newDist, edge, rec);
                    tgtRec.ref = pq.referencedAdd(tgtRec);
                    records.put(tgt, tgtRec);
                } else if (newDist < tgtRec.dist) {
                    // using currently considered edge decreases current distance
                    tgtRec.dist = newDist;
                    tgtRec.reach = edge;
                    tgtRec.depth = rec.depth + 1;
                    tgtRec.parent = rec;
                    // update it's position in the queue
                    pq.keyChanged(tgtRec.ref);
                }
            }
        }
    }

    @Override
    public N getInitialNode() {
        return init;
    }

    @Override
    public float getShortestPathDistance(N target) {
        Record<N, E> rec = records.get(target);
        if (rec == null) {
            return Graphs.INVALID_DISTANCE;
        }
        return rec.dist;
    }

    @Override
    public @Nullable List<E> getShortestPath(N target) {
        Record<N, E> rec = records.get(target);
        if (rec == null) {
            return null;
        }

        if (rec.depth == 0) {
            return Collections.emptyList();
        }

        List<E> result = new ArrayList<>(rec.depth);

        E edge;
        while ((edge = rec.reach) != null) {
            result.add(edge);
            rec = rec.parent;
            assert rec != null;
        }

        Collections.reverse(result);
        return result;
    }

    @Override
    public @Nullable E getShortestPathEdge(N target) {
        Record<N, E> rec = records.get(target);
        if (rec == null) {
            return null;
        }
        return rec.reach;
    }

    /**
     * Internal data record. Note: this class has a natural ordering that is inconsistent with equals.
     */
    private static final class Record<N, E> implements Comparable<Record<N, E>> {

        public final N node;
        public float dist;
        public @Nullable ElementReference ref;
        public @PolyNull E reach;
        public @PolyNull Record<N, E> parent;
        int depth;

        Record(N node, float dist) {
            this(node, dist, null, null);
        }

        Record(N node, float dist, @PolyNull E reach, @PolyNull Record<N, E> parent) {
            this.node = node;
            this.dist = dist;
            this.reach = reach;
            this.parent = parent;
            this.depth = (parent != null) ? parent.depth + 1 : 0;
        }

        @Override
        public int compareTo(Record<N, E> o) {
            return Float.compare(dist, o.dist);
        }
    }
}

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.sssp;
17
18	import java.util.ArrayList;
19	import java.util.Collections;
20	import java.util.List;
21
22	import net.automatalib.common.smartcollection.BinaryHeap;
23	import net.automatalib.common.smartcollection.ElementReference;
24	import net.automatalib.common.smartcollection.SmartDynamicPriorityQueue;
25	import net.automatalib.common.util.mapping.MutableMapping;
26	import net.automatalib.graph.Graph;
27	import net.automatalib.graph.concept.EdgeWeights;
28	import net.automatalib.util.graph.Graphs;
29	import org.checkerframework.checker.nullness.qual.Nullable;
30	import org.checkerframework.checker.nullness.qual.PolyNull;
31
32	/**
33	* Implementation of Dijkstra's algorithm for the single-source shortest path problem, as described in <a
34	* href="https://doi.org/10.1007/BF01386390">A note on two problems in connexion with graphs</a>.
35	*
36	* @param <N>
37	* node class
38	* @param <E>
39	* edge class
40	*/
41	public class DijkstraSSSP<N, E> implements SSSPResult<N, E> {	2✔
42
43	private final Graph<N, E> graph;
44	private final N init;
45	private final EdgeWeights<E> edgeWeights;
46	private final MutableMapping<N, @Nullable Record<N, E>> records;
47
48	/**
49	* Constructor.
50	*
51	* @param graph
52	* the graph in which to search for shortest paths
53	* @param init
54	* the initial node
55	* @param edgeWeights
56	* the edge weights
57	*/
58	public DijkstraSSSP(Graph<N, E> graph, N init, EdgeWeights<E> edgeWeights) {	2✔
59	this.graph = graph;	2✔
60	this.init = init;	2✔
61	this.edgeWeights = edgeWeights;	2✔
62	this.records = graph.createStaticNodeMapping();	2✔
63	}	2✔
64
65	/**
66	* Search for the shortest paths from a single source node in a graph.
67	*
68	* @param graph
69	* the graph in which to perform the search
70	* @param init
71	* the initial (source) node
72	* @param edgeWeights
73	* the edge weights
74	* @param <N>
75	* node type
76	* @param <E>
77	* edge type
78	*
79	* @return the single-source shortest path results
80	*/
81	public static <N, E> SSSPResult<N, E> findSSSP(Graph<N, E> graph, N init, EdgeWeights<E> edgeWeights) {
82	DijkstraSSSP<N, E> dijkstra = new DijkstraSSSP<>(graph, init, edgeWeights);	2✔
83	dijkstra.findSSSP();	2✔
84	return dijkstra;	2✔
85	}
86
87	/**
88	* Start the search. This method may only be invoked once.
89	*/
90	public void findSSSP() {
91	Record<N, E> initRec = new Record<>(init, 0.0f);	2✔
92	if (records.put(init, initRec) != null) {	2✔
93	throw new IllegalStateException("Search has already been performed!");	×
94	}
95
96	SmartDynamicPriorityQueue<Record<N, E>> pq = BinaryHeap.create(graph.size());	2✔
97	initRec.ref = pq.referencedAdd(initRec);	2✔
98
99	while (!pq.isEmpty()) {	2✔
100	// Remove node with minimum distance
101	Record<N, E> rec = pq.extractMin();	2✔
102	float dist = rec.dist;	2✔
103
104	N node = rec.node;	2✔
105
106	// edge scanning
107	for (E edge : graph.getOutgoingEdges(node)) {	2✔
108	float w = edgeWeights.getEdgeWeight(edge);	2✔
109	float newDist = dist + w;	2✔
110
111	N tgt = graph.getTarget(edge);	2✔
112	Record<N, E> tgtRec = records.get(tgt);	2✔
113	if (tgtRec == null) {	2✔
114	// node has not been visited before, add a record
115	// and add it to the queue
116	tgtRec = new Record<>(tgt, newDist, edge, rec);	2✔
117	tgtRec.ref = pq.referencedAdd(tgtRec);	2✔
118	records.put(tgt, tgtRec);	2✔
119	} else if (newDist < tgtRec.dist) {	2✔
120	// using currently considered edge decreases current distance
121	tgtRec.dist = newDist;	2✔
122	tgtRec.reach = edge;	2✔
123	tgtRec.depth = rec.depth + 1;	2✔
124	tgtRec.parent = rec;	2✔
125	// update it's position in the queue
126	pq.keyChanged(tgtRec.ref);	2✔
127	}
128	}	2✔
129	}	2✔
130	}	2✔
131
132	@Override
133	public N getInitialNode() {
134	return init;	2✔
135	}
136
137	@Override
138	public float getShortestPathDistance(N target) {
139	Record<N, E> rec = records.get(target);	2✔
140	if (rec == null) {	2✔
141	return Graphs.INVALID_DISTANCE;	2✔
142	}
143	return rec.dist;	2✔
144	}
145
146	@Override
147	public @Nullable List<E> getShortestPath(N target) {
148	Record<N, E> rec = records.get(target);	2✔
149	if (rec == null) {	2✔
150	return null;	×
151	}
152
153	if (rec.depth == 0) {	2✔
154	return Collections.emptyList();	×
155	}
156
157	List<E> result = new ArrayList<>(rec.depth);	2✔
158
159	E edge;
160	while ((edge = rec.reach) != null) {	2✔
161	result.add(edge);	2✔
162	rec = rec.parent;	2✔
163	assert rec != null;	2✔
164	}
165
166	Collections.reverse(result);	2✔
167	return result;	2✔
168	}
169
170	@Override
171	public @Nullable E getShortestPathEdge(N target) {
172	Record<N, E> rec = records.get(target);	×
173	if (rec == null) {	×
174	return null;	×
175	}
176	return rec.reach;	×
177	}
178
179	/**
180	* Internal data record. Note: this class has a natural ordering that is inconsistent with equals.
181	*/
182	private static final class Record<N, E> implements Comparable<Record<N, E>> {
183
184	public final N node;
185	public float dist;
186	public @Nullable ElementReference ref;
187	public @PolyNull E reach;
188	public @PolyNull Record<N, E> parent;
189	int depth;
190
191	Record(N node, float dist) {
192	this(node, dist, null, null);	2✔
193	}	2✔
194
195	Record(N node, float dist, @PolyNull E reach, @PolyNull Record<N, E> parent) {	2✔
196	this.node = node;	2✔
197	this.dist = dist;	2✔
198	this.reach = reach;	2✔
199	this.parent = parent;	2✔
200	this.depth = (parent != null) ? parent.depth + 1 : 0;	2✔
201	}	2✔
202
203	@Override
204	public int compareTo(Record<N, E> o) {
205	return Float.compare(dist, o.dist);	2✔
206	}
207	}
208	}

LearnLib / automatalib / 12019076191

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