From 8923edffdb36b790014ff47301e53f7ede93ea0d Mon Sep 17 00:00:00 2001 From: "Benjamin J. Culkin" Date: Wed, 11 Oct 2017 22:49:16 -0300 Subject: Cleanup more --- .../main/java/bjc/utils/graph/AdjacencyMap.java | 77 ++++++---- base/src/main/java/bjc/utils/graph/Edge.java | 50 ++++--- base/src/main/java/bjc/utils/graph/Graph.java | 160 ++++++++++++--------- 3 files changed, 166 insertions(+), 121 deletions(-) (limited to 'base/src/main/java/bjc/utils/graph') diff --git a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java index 446ab5b..58ce107 100644 --- a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java +++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java @@ -20,20 +20,22 @@ import bjc.utils.funcutils.FuncUtils; * @author ben * * @param - * The type of the nodes in the graph + * The type of the nodes in the graph */ public class AdjacencyMap { /** * Create an adjacency map from a stream of text * * @param stream - * The stream of text to read in - * @return An adjacency map defined by the text + * The stream of text to read in + * + * @return + * An adjacency map defined by the text */ public static AdjacencyMap fromStream(final InputStream stream) { if (stream == null) throw new NullPointerException("Input source must not be null"); - // Create the adjacency map + /* Create the adjacency map. */ AdjacencyMap adjacency; try (Scanner input = new Scanner(stream)) { @@ -44,12 +46,14 @@ public class AdjacencyMap { final String possible = input.next(); try { - // First, read in number of vertices + /* First, read in number of vertices. */ vertexCount = Integer.parseInt(possible); } catch (final NumberFormatException nfex) { - final InputMismatchException imex = new InputMismatchException( - "The first line must contain the number of vertices. " + possible - + " is not a valid number"); + String msg = String.format( + "The first line must contain the number of vertices. %s is not a valid number", + possible); + + final InputMismatchException imex = new InputMismatchException(msg); imex.initCause(nfex); @@ -75,12 +79,16 @@ public class AdjacencyMap { return adjacency; } + /* Read a row of edges. */ private static void readRow(final AdjacencyMap adjacency, final int vertexCount, final IHolder row, final String strang) { final String[] parts = strang.split(" "); - if (parts.length != vertexCount) - throw new InputMismatchException("Must specify a weight for all " + vertexCount + " vertices"); + if (parts.length != vertexCount) { + String msg = String.format("Must specify a weight for all %d vertices", vertexCount); + + throw new InputMismatchException(msg); + } int column = 0; @@ -90,9 +98,9 @@ public class AdjacencyMap { try { weight = Integer.parseInt(part); } catch (final NumberFormatException nfex) { - final InputMismatchException imex = new InputMismatchException( - "" + part + " is not a valid weight."); + String msg = String.format("%d is not a valid weight.", part); + final InputMismatchException imex = new InputMismatchException(); imex.initCause(nfex); throw imex; @@ -106,16 +114,14 @@ public class AdjacencyMap { row.transform((rowNumber) -> rowNumber + 1); } - /** - * The backing storage of the map - */ + /** The backing storage of the map */ private final IMap> adjacency = new FunctionalMap<>(); /** * Create a new map from a set of vertices * * @param vertices - * The set of vertices to create a map from + * The set of vertices to create a map from */ public AdjacencyMap(final IList vertices) { if (vertices == null) throw new NullPointerException("Vertices must not be null"); @@ -134,7 +140,8 @@ public class AdjacencyMap { /** * Check if the graph is directed * - * @return Whether or not the graph is directed + * @return + * Whether or not the graph is directed */ public boolean isDirected() { final IHolder result = new Identity<>(true); @@ -153,32 +160,40 @@ public class AdjacencyMap { } /** - * Set the weight of an edge + * Set the weight of an edge. * * @param source - * The source node of the edge + * The source node of the edge. * @param target - * The target node of the edge + * The target node of the edge. * @param weight - * The weight of the edge + * The weight of the edge. */ public void setWeight(final T source, final T target, final int weight) { - if (source == null) + if (source == null) { throw new NullPointerException("Source vertex must not be null"); - else if (target == null) throw new NullPointerException("Target vertex must not be null"); + } else if (target == null) { + throw new NullPointerException("Target vertex must not be null"); + } + + if (!adjacency.containsKey(source)) { + String msg = String.format("Source vertex %s isn't present in map", source); - if (!adjacency.containsKey(source)) - throw new IllegalArgumentException("Source vertex " + source + " isn't present in map"); - else if (!adjacency.containsKey(target)) - throw new IllegalArgumentException("Target vertex " + target + " isn't present in map"); + throw new IllegalArgumentException(msg); + } else if (!adjacency.containsKey(target)) { + String msg = String.format("Target vertex %s isn't present in map", target); + + throw new IllegalArgumentException(msg); + } adjacency.get(source).put(target, weight); } /** - * Convert this to a different graph representation + * Convert this to a different graph representation. * - * @return The new representation of this graph + * @return + * The new representation of this graph. */ public Graph toGraph() { final Graph ret = new Graph<>(); @@ -193,10 +208,10 @@ public class AdjacencyMap { } /** - * Convert an adjacency map back into a stream + * Convert an adjacency map back into a stream. * * @param sink - * The stream to convert to + * The stream to convert to. */ public void toStream(final OutputStream sink) { if (sink == null) throw new NullPointerException("Output source must not be null"); diff --git a/base/src/main/java/bjc/utils/graph/Edge.java b/base/src/main/java/bjc/utils/graph/Edge.java index 0152e3d..9236464 100644 --- a/base/src/main/java/bjc/utils/graph/Edge.java +++ b/base/src/main/java/bjc/utils/graph/Edge.java @@ -1,38 +1,38 @@ package bjc.utils.graph; /** - * An edge in a weighted graph + * An edge in a weighted graph. * * @author ben * * @param - * The type of the nodes in the graph + * The type of the nodes in the graph. */ public class Edge { - /* - * The distance from initial to terminal node - */ + /* The distance from initial to terminal node. */ private final int distance; - /* - * The initial and terminal nodes of this edge - */ + /* The initial and terminal nodes of this edge. */ private final T source, target; /** - * Create a new edge with set parameters + * Create a new edge with set parameters. * * @param initial - * The initial node of the edge + * The initial node of the edge. + * * @param terminal - * The terminal node of the edge + * The terminal node of the edge. + * * @param distance - * The distance between initial and terminal edge + * The distance between initial and terminal edge. */ public Edge(final T initial, final T terminal, final int distance) { - if (initial == null) + if (initial == null) { throw new NullPointerException("Initial node must not be null"); - else if (terminal == null) throw new NullPointerException("Terminal node must not be null"); + } else if (terminal == null) { + throw new NullPointerException("Terminal node must not be null"); + } this.source = initial; this.target = terminal; @@ -65,28 +65,31 @@ public class Edge { } /** - * Get the distance in this edge + * Get the distance in this edge. * - * @return The distance between the initial and terminal nodes of this - * edge + * @return + * The distance between the initial and terminal nodes of this + * edge. */ public int getDistance() { return distance; } /** - * Get the initial node of an edge + * Get the initial node of an edge. * - * @return The initial node of this edge + * @return + * The initial node of this edge. */ public T getSource() { return source; } /** - * Get the target node of an edge + * Get the target node of an edge. * - * @return The target node of this edge + * @return + * The target node of this edge. */ public T getTarget() { return target; @@ -107,6 +110,9 @@ public class Edge { @Override public String toString() { - return " first vertex " + source + " to vertex " + target + " with distance: " + distance; + String msg = String.format("source vertex %s to target vertex %s with distance: %s", + source, target, distance); + + return msg; } } diff --git a/base/src/main/java/bjc/utils/graph/Graph.java b/base/src/main/java/bjc/utils/graph/Graph.java index 280a7f5..3e03919 100644 --- a/base/src/main/java/bjc/utils/graph/Graph.java +++ b/base/src/main/java/bjc/utils/graph/Graph.java @@ -17,23 +17,25 @@ import bjc.utils.funcdata.IList; import bjc.utils.funcdata.IMap; /** - * A directed weighted graph, where the vertices have some arbitrary label + * A directed weighted graph, where the vertices have some arbitrary label. * * @author ben * * @param - * The label for vertices + * The label for vertices. */ public class Graph { /** - * Create a graph from a list of edges + * Create a graph from a list of edges. * * @param - * 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 - * @return A graph built from the provided edge-list + * The list of edges to build from. + * + * @return + * A graph built from the provided edge-list. */ public static Graph fromEdgeList(final List> edges) { final Graph g = new Graph<>(); @@ -45,46 +47,46 @@ public class Graph { return g; } - /** - * The backing representation of the graph - */ + /** The backing representation of the graph. */ private final IMap> backing; - /** - * Create a new graph - */ + /** Create a new empty graph. */ public Graph() { backing = new FunctionalMap<>(); } /** - * Add a edge to the graph + * 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 the edge is directed or not. */ public void addEdge(final T source, final T target, final int distance, final boolean directed) { - // Can't add edges with a null source or target - if (source == null) + /* Can't add edges with a null source or target. */ + if (source == null) { throw new NullPointerException("The source vertex cannot be null"); - else if (target == null) throw new NullPointerException("The target vertex cannot be null"); + } else if (target == null) { + throw new NullPointerException("The target vertex cannot be null"); + } - // Initialize adjacency list for vertices if necessary + /* Initialize adjacency list for vertices if necessary. */ if (!backing.containsKey(source)) { backing.put(source, new FunctionalMap()); } - // Add the edge to the graph + /* Add the edge to the graph. */ backing.get(source).put(target, distance); - // Handle possible directed edges + /* Handle possible directed edges. */ if (!directed) { if (!backing.containsKey(target)) { backing.put(target, new FunctionalMap()); @@ -96,20 +98,24 @@ public class Graph { /** * Execute an action for all edges of a specific vertex matching - * conditions + * 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(final T source, final BiPredicate matcher, final BiConsumer action) { - if (matcher == null) + if (matcher == null) { throw new NullPointerException("Matcher must not be null"); - else if (action == null) throw new NullPointerException("Action must not be null"); + } else if (action == null) { + throw new NullPointerException("Action must not be null"); + } getEdges(source).forEach((target, weight) -> { if (matcher.test(target, weight)) { @@ -119,14 +125,15 @@ public class Graph { } /** - * Get all the edges that begin at a particular source vertex + * Get all the edges that begin at a particular source vertex. * * @param source - * The vertex to use as a source - * @return All of the edges with the specified vertex as a source + * The vertex to use as a source. + * @return + * All of the edges with the specified vertex as a source. */ public IMap getEdges(final T source) { - // Can't find edges for a null source + /* Can't find edges for a null source. */ if (source == null) throw new NullPointerException("The source cannot be null."); else if (!backing.containsKey(source)) @@ -136,9 +143,10 @@ public class Graph { } /** - * Get the initial vertex of the graph + * Get the initial vertex of the graph. * - * @return The initial vertex of the graph + * @return + * The initial vertex of the graph. */ public T getInitial() { return backing.keyList().first(); @@ -150,27 +158,28 @@ public class Graph { * If the graph is non-connected, this will lead to unpredictable * results. * - * @return a list of edges that constitute the MST + * @return + * A list of edges that constitute the MST. */ public List> getMinimumSpanningTree() { - // Set of all of the currently available edges + /* Set of all of the currently available edges. */ final Queue> available = new PriorityQueue<>(10, (left, right) -> left.getDistance() - right.getDistance()); - // The MST of the graph + /* The MST of the graph. */ final List> minimums = new ArrayList<>(); - // The set of all of the visited vertices. + /* The set of all of the visited vertices. */ final Set visited = new HashSet<>(); - // Start at the initial vertex and visit it + /* Start at the initial vertex and visit it */ final IHolder source = new Identity<>(getInitial()); visited.add(source.getValue()); - // Make sure we visit all the nodes + /* Make sure we visit all the nodes. */ while (visited.size() != getVertexCount()) { - // Grab all edges adjacent to the provided edge + /* Grab all edges adjacent to the provided edge. */ forAllEdgesMatchingAt(source.getValue(), (target, weight) -> { return !visited.contains(target); @@ -180,23 +189,24 @@ public class Graph { available.add(new Edge<>(vert, target, weight)); }); - // Get the edge with the minimum distance + /* Get the edge with the minimum distance. */ final IHolder> minimum = new Identity<>(available.poll()); - // Only consider edges where we haven't visited the - // target of - // the edge + /* + * Only consider edges where we haven't visited the + * target of the edge. + */ while (visited.contains(minimum.getValue().getTarget())) { minimum.transform((edge) -> available.poll()); } - // Add it to our MST + /* Add it to our MST. */ minimums.add(minimum.getValue()); - // Advance to the next node + /* Advance to the next node. */ source.transform((vertex) -> minimum.unwrap(edge -> edge.getTarget())); - // Visit this node + /* Visit this node. */ visited.add(source.getValue()); } @@ -204,9 +214,10 @@ public class Graph { } /** - * Get the count of the vertices in this graph + * Get the count of the vertices in this graph. * - * @return A count of the vertices in this graph + * @return + * A count of the vertices in this graph. */ public int getVertexCount() { return backing.size(); @@ -215,43 +226,56 @@ public class Graph { /** * Get all of the vertices in this graph. * - * @return A unmodifiable set of all the vertices in the graph. + * @return + * A unmodifiable set of all the vertices in the graph. */ public IList getVertices() { return backing.keyList(); } /** - * Remove the edge starting at the source and ending at the target + * 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(final T source, final T target) { - // Can't remove things w/ null vertices - if (source == null) + /* Can't remove things w/ null vertices. */ + if (source == null) { throw new NullPointerException("The source vertex cannot be null"); - else if (target == null) throw new NullPointerException("The target vertex cannot be null"); + } else if (target == 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."); + /* Can't remove if one vertice doesn't exists. */ + if (!backing.containsKey(source)) { + String msg = String.format("vertex %s does not exist", source); + + throw new NoSuchElementException(msg); + } - if (!backing.containsKey(target)) - throw new NoSuchElementException("vertex " + target + " does not exist."); + if (!backing.containsKey(target)) { + String msg = String.format("vertex %s does not exist", target); + + throw new NoSuchElementException(); + } backing.get(source).remove(target); - // Uncomment this to turn the graph undirected - // graph.get(target).remove(source); + /* Uncomment this to turn the graph undirected + * + * graph.get(target).remove(source); + */ } /** - * Convert a graph into a adjacency map/matrix + * Convert a graph into a adjacency map/matrix. * - * @return A adjacency map representing this graph + * @return + * A adjacency map representing this graph. */ public AdjacencyMap toAdjacencyMap() { final AdjacencyMap adjacency = new AdjacencyMap<>(backing.keyList()); -- cgit v1.2.3