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

98.73

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

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