diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java')
| -rw-r--r-- | BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java | 86 |
1 files changed, 36 insertions, 50 deletions
diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java index 66fe580..70fb555 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java @@ -22,25 +22,24 @@ import bjc.utils.funcdata.IMap; * @author ben * * @param <T> - * The label for vertices + * The label for vertices */ public class Graph<T> { /** * Create a graph from a list of edges * * @param <E> - * The type of data stored in the edges + * The type of data stored in the edges * * @param edges - * The list of edges to build from + * The list of edges to build from * @return A graph built from the provided edge-list */ public static <E> Graph<E> fromEdgeList(List<Edge<E>> edges) { Graph<E> g = new Graph<>(); edges.forEach(edge -> { - g.addEdge(edge.getSource(), edge.getTarget(), - edge.getDistance(), true); + g.addEdge(edge.getSource(), edge.getTarget(), edge.getDistance(), true); }); return g; @@ -62,29 +61,26 @@ public class Graph<T> { * Add a edge to the graph * * @param source - * The source vertex for this edge + * The source vertex for this edge * @param target - * The target vertex for this edge + * The target vertex for this edge * @param distance - * The distance from the source vertex to the target vertex + * The distance from the source vertex to the target + * vertex * @param directed - * Whether or not + * Whether or not */ - public void addEdge(T source, T target, int distance, - boolean directed) { + public void addEdge(T source, T target, int distance, boolean directed) { // Can't add edges with a null source or target if (source == null) { - throw new NullPointerException( - "The source vertex cannot be null"); + throw new NullPointerException("The source vertex cannot be null"); } else if (target == null) { - throw new NullPointerException( - "The target vertex cannot be null"); + throw new NullPointerException("The target vertex cannot be null"); } // Initialize adjacency list for vertices if necessary if (!backing.containsKey(source)) { - backing.put(source, - new FunctionalMap<T, Integer>()); + backing.put(source, new FunctionalMap<T, Integer>()); } // Add the edge to the graph @@ -93,8 +89,7 @@ public class Graph<T> { // Handle possible directed edges if (!directed) { if (!backing.containsKey(target)) { - backing.put(target, - new FunctionalMap<T, Integer>()); + backing.put(target, new FunctionalMap<T, Integer>()); } backing.get(target).put(source, distance); @@ -106,15 +101,13 @@ public class Graph<T> { * conditions * * @param source - * The vertex to test edges for + * The vertex to test edges for * @param matcher - * The conditions an edge must match + * The conditions an edge must match * @param action - * The action to execute for matching edges + * The action to execute for matching edges */ - public void forAllEdgesMatchingAt(T source, - BiPredicate<T, Integer> matcher, - BiConsumer<T, Integer> action) { + public void forAllEdgesMatchingAt(T source, BiPredicate<T, Integer> matcher, BiConsumer<T, Integer> action) { if (matcher == null) { throw new NullPointerException("Matcher must not be null"); } else if (action == null) { @@ -132,7 +125,7 @@ public class Graph<T> { * Get all the edges that begin at a particular source vertex * * @param source - * The vertex to use as a source + * The vertex to use as a source * @return All of the edges with the specified vertex as a source */ public IMap<T, Integer> getEdges(T source) { @@ -140,8 +133,7 @@ public class Graph<T> { if (source == null) { throw new NullPointerException("The source cannot be null."); } else if (!backing.containsKey(source)) { - throw new IllegalArgumentException( - "Vertex " + source + " is not in graph"); + throw new IllegalArgumentException("Vertex " + source + " is not in graph"); } return backing.get(source); @@ -159,7 +151,8 @@ public class Graph<T> { /** * Uses Prim's algorothm to calculate a MST for the graph. * - * If the graph is non-connected, this will lead to unpredictable results. + * If the graph is non-connected, this will lead to unpredictable + * results. * * @return a list of edges that constitute the MST */ @@ -183,19 +176,17 @@ public class Graph<T> { while (visited.size() != getVertexCount()) { // Grab all edges adjacent to the provided edge - forAllEdgesMatchingAt(source.getValue(), - (target, weight) -> { - return !visited.contains(target); - }, (target, weight) -> { - available.add(new Edge<>( - source.unwrap(vertex -> vertex), - target, weight)); - }); + forAllEdgesMatchingAt(source.getValue(), (target, weight) -> { + return !visited.contains(target); + }, (target, weight) -> { + available.add(new Edge<>(source.unwrap(vertex -> vertex), target, weight)); + }); // Get the edge with the minimum distance IHolder<Edge<T>> minimum = new Identity<>(available.poll()); - // Only consider edges where we haven't visited the target of + // Only consider edges where we haven't visited the + // target of // the edge while (visited.contains(minimum.getValue())) { minimum.transform((edge) -> available.poll()); @@ -236,29 +227,25 @@ public class Graph<T> { * Remove the edge starting at the source and ending at the target * * @param source - * The source vertex for the edge + * The source vertex for the edge * @param target - * The target vertex for the edge + * The target vertex for the edge */ public void removeEdge(T source, T target) { // Can't remove things w/ null vertices if (source == null) { - throw new NullPointerException( - "The source vertex cannot be null"); + throw new NullPointerException("The source vertex cannot be null"); } else if (target == null) { - throw new NullPointerException( - "The target vertex cannot be null"); + throw new NullPointerException("The target vertex cannot be null"); } // Can't remove if one vertice doesn't exists if (!backing.containsKey(source)) { - throw new NoSuchElementException( - "vertex " + source + " does not exist."); + throw new NoSuchElementException("vertex " + source + " does not exist."); } if (!backing.containsKey(target)) { - throw new NoSuchElementException( - "vertex " + target + " does not exist."); + throw new NoSuchElementException("vertex " + target + " does not exist."); } backing.get(source).remove(target); @@ -273,8 +260,7 @@ public class Graph<T> { * @return A adjacency map representing this graph */ public AdjacencyMap<T> toAdjacencyMap() { - AdjacencyMap<T> adjacency = new AdjacencyMap<>( - backing.keyList()); + AdjacencyMap<T> adjacency = new AdjacencyMap<>(backing.keyList()); backing.forEach((sourceKey, sourceValue) -> { sourceValue.forEach((targetKey, targetValue) -> { |