14561760799

Committed 20 Apr 2025 05:26PM UTC coverage: 53.367% (-0.04%) from 53.402%

Build # 14561760799

Build Type

push

github

Committed by

ljacqu

Commit Message

jgrapht: Bump to 1.3.0

Run Details

270 of 578 branches covered (46.71%)

729 of 1366 relevant lines covered (53.37%)

3.1 hits per line

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

80.0

/src/main/java/ch/jalu/wordeval/wordgraph/WordGraphService.java

package ch.jalu.wordeval.wordgraph;

import ch.jalu.wordeval.DataUtils;
import com.google.gson.reflect.TypeToken;
import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleGraph;

import java.lang.reflect.Type;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Service for word graphs.
 */
public final class WordGraphService {
  
  private static DataUtils dataUtils = new DataUtils();
  
  private WordGraphService() {
  }
  
  /**
   * Exports a word graph to a file as JSON.
   * @param filename the filename to write the graph to
   * @param graph the graph to store
   */
  public static void exportConnections(String filename, SimpleGraph<String, DefaultWeightedEdge> graph) {
    Map<String, List<String>> connections = convertEdgesToConnectionsMap(graph);
    dataUtils.writeToFile(filename, dataUtils.toJson(connections));
  }
  
  /**
   * Imports a graph from a JSON file.
   * @param filename the filename to read the data from
   * @return the stored graph
   */
  public static SimpleGraph<String, DefaultWeightedEdge> importConnections(String filename) {
    Type type = new TypeToken<Map<String, List<String>>>(){}.getType();
    Map<String, List<String>> connections = dataUtils.fromJson(DataUtils.readFile(filename), type);
    return convertConnectionsMapToGraph(connections);
  }
  
  /**
   * Returns the set of neighbors of the given vertex.
   * @param <V> the vertex type
   * @param <E> the edge type
   * @param graph the graph
   * @param vertex the vertex to analyze
   * @return the neighbors of the vertex in the given graph
   */
  public static <V, E> Set<V> getNeighbors(Graph<V, E> graph, V vertex) {
    if (!graph.containsVertex(vertex)) {
      return new HashSet<>();
    }
    return graph.edgesOf(vertex).stream()
      .map(edge -> getNeighbor(graph, edge, vertex))
      .collect(Collectors.toSet());
  }
  
  /**
   * Gets the neighbor of the given edge.
   * @param <V> the vertex type
   * @param <E> the edge type
   * @param graph the graph
   * @param edge the edge to process
   * @param vertex the vertex whose neighbor should be returned
   * @return the neighbor of the given vertex
   */
  private static <V, E> V getNeighbor(Graph<V, E> graph, E edge, V vertex) {
    V source = graph.getEdgeSource(edge);
    return source.equals(vertex) ? graph.getEdgeTarget(edge) : source;
  }
  
  /**
   * Returns the shortest path between two vertices as a list of vertices that have
   * to be visited.
   * @param <V> the vertex type
   * @param <E> the edge type
   * @param graph the graph
   * @param source the source vertex (start)
   * @param target the target vertex (end)
   * @return the shortest path from source to target
   */
  public static <V, E> LinkedHashSet<V> getShortestPath(Graph<V, E> graph, V source, V target) {
    if (!graph.containsVertex(source) || !graph.containsVertex(target)) {
      return new LinkedHashSet<>();
    }

    // TODO #67: Is there a better algorithm for an undirected graph?
    GraphPath<V, E> path = DijkstraShortestPath.findPathBetween(graph, source, target);
    final List<E> edges = path == null ? null : path.getEdgeList();
    if (edges == null || pathHasDisabledEdge(graph, edges)) {
      return new LinkedHashSet<>();
    }

    LinkedHashSet<V> vertices = new LinkedHashSet<>();
    vertices.add(source);
    V lastVertex = source;
    for (E edge : edges) {
      V newVertex = getNeighbor(graph, edge, lastVertex);
      vertices.add(newVertex);
      lastVertex = newVertex;
    }
    return vertices;
  }
  
  /**
   * Sets all edges of the given vertex to a weight of infinite.
   * They will be avoided in a shortest path query, unless it is
   * impossible not to traverse any edge with such a weight.
   * @param <V> the vertex class
   * @param <E> the edge class
   * @param graph the graph
   * @param vertex the vertex to disable
   * @return {@code true} if the vertex exists, {@code false} otherwise
   */
  public static <V, E> boolean disableVertexEdges(SimpleGraph<V, E> graph, V vertex) {
    return setWeightForAllEdges(graph, vertex, Double.POSITIVE_INFINITY);
  }
  
  /**
   * Sets the weight of the given vertex' edges to the default of 1.
   * @param <V> the vertex class
   * @param <E> the edge class
   * @param graph the graph
   * @param vertex the vertex to enable
   * @return {@code true} if the vertex exists, {@code false} otherwise
   */
  public static <V, E> boolean enableVertexEdges(SimpleGraph<V, E> graph, V vertex) {
    return setWeightForAllEdges(graph, vertex, 1);
  }
  
  private static <V, E> boolean setWeightForAllEdges(SimpleGraph<V, E> graph, V vertex, double weight) {
    if (!graph.containsVertex(vertex)) {
      return false;
    }
    for (E edge : graph.edgesOf(vertex)) {
      graph.setEdgeWeight(edge, weight);
    }
    return true;
  }
  
  /**
   * Checks if the list of edges traverses an edge with infinite weight.
   * @param <V> the vertex class
   * @param <E> the edge class
   * @param graph the graph
   * @param edges the list of vertices (the path) to verify
   * @return {@code true} if an edge has infinite weight, {@code false} otherwise
   */
  public static <V, E> boolean pathHasDisabledEdge(Graph<V, E> graph, Collection<E> edges) {
    return edges.stream()
      .anyMatch(edge -> Double.isInfinite(graph.getEdgeWeight(edge)));
  }
  
  private static <V, E> Map<V, List<V>> convertEdgesToConnectionsMap(Graph<V, E> graph) {
    Map<V, List<V>> connections = new HashMap<>();
    for (E edge : graph.edgeSet()) {
      V source = graph.getEdgeSource(edge);
      V target = graph.getEdgeTarget(edge);
      connections.putIfAbsent(source, new ArrayList<>());
      connections.get(source).add(target);
    }
    return connections;
  }
  
  private static <V> SimpleGraph<V, DefaultWeightedEdge> convertConnectionsMapToGraph(Map<V, List<V>> connections) {
    SimpleGraph<V, DefaultWeightedEdge> graph = new SimpleGraph<>(DefaultWeightedEdge.class);
    for (Map.Entry<V, List<V>> entry : connections.entrySet()) {
      graph.addVertex(entry.getKey());
      entry.getValue().stream()
        .peek(graph::addVertex)
        .forEach(rightWord -> graph.addEdge(entry.getKey(), rightWord));
    }
    return graph;
  }

}

1	package ch.jalu.wordeval.wordgraph;
2
3	import ch.jalu.wordeval.DataUtils;
4	import com.google.gson.reflect.TypeToken;
5	import org.jgrapht.Graph;
6	import org.jgrapht.GraphPath;
7	import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
8	import org.jgrapht.graph.DefaultWeightedEdge;
9	import org.jgrapht.graph.SimpleGraph;
10
11	import java.lang.reflect.Type;
12	import java.util.ArrayList;
13	import java.util.Collection;
14	import java.util.HashMap;
15	import java.util.HashSet;
16	import java.util.LinkedHashSet;
17	import java.util.List;
18	import java.util.Map;
19	import java.util.Set;
20	import java.util.stream.Collectors;
21
22	/**
23	* Service for word graphs.
24	*/
25	public final class WordGraphService {
26
27	private static DataUtils dataUtils = new DataUtils();	5✔
28
29	private WordGraphService() {
30	}
31
32	/**
33	* Exports a word graph to a file as JSON.
34	* @param filename the filename to write the graph to
35	* @param graph the graph to store
36	*/
37	public static void exportConnections(String filename, SimpleGraph<String, DefaultWeightedEdge> graph) {
38	Map<String, List<String>> connections = convertEdgesToConnectionsMap(graph);	3✔
39	dataUtils.writeToFile(filename, dataUtils.toJson(connections));	6✔
40	}	1✔
41
42	/**
43	* Imports a graph from a JSON file.
44	* @param filename the filename to read the data from
45	* @return the stored graph
46	*/
47	public static SimpleGraph<String, DefaultWeightedEdge> importConnections(String filename) {
48	Type type = new TypeToken<Map<String, List<String>>>(){}.getType();	×
49	Map<String, List<String>> connections = dataUtils.fromJson(DataUtils.readFile(filename), type);	×
50	return convertConnectionsMapToGraph(connections);	×
51	}
52
53	/**
54	* Returns the set of neighbors of the given vertex.
55	* @param <V> the vertex type
56	* @param <E> the edge type
57	* @param graph the graph
58	* @param vertex the vertex to analyze
59	* @return the neighbors of the vertex in the given graph
60	*/
61	public static <V, E> Set<V> getNeighbors(Graph<V, E> graph, V vertex) {
62	if (!graph.containsVertex(vertex)) {	4✔
63	return new HashSet<>();	4✔
64	}
65	return graph.edgesOf(vertex).stream()	8✔
66	.map(edge -> getNeighbor(graph, edge, vertex))	6✔
67	.collect(Collectors.toSet());	3✔
68	}
69
70	/**
71	* Gets the neighbor of the given edge.
72	* @param <V> the vertex type
73	* @param <E> the edge type
74	* @param graph the graph
75	* @param edge the edge to process
76	* @param vertex the vertex whose neighbor should be returned
77	* @return the neighbor of the given vertex
78	*/
79	private static <V, E> V getNeighbor(Graph<V, E> graph, E edge, V vertex) {
80	V source = graph.getEdgeSource(edge);	4✔
81	return source.equals(vertex) ? graph.getEdgeTarget(edge) : source;	10✔
82	}
83
84	/**
85	* Returns the shortest path between two vertices as a list of vertices that have
86	* to be visited.
87	* @param <V> the vertex type
88	* @param <E> the edge type
89	* @param graph the graph
90	* @param source the source vertex (start)
91	* @param target the target vertex (end)
92	* @return the shortest path from source to target
93	*/
94	public static <V, E> LinkedHashSet<V> getShortestPath(Graph<V, E> graph, V source, V target) {
95	if (!graph.containsVertex(source) \|\| !graph.containsVertex(target)) {	8✔
96	return new LinkedHashSet<>();	4✔
97	}
98
99	// TODO #67: Is there a better algorithm for an undirected graph?
100	GraphPath<V, E> path = DijkstraShortestPath.findPathBetween(graph, source, target);	5✔
101	final List<E> edges = path == null ? null : path.getEdgeList();	7✔
102	if (edges == null \|\| pathHasDisabledEdge(graph, edges)) {	6!
103	return new LinkedHashSet<>();	4✔
104	}
105
106	LinkedHashSet<V> vertices = new LinkedHashSet<>();	4✔
107	vertices.add(source);	4✔
108	V lastVertex = source;	2✔
109	for (E edge : edges) {	9✔
110	V newVertex = getNeighbor(graph, edge, lastVertex);	5✔
111	vertices.add(newVertex);	4✔
112	lastVertex = newVertex;	2✔
113	}	1✔
114	return vertices;	2✔
115	}
116
117	/**
118	* Sets all edges of the given vertex to a weight of infinite.
119	* They will be avoided in a shortest path query, unless it is
120	* impossible not to traverse any edge with such a weight.
121	* @param <V> the vertex class
122	* @param <E> the edge class
123	* @param graph the graph
124	* @param vertex the vertex to disable
125	* @return {@code true} if the vertex exists, {@code false} otherwise
126	*/
127	public static <V, E> boolean disableVertexEdges(SimpleGraph<V, E> graph, V vertex) {
128	return setWeightForAllEdges(graph, vertex, Double.POSITIVE_INFINITY);	5✔
129	}
130
131	/**
132	* Sets the weight of the given vertex' edges to the default of 1.
133	* @param <V> the vertex class
134	* @param <E> the edge class
135	* @param graph the graph
136	* @param vertex the vertex to enable
137	* @return {@code true} if the vertex exists, {@code false} otherwise
138	*/
139	public static <V, E> boolean enableVertexEdges(SimpleGraph<V, E> graph, V vertex) {
140	return setWeightForAllEdges(graph, vertex, 1);	5✔
141	}
142
143	private static <V, E> boolean setWeightForAllEdges(SimpleGraph<V, E> graph, V vertex, double weight) {
144	if (!graph.containsVertex(vertex)) {	4✔
145	return false;	2✔
146	}
147	for (E edge : graph.edgesOf(vertex)) {	11✔
148	graph.setEdgeWeight(edge, weight);	4✔
149	}	1✔
150	return true;	2✔
151	}
152
153	/**
154	* Checks if the list of edges traverses an edge with infinite weight.
155	* @param <V> the vertex class
156	* @param <E> the edge class
157	* @param graph the graph
158	* @param edges the list of vertices (the path) to verify
159	* @return {@code true} if an edge has infinite weight, {@code false} otherwise
160	*/
161	public static <V, E> boolean pathHasDisabledEdge(Graph<V, E> graph, Collection<E> edges) {
162	return edges.stream()	5✔
163	.anyMatch(edge -> Double.isInfinite(graph.getEdgeWeight(edge)));	6✔
164	}
165
166	private static <V, E> Map<V, List<V>> convertEdgesToConnectionsMap(Graph<V, E> graph) {
167	Map<V, List<V>> connections = new HashMap<>();	4✔
168	for (E edge : graph.edgeSet()) {	10✔
169	V source = graph.getEdgeSource(edge);	4✔
170	V target = graph.getEdgeTarget(edge);	4✔
171	connections.putIfAbsent(source, new ArrayList<>());	7✔
172	connections.get(source).add(target);	7✔
173	}	1✔
174	return connections;	2✔
175	}
176
177	private static <V> SimpleGraph<V, DefaultWeightedEdge> convertConnectionsMapToGraph(Map<V, List<V>> connections) {
178	SimpleGraph<V, DefaultWeightedEdge> graph = new SimpleGraph<>(DefaultWeightedEdge.class);	×
179	for (Map.Entry<V, List<V>> entry : connections.entrySet()) {	×
180	graph.addVertex(entry.getKey());	×
181	entry.getValue().stream()	×
182	.peek(graph::addVertex)	×
183	.forEach(rightWord -> graph.addEdge(entry.getKey(), rightWord));	×
184	}	×
185	return graph;	×
186	}
187
188	}

ljacqu / wordeval / 14561760799

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