diff options
| author | bjculkin <bjculkin@mix.wvu.edu> | 2018-02-12 22:45:04 -0500 |
|---|---|---|
| committer | bjculkin <bjculkin@mix.wvu.edu> | 2018-02-12 22:45:04 -0500 |
| commit | df94066e3af02ff02d5ab4d033a3d603f743234c (patch) | |
| tree | 168a1edaf58d386c175ffb601e9d4da8e13d31e2 /base/src/main/java/bjc/utils/graph | |
| parent | ae51c587c53f7ca311e556e3cbd0c5566d6c2843 (diff) | |
Formatting pass
Diffstat (limited to 'base/src/main/java/bjc/utils/graph')
| -rw-r--r-- | base/src/main/java/bjc/utils/graph/AdjacencyMap.java | 53 | ||||
| -rw-r--r-- | base/src/main/java/bjc/utils/graph/Edge.java | 49 | ||||
| -rw-r--r-- | base/src/main/java/bjc/utils/graph/Graph.java | 84 |
3 files changed, 87 insertions, 99 deletions
diff --git a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java index 1598b25..965eccc 100644 --- a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java +++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java @@ -20,25 +20,24 @@ import bjc.utils.funcutils.FuncUtils; * @author ben * * @param <T> - * The type of the nodes in the graph + * The type of the nodes in the graph */ public class AdjacencyMap<T> { /** * Create an adjacency map from a stream of text * * @param stream - * The stream of text to read in + * The stream of text to read in * - * @return - * An adjacency map defined by the text + * @return An adjacency map defined by the text */ public static AdjacencyMap<Integer> fromStream(final InputStream stream) { - if (stream == null) throw new NullPointerException("Input source must not be null"); + if(stream == null) throw new NullPointerException("Input source must not be null"); /* Create the adjacency map. */ AdjacencyMap<Integer> adjacency; - try (Scanner input = new Scanner(stream)) { + try(Scanner input = new Scanner(stream)) { input.useDelimiter("\n"); int vertexCount; @@ -48,8 +47,8 @@ public class AdjacencyMap<T> { try { /* First, read in number of vertices. */ vertexCount = Integer.parseInt(possible); - } catch (final NumberFormatException nfex) { - String msg = String.format( + } catch(final NumberFormatException nfex) { + String msg = String.format( "The first line must contain the number of vertices. %s is not a valid number", possible); @@ -60,7 +59,7 @@ public class AdjacencyMap<T> { throw imex; } - if (vertexCount <= 0) + if(vertexCount <= 0) throw new InputMismatchException("The number of vertices must be greater than 0"); final IList<Integer> vertices = new FunctionalList<>(); @@ -84,7 +83,7 @@ public class AdjacencyMap<T> { final IHolder<Integer> row, final String strang) { final String[] parts = strang.split(" "); - if (parts.length != vertexCount) { + if(parts.length != vertexCount) { String msg = String.format("Must specify a weight for all %d vertices", vertexCount); throw new InputMismatchException(msg); @@ -92,12 +91,12 @@ public class AdjacencyMap<T> { int column = 0; - for (final String part : parts) { + for(final String part : parts) { int weight; try { weight = Integer.parseInt(part); - } catch (final NumberFormatException nfex) { + } catch(final NumberFormatException nfex) { String msg = String.format("%d is not a valid weight.", part); final InputMismatchException imex = new InputMismatchException(msg); @@ -121,10 +120,10 @@ public class AdjacencyMap<T> { * 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<T> vertices) { - if (vertices == null) throw new NullPointerException("Vertices must not be null"); + if(vertices == null) throw new NullPointerException("Vertices must not be null"); vertices.forEach(vertex -> { final IMap<T, Integer> row = new FunctionalMap<>(); @@ -140,8 +139,7 @@ public class AdjacencyMap<T> { /** * 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<Boolean> result = new Identity<>(true); @@ -150,7 +148,7 @@ public class AdjacencyMap<T> { sourceValue.forEach((targetKey, targetValue) -> { final int inverseValue = adjacency.get(targetKey).get(sourceKey); - if (targetValue != inverseValue) { + if(targetValue != inverseValue) { result.replace(false); } }); @@ -163,24 +161,24 @@ public class AdjacencyMap<T> { * 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) { + } else if(target == null) { throw new NullPointerException("Target vertex must not be null"); } - if (!adjacency.containsKey(source)) { + if(!adjacency.containsKey(source)) { String msg = String.format("Source vertex %s isn't present in map", source); throw new IllegalArgumentException(msg); - } else if (!adjacency.containsKey(target)) { + } else if(!adjacency.containsKey(target)) { String msg = String.format("Target vertex %s isn't present in map", target); throw new IllegalArgumentException(msg); @@ -192,8 +190,7 @@ public class AdjacencyMap<T> { /** * Convert this to a different graph representation. * - * @return - * The new representation of this graph. + * @return The new representation of this graph. */ public Graph<T> toGraph() { final Graph<T> ret = new Graph<>(); @@ -211,10 +208,10 @@ public class AdjacencyMap<T> { * 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"); + if(sink == null) throw new NullPointerException("Output source must not be null"); final PrintStream outputPrinter = new PrintStream(sink); diff --git a/base/src/main/java/bjc/utils/graph/Edge.java b/base/src/main/java/bjc/utils/graph/Edge.java index 9236464..e7e7b36 100644 --- a/base/src/main/java/bjc/utils/graph/Edge.java +++ b/base/src/main/java/bjc/utils/graph/Edge.java @@ -6,10 +6,10 @@ package bjc.utils.graph; * @author ben * * @param <T> - * The type of the nodes in the graph. + * The type of the nodes in the graph. */ public class Edge<T> { - /* 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. */ @@ -19,18 +19,18 @@ public class Edge<T> { * 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) { + } else if(terminal == null) { throw new NullPointerException("Terminal node must not be null"); } @@ -41,24 +41,24 @@ public class Edge<T> { @Override public boolean equals(final Object obj) { - if (this == obj) + if(this == obj) return true; - else if (obj == null) + else if(obj == null) return false; - else if (getClass() != obj.getClass()) + else if(getClass() != obj.getClass()) return false; else { final Edge<?> other = (Edge<?>) obj; - if (distance != other.distance) + if(distance != other.distance) return false; - else if (source == null) { - if (other.source != null) return false; - } else if (!source.equals(other.source)) + else if(source == null) { + if(other.source != null) return false; + } else if(!source.equals(other.source)) return false; - else if (target == null) { - if (other.target != null) return false; - } else if (!target.equals(other.target)) return false; + else if(target == null) { + if(other.target != null) return false; + } else if(!target.equals(other.target)) return false; return true; } @@ -67,9 +67,8 @@ public class Edge<T> { /** * 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; @@ -78,8 +77,7 @@ public class Edge<T> { /** * 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; @@ -88,8 +86,7 @@ public class Edge<T> { /** * 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; @@ -110,8 +107,8 @@ public class Edge<T> { @Override public String toString() { - String msg = String.format("source vertex %s to target vertex %s with distance: %s", - source, target, 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 d00dbae..83c2dc2 100644 --- a/base/src/main/java/bjc/utils/graph/Graph.java +++ b/base/src/main/java/bjc/utils/graph/Graph.java @@ -22,20 +22,19 @@ 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. + * @return A graph built from the provided edge-list. */ public static <E> Graph<E> fromEdgeList(final List<Edge<E>> edges) { final Graph<E> g = new Graph<>(); @@ -59,27 +58,27 @@ 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 the edge is directed 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) { + if(source == null) { throw new NullPointerException("The source vertex cannot be null"); - } else if (target == null) { + } else if(target == null) { throw new NullPointerException("The target vertex cannot be null"); } /* Initialize adjacency list for vertices if necessary. */ - if (!backing.containsKey(source)) { + if(!backing.containsKey(source)) { backing.put(source, new FunctionalMap<T, Integer>()); } @@ -87,8 +86,8 @@ public class Graph<T> { backing.get(source).put(target, distance); /* Handle possible directed edges. */ - if (!directed) { - if (!backing.containsKey(target)) { + if(!directed) { + if(!backing.containsKey(target)) { backing.put(target, new FunctionalMap<T, Integer>()); } @@ -101,24 +100,24 @@ 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(final T source, final BiPredicate<T, Integer> matcher, final BiConsumer<T, Integer> action) { - if (matcher == null) { + if(matcher == null) { throw new NullPointerException("Matcher must not be null"); - } else if (action == null) { + } else if(action == null) { throw new NullPointerException("Action must not be null"); } getEdges(source).forEach((target, weight) -> { - if (matcher.test(target, weight)) { + if(matcher.test(target, weight)) { action.accept(target, weight); } }); @@ -128,15 +127,14 @@ public class Graph<T> { * 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<T, Integer> getEdges(final T source) { /* Can't find edges for a null source. */ - if (source == null) + if(source == null) throw new NullPointerException("The source cannot be null."); - else if (!backing.containsKey(source)) + else if(!backing.containsKey(source)) throw new IllegalArgumentException("Vertex " + source + " is not in graph"); return backing.get(source); @@ -145,8 +143,7 @@ public class Graph<T> { /** * 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(); @@ -158,8 +155,7 @@ public class Graph<T> { * 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<Edge<T>> getMinimumSpanningTree() { /* Set of all of the currently available edges. */ @@ -178,7 +174,7 @@ public class Graph<T> { visited.add(source.getValue()); /* Make sure we visit all the nodes. */ - while (visited.size() != getVertexCount()) { + while(visited.size() != getVertexCount()) { /* Grab all edges adjacent to the provided edge. */ forAllEdgesMatchingAt(source.getValue(), (target, weight) -> { @@ -194,9 +190,9 @@ public class Graph<T> { /* * Only consider edges where we haven't visited the - * target of the edge. + * target of the edge. */ - while (visited.contains(minimum.getValue().getTarget())) { + while(visited.contains(minimum.getValue().getTarget())) { minimum.transform((edge) -> available.poll()); } @@ -216,8 +212,7 @@ public class Graph<T> { /** * 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(); @@ -226,8 +221,7 @@ public class Graph<T> { /** * 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<T> getVertices() { return backing.keyList(); @@ -237,27 +231,27 @@ 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(final T source, final T target) { /* Can't remove things w/ null vertices. */ - if (source == null) { + if(source == null) { throw new NullPointerException("The source vertex cannot be null"); - } else if (target == 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)) { + if(!backing.containsKey(source)) { String msg = String.format("vertex %s does not exist", source); throw new NoSuchElementException(msg); } - if (!backing.containsKey(target)) { + if(!backing.containsKey(target)) { String msg = String.format("vertex %s does not exist", target); throw new NoSuchElementException(msg); @@ -265,7 +259,8 @@ public class Graph<T> { backing.get(source).remove(target); - /* Uncomment this to turn the graph undirected + /* + * Uncomment this to turn the graph undirected * * graph.get(target).remove(source); */ @@ -274,8 +269,7 @@ public class Graph<T> { /** * Convert a graph into a adjacency map/matrix. * - * @return - * A adjacency map representing this graph. + * @return A adjacency map representing this graph. */ public AdjacencyMap<T> toAdjacencyMap() { final AdjacencyMap<T> adjacency = new AdjacencyMap<>(backing.keyList()); |
