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

98.73

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

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

import net.automatalib.graph.Graph;
import net.automatalib.graph.concept.EdgeWeights;
import net.automatalib.graph.concept.NodeIDs;
import net.automatalib.util.graph.Graphs;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Implementation of the Floyd-Warshall dynamic programming algorithm for the all pairs shortest paths problem, as
 * described in <a href="https://doi.org/10.1145/367766.368168">Algorithm 97: Shortest path</a>.
 *
 * @param <N>
 *         node class
 * @param <E>
 *         edge class
 */
public class FloydWarshallAPSP<N, E> implements APSPResult<N, E> {

    private final int size;
    private final NodeIDs<N> ids;
    private final @Nullable APSPRecord<E>[][] table;

    @SuppressWarnings({"unchecked", "initialization"})
    public FloydWarshallAPSP(Graph<N, E> graph, EdgeWeights<E> ew) {
        this.size = graph.size();
        this.ids = graph.nodeIDs();
        this.table = new APSPRecord[size][size];

        initialize(graph, ew);
    }

    private void initialize(Graph<N, E> graph, EdgeWeights<E> ew) {
        for (int i = 0; i < size; i++) {
            N src = ids.getNode(i);

            Collection<E> edges = graph.getOutgoingEdges(src);

            for (E edge : edges) {
                N tgt = graph.getTarget(edge);
                if (Objects.equals(tgt, src)) {
                    continue;
                }

                int j = ids.getNodeId(tgt);
                float w = ew.getEdgeWeight(edge);
                APSPRecord<E> prev = table[i][j];
                if (prev == null || prev.distance > w) {
                    table[i][j] = new APSPRecord<>(edge, w);
                }
            }
        }
    }

    public static <N, E> APSPResult<N, E> findAPSP(Graph<N, E> graph, EdgeWeights<E> edgeWeights) {
        FloydWarshallAPSP<N, E> fw = new FloydWarshallAPSP<>(graph, edgeWeights);
        fw.findAPSP();
        return fw;
    }

    public void findAPSP() {
        for (int k = 0; k < size; k++) {

            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (j == i) {
                        continue;
                    }

                    APSPRecord<E> currRec = table[i][j];

                    if (k == i || k == j) {
                        continue;
                    }

                    APSPRecord<E> part1 = table[i][k], part2 = table[k][j];

                    if (part1 == null || part2 == null) {
                        continue;
                    }

                    float dist1 = part1.distance, dist2 = part2.distance;
                    float total = dist1 + dist2;

                    if (currRec == null) {
                        currRec = new APSPRecord<>(total, k, part1.numEdges + part2.numEdges);
                        table[i][j] = currRec;
                    } else if (currRec.distance > total) {
                        currRec.distance = total;
                        currRec.middle = k;
                        currRec.numEdges = part1.numEdges + part2.numEdges;
                    }

                }
            }
        }
    }

    @Override
    public float getShortestPathDistance(N src, N tgt) {
        int srcId = ids.getNodeId(src), tgtId = ids.getNodeId(tgt);

        if (srcId == tgtId) {
            return 0;
        }

        APSPRecord<E> rec = table[srcId][tgtId];
        if (rec == null) {
            return Graphs.INVALID_DISTANCE;
        }

        return rec.distance;
    }

    @Override
    public @Nullable List<E> getShortestPath(N src, N tgt) {
        int srcId = ids.getNodeId(src), tgtId = ids.getNodeId(tgt);

        if (srcId == tgtId) {
            return Collections.emptyList();
        }

        APSPRecord<E> rec = table[srcId][tgtId];

        if (rec == null) {
            return null;
        }

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

        buildPath(result, srcId, tgtId, rec);

        return result;
    }

    @SuppressWarnings("nullness") // our initialization ensures that we don't access undefined indices
    private void buildPath(List<E> path, int srcId, int tgtId, APSPRecord<E> rec) {
        if (rec.middle == -1) {
            path.add(rec.edge);
            return;
        }

        int middle = rec.middle;
        buildPath(path, srcId, middle, table[srcId][middle]);
        buildPath(path, middle, tgtId, table[middle][tgtId]);
    }

    private static final class APSPRecord<E> {

        public final @Nullable E edge;
        public float distance;
        public int middle;
        public int numEdges;

        APSPRecord(E edge, float distance) {
            this.edge = edge;
            this.distance = distance;
            this.middle = -1;
            this.numEdges = 1;
        }

        APSPRecord(float distance, int middle, int numEdges) {
            this.edge = null;
            this.distance = distance;
            this.middle = middle;
            this.numEdges = numEdges;
        }
    }
}

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.apsp;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.Collections;
21	import java.util.List;
22	import java.util.Objects;
23
24	import net.automatalib.graph.Graph;
25	import net.automatalib.graph.concept.EdgeWeights;
26	import net.automatalib.graph.concept.NodeIDs;
27	import net.automatalib.util.graph.Graphs;
28	import org.checkerframework.checker.nullness.qual.Nullable;
29
30	/**
31	* Implementation of the Floyd-Warshall dynamic programming algorithm for the all pairs shortest paths problem, as
32	* described in <a href="https://doi.org/10.1145/367766.368168">Algorithm 97: Shortest path</a>.
33	*
34	* @param <N>
35	* node class
36	* @param <E>
37	* edge class
38	*/
39	public class FloydWarshallAPSP<N, E> implements APSPResult<N, E> {
40
41	private final int size;
42	private final NodeIDs<N> ids;
43	private final @Nullable APSPRecord<E>[][] table;
44
45	@SuppressWarnings({"unchecked", "initialization"})
46	public FloydWarshallAPSP(Graph<N, E> graph, EdgeWeights<E> ew) {	2✔
47	this.size = graph.size();	2✔
48	this.ids = graph.nodeIDs();	2✔
49	this.table = new APSPRecord[size][size];	2✔
50
51	initialize(graph, ew);	2✔
52	}	2✔
53
54	private void initialize(Graph<N, E> graph, EdgeWeights<E> ew) {
55	for (int i = 0; i < size; i++) {	2✔
56	N src = ids.getNode(i);	2✔
57
58	Collection<E> edges = graph.getOutgoingEdges(src);	2✔
59
60	for (E edge : edges) {	2✔
61	N tgt = graph.getTarget(edge);	2✔
62	if (Objects.equals(tgt, src)) {	2✔
63	continue;	2✔
64	}
65
66	int j = ids.getNodeId(tgt);	2✔
67	float w = ew.getEdgeWeight(edge);	2✔
68	APSPRecord<E> prev = table[i][j];	2✔
69	if (prev == null \|\| prev.distance > w) {	2✔
70	table[i][j] = new APSPRecord<>(edge, w);	2✔
71	}
72	}	2✔
73	}
74	}	2✔
75
76	public static <N, E> APSPResult<N, E> findAPSP(Graph<N, E> graph, EdgeWeights<E> edgeWeights) {
77	FloydWarshallAPSP<N, E> fw = new FloydWarshallAPSP<>(graph, edgeWeights);	2✔
78	fw.findAPSP();	2✔
79	return fw;	2✔
80	}
81
82	public void findAPSP() {
83	for (int k = 0; k < size; k++) {	2✔
84
85	for (int i = 0; i < size; i++) {	2✔
86	for (int j = 0; j < size; j++) {	2✔
87	if (j == i) {	2✔
88	continue;	2✔
89	}
90
91	APSPRecord<E> currRec = table[i][j];	2✔
92
93	if (k == i \|\| k == j) {	2✔
94	continue;	2✔
95	}
96
97	APSPRecord<E> part1 = table[i][k], part2 = table[k][j];	2✔
98
99	if (part1 == null \|\| part2 == null) {	2✔
100	continue;	2✔
101	}
102
103	float dist1 = part1.distance, dist2 = part2.distance;	2✔
104	float total = dist1 + dist2;	2✔
105
106	if (currRec == null) {	2✔
107	currRec = new APSPRecord<>(total, k, part1.numEdges + part2.numEdges);	2✔
108	table[i][j] = currRec;	2✔
109	} else if (currRec.distance > total) {	2✔
110	currRec.distance = total;	2✔
111	currRec.middle = k;	2✔
112	currRec.numEdges = part1.numEdges + part2.numEdges;	2✔
113	}
114
115	}
116	}
117	}
118	}	2✔
119
120	@Override
121	public float getShortestPathDistance(N src, N tgt) {
122	int srcId = ids.getNodeId(src), tgtId = ids.getNodeId(tgt);	2✔
123
124	if (srcId == tgtId) {	2✔
125	return 0;	×
126	}
127
128	APSPRecord<E> rec = table[srcId][tgtId];	2✔
129	if (rec == null) {	2✔
130	return Graphs.INVALID_DISTANCE;	2✔
131	}
132
133	return rec.distance;	2✔
134	}
135
136	@Override
137	public @Nullable List<E> getShortestPath(N src, N tgt) {
138	int srcId = ids.getNodeId(src), tgtId = ids.getNodeId(tgt);	2✔
139
140	if (srcId == tgtId) {	2✔
141	return Collections.emptyList();	2✔
142	}
143
144	APSPRecord<E> rec = table[srcId][tgtId];	2✔
145
146	if (rec == null) {	2✔
147	return null;	2✔
148	}
149
150	List<E> result = new ArrayList<>(rec.numEdges);	2✔
151
152	buildPath(result, srcId, tgtId, rec);	2✔
153
154	return result;	2✔
155	}
156
157	@SuppressWarnings("nullness") // our initialization ensures that we don't access undefined indices
158	private void buildPath(List<E> path, int srcId, int tgtId, APSPRecord<E> rec) {
159	if (rec.middle == -1) {	2✔
160	path.add(rec.edge);	2✔
161	return;	2✔
162	}
163
164	int middle = rec.middle;	2✔
165	buildPath(path, srcId, middle, table[srcId][middle]);	2✔
166	buildPath(path, middle, tgtId, table[middle][tgtId]);	2✔
167	}	2✔
168
169	private static final class APSPRecord<E> {
170
171	public final @Nullable E edge;
172	public float distance;
173	public int middle;
174	public int numEdges;
175
176	APSPRecord(E edge, float distance) {	2✔
177	this.edge = edge;	2✔
178	this.distance = distance;	2✔
179	this.middle = -1;	2✔
180	this.numEdges = 1;	2✔
181	}	2✔
182
183	APSPRecord(float distance, int middle, int numEdges) {	2✔
184	this.edge = null;	2✔
185	this.distance = distance;	2✔
186	this.middle = middle;	2✔
187	this.numEdges = numEdges;	2✔
188	}	2✔
189	}
190	}

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