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

92.86

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

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

import net.automatalib.common.util.mapping.Mapping;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.graph.BidirectionalGraph;
import net.automatalib.graph.Graph;
import net.automatalib.graph.concept.EdgeWeights;
import net.automatalib.util.graph.apsp.APSPResult;
import net.automatalib.util.graph.apsp.FloydWarshallAPSP;
import net.automatalib.util.graph.scc.SCCListener;
import net.automatalib.util.graph.scc.SCCs;
import net.automatalib.util.graph.scc.TarjanSCCVisitor;
import net.automatalib.util.graph.sssp.DijkstraSSSP;
import net.automatalib.util.graph.sssp.SSSPResult;

public final class Graphs {

    /**
     * Float value to signal that no valid distance is returned (e.g., when attempting to retrieve the length of a path
     * that does not exist).
     */
    public static final float INVALID_DISTANCE = Float.NEGATIVE_INFINITY;

    private Graphs() {}

    public static <N, E> Mapping<N, Collection<E>> incomingEdges(Graph<N, E> graph) {
        if (graph instanceof BidirectionalGraph) {
            final BidirectionalGraph<N, E> bdGraph = (BidirectionalGraph<N, E>) graph;
            return bdGraph::getIncomingEdges;
        }

        MutableMapping<N, Collection<E>> inEdgesMapping = graph.createStaticNodeMapping();

        for (N node : graph) {
            Collection<E> outEdges = graph.getOutgoingEdges(node);
            for (E e : outEdges) {
                N tgt = graph.getTarget(e);
                Collection<E> inEdges = inEdgesMapping.get(tgt);
                if (inEdges == null) {
                    inEdges = new ArrayList<>();
                    inEdgesMapping.put(tgt, inEdges);
                }
                inEdges.add(e);
            }
        }

        return inEdgesMapping;
    }

    /**
     * Converts a list of edges into a corresponding list of nodes. Note that the list of nodes is always one larger
     * than the respective list of edges.
     *
     * @param edgeList
     *         the list of edges
     * @param graph
     *         the graph
     * @param init
     *         the initial node
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return the node list corresponding to the given edge list.
     */
    public static <N, E> List<N> toNodeList(List<E> edgeList, Graph<N, E> graph, N init) {
        List<N> result = new ArrayList<>(edgeList.size() + 1);
        result.add(init);

        for (E edge : edgeList) {
            N tgt = graph.getTarget(edge);
            result.add(tgt);
        }

        return result;
    }

    /**
     * Computes the shortest paths between all pairs of nodes in a graph, using the Floyd-Warshall dynamic programming
     * algorithm. Note that the result is only correct if the graph contains no cycles with negative edge weight sums.
     *
     * @param graph
     *         the graph
     * @param edgeWeights
     *         the edge weights
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return the all pairs shortest paths result
     *
     * @see FloydWarshallAPSP
     */
    public static <N, E> APSPResult<N, E> findAPSP(Graph<N, E> graph, EdgeWeights<E> edgeWeights) {
        return FloydWarshallAPSP.findAPSP(graph, edgeWeights);
    }

    /**
     * Computes the shortest paths between a single source node and all other nodes in a graph, using Dijkstra's
     * algorithm. Note that the result is only correct if the graph contains no edges with negative weights.
     *
     * @param graph
     *         the graph
     * @param init
     *         the source node
     * @param edgeWeights
     *         the edge weights
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return the single-source shortest paths result
     *
     * @see DijkstraSSSP
     */
    public static <N, E> SSSPResult<N, E> findSSSP(Graph<N, E> graph, N init, EdgeWeights<E> edgeWeights) {
        return DijkstraSSSP.findSSSP(graph, init, edgeWeights);
    }

    /**
     * Collects all strongly-connected components in a graph. The SCCs are returned as a list of lists.
     * <p>
     * Tarjan's algorithm is used for realizing the SCC search.
     *
     * @param graph
     *         the graph
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @return a list of all SCCs, each represented as a list of its nodes
     *
     * @see TarjanSCCVisitor
     * @see SCCs
     */
    public static <N, E> List<List<N>> collectSCCs(Graph<N, E> graph) {
        return SCCs.collectSCCs(graph);
    }

    /**
     * Find all strongly-connected components in a graph. When a new SCC is found, the {@link
     * SCCListener#foundSCC(java.util.Collection)} method is invoked. The listener object may hence not be null.
     * <p>
     * Tarjan's algorithm is used for realizing the SCC search.
     *
     * @param graph
     *         the graph
     * @param sccListener
     *         the SCC listener
     * @param <N>
     *         node type
     * @param <E>
     *         edge type
     *
     * @see TarjanSCCVisitor
     * @see SCCs
     */
    public static <N, E> void findSCCs(Graph<N, E> graph, SCCListener<N> sccListener) {
        SCCs.findSCCs(graph, sccListener);
    }
}

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;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.List;
21
22	import net.automatalib.common.util.mapping.Mapping;
23	import net.automatalib.common.util.mapping.MutableMapping;
24	import net.automatalib.graph.BidirectionalGraph;
25	import net.automatalib.graph.Graph;
26	import net.automatalib.graph.concept.EdgeWeights;
27	import net.automatalib.util.graph.apsp.APSPResult;
28	import net.automatalib.util.graph.apsp.FloydWarshallAPSP;
29	import net.automatalib.util.graph.scc.SCCListener;
30	import net.automatalib.util.graph.scc.SCCs;
31	import net.automatalib.util.graph.scc.TarjanSCCVisitor;
32	import net.automatalib.util.graph.sssp.DijkstraSSSP;
33	import net.automatalib.util.graph.sssp.SSSPResult;
34
35	public final class Graphs {
36
37	/**
38	* Float value to signal that no valid distance is returned (e.g., when attempting to retrieve the length of a path
39	* that does not exist).
40	*/
41	public static final float INVALID_DISTANCE = Float.NEGATIVE_INFINITY;
42
43	private Graphs() {}
44
45	public static <N, E> Mapping<N, Collection<E>> incomingEdges(Graph<N, E> graph) {
46	if (graph instanceof BidirectionalGraph) {	2✔
47	final BidirectionalGraph<N, E> bdGraph = (BidirectionalGraph<N, E>) graph;	2✔
48	return bdGraph::getIncomingEdges;	2✔
49	}
50
51	MutableMapping<N, Collection<E>> inEdgesMapping = graph.createStaticNodeMapping();	2✔
52
53	for (N node : graph) {	2✔
54	Collection<E> outEdges = graph.getOutgoingEdges(node);	2✔
55	for (E e : outEdges) {	2✔
56	N tgt = graph.getTarget(e);	2✔
57	Collection<E> inEdges = inEdgesMapping.get(tgt);	2✔
58	if (inEdges == null) {	2✔
59	inEdges = new ArrayList<>();	2✔
60	inEdgesMapping.put(tgt, inEdges);	2✔
61	}
62	inEdges.add(e);	2✔
63	}	2✔
64	}	2✔
65
66	return inEdgesMapping;	2✔
67	}
68
69	/**
70	* Converts a list of edges into a corresponding list of nodes. Note that the list of nodes is always one larger
71	* than the respective list of edges.
72	*
73	* @param edgeList
74	* the list of edges
75	* @param graph
76	* the graph
77	* @param init
78	* the initial node
79	* @param <N>
80	* node type
81	* @param <E>
82	* edge type
83	*
84	* @return the node list corresponding to the given edge list.
85	*/
86	public static <N, E> List<N> toNodeList(List<E> edgeList, Graph<N, E> graph, N init) {
87	List<N> result = new ArrayList<>(edgeList.size() + 1);	2✔
88	result.add(init);	2✔
89
90	for (E edge : edgeList) {	2✔
91	N tgt = graph.getTarget(edge);	2✔
92	result.add(tgt);	2✔
93	}	2✔
94
95	return result;	2✔
96	}
97
98	/**
99	* Computes the shortest paths between all pairs of nodes in a graph, using the Floyd-Warshall dynamic programming
100	* algorithm. Note that the result is only correct if the graph contains no cycles with negative edge weight sums.
101	*
102	* @param graph
103	* the graph
104	* @param edgeWeights
105	* the edge weights
106	* @param <N>
107	* node type
108	* @param <E>
109	* edge type
110	*
111	* @return the all pairs shortest paths result
112	*
113	* @see FloydWarshallAPSP
114	*/
115	public static <N, E> APSPResult<N, E> findAPSP(Graph<N, E> graph, EdgeWeights<E> edgeWeights) {
116	return FloydWarshallAPSP.findAPSP(graph, edgeWeights);	2✔
117	}
118
119	/**
120	* Computes the shortest paths between a single source node and all other nodes in a graph, using Dijkstra's
121	* algorithm. Note that the result is only correct if the graph contains no edges with negative weights.
122	*
123	* @param graph
124	* the graph
125	* @param init
126	* the source node
127	* @param edgeWeights
128	* the edge weights
129	* @param <N>
130	* node type
131	* @param <E>
132	* edge type
133	*
134	* @return the single-source shortest paths result
135	*
136	* @see DijkstraSSSP
137	*/
138	public static <N, E> SSSPResult<N, E> findSSSP(Graph<N, E> graph, N init, EdgeWeights<E> edgeWeights) {
139	return DijkstraSSSP.findSSSP(graph, init, edgeWeights);	2✔
140	}
141
142	/**
143	* Collects all strongly-connected components in a graph. The SCCs are returned as a list of lists.
144	* <p>
145	* Tarjan's algorithm is used for realizing the SCC search.
146	*
147	* @param graph
148	* the graph
149	* @param <N>
150	* node type
151	* @param <E>
152	* edge type
153	*
154	* @return a list of all SCCs, each represented as a list of its nodes
155	*
156	* @see TarjanSCCVisitor
157	* @see SCCs
158	*/
159	public static <N, E> List<List<N>> collectSCCs(Graph<N, E> graph) {
160	return SCCs.collectSCCs(graph);	2✔
161	}
162
163	/**
164	* Find all strongly-connected components in a graph. When a new SCC is found, the {@link
165	* SCCListener#foundSCC(java.util.Collection)} method is invoked. The listener object may hence not be null.
166	* <p>
167	* Tarjan's algorithm is used for realizing the SCC search.
168	*
169	* @param graph
170	* the graph
171	* @param sccListener
172	* the SCC listener
173	* @param <N>
174	* node type
175	* @param <E>
176	* edge type
177	*
178	* @see TarjanSCCVisitor
179	* @see SCCs
180	*/
181	public static <N, E> void findSCCs(Graph<N, E> graph, SCCListener<N> sccListener) {
182	SCCs.findSCCs(graph, sccListener);	×
183	}	×
184	}

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