From 8a8b457c98e207d809a7616e73eb59bfe197a7a5 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Thu, 31 Mar 2016 11:43:21 -0400 Subject: More code maintenance --- .../main/java/bjc/utils/graph/AdjacencyMap.java | 109 ++++++++-------- BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java | 10 +- .../src/main/java/bjc/utils/graph/Graph.java | 141 ++++++++++++--------- 3 files changed, 144 insertions(+), 116 deletions(-) (limited to 'BJC-Utils2/src/main/java/bjc/utils/graph') diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java index 6420d8e..513044e 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java @@ -6,6 +6,7 @@ import java.io.PrintStream; import java.util.HashMap; import java.util.HashSet; import java.util.Map; +import java.util.Map.Entry; import java.util.Scanner; import java.util.Set; import java.util.stream.IntStream; @@ -29,43 +30,44 @@ public class AdjacencyMap { * @return An adjacency map defined by the text */ public static AdjacencyMap fromStream(InputStream stream) { - Scanner scn = new Scanner(stream); - scn.useDelimiter("\n"); + Scanner inputSource = new Scanner(stream); + inputSource.useDelimiter("\n"); // First, read in number of vertices - int numVertices = Integer.parseInt(scn.next()); + int numVertices = Integer.parseInt(inputSource.next()); Set vertices = new HashSet<>(); - IntStream.range(0, numVertices).forEach(e -> vertices.add(e)); + IntStream.range(0, numVertices) + .forEach(element -> vertices.add(element)); // Create the adjacency map - AdjacencyMap aMap = new AdjacencyMap<>(vertices); + AdjacencyMap adjacencyMap = new AdjacencyMap<>(vertices); GenHolder row = new GenHolder<>(0); - scn.forEachRemaining((strang) -> { + inputSource.forEachRemaining((strang) -> { String[] parts = strang.split(" "); - int col = 0; + int column = 0; for (String part : parts) { - aMap.setWeight(row.unwrap(vl -> vl), col, - Integer.parseInt(part)); + adjacencyMap.setWeight(row.unwrap(number -> number), + column, Integer.parseInt(part)); - col++; + column++; } - row.transform((vl) -> vl + 1); + row.transform((number) -> number + 1); }); - scn.close(); + inputSource.close(); - return aMap; + return adjacencyMap; } /** * The backing storage of the map */ - private Map> adjMap; + private Map> adjacencyMap = new HashMap<>(); /** * Create a new map from a set of vertices @@ -74,12 +76,13 @@ public class AdjacencyMap { * The set of vertices to create a map from */ public AdjacencyMap(Set vertices) { - vertices.forEach(src -> { - Map srcRow = new HashMap<>(); + vertices.forEach(vertex -> { + Map vertexRow = new HashMap<>(); - vertices.forEach(tgt -> srcRow.put(tgt, 0)); + vertices.forEach( + targetVertex -> vertexRow.put(targetVertex, 0)); - adjMap.put(src, srcRow); + adjacencyMap.put(vertex, vertexRow); }); } @@ -89,33 +92,37 @@ public class AdjacencyMap { * @return Whether or not the graph is directed */ public boolean isDirected() { - GenHolder res = new GenHolder<>(true); - - adjMap.entrySet() - .forEach(src -> src.getValue().entrySet().forEach(tgt -> { - int lhs = tgt.getValue(); - int rhs = adjMap.get(tgt.getKey()).get(src.getKey()); - - if (lhs != rhs) { - res.transform((vl) -> false); - } - })); + GenHolder result = new GenHolder<>(true); + + adjacencyMap.entrySet().forEach(mapEntry -> { + Set> entryVertices = + mapEntry.getValue().entrySet(); + entryVertices.forEach(targetVertex -> { + int leftValue = targetVertex.getValue(); + int rightValue = adjacencyMap.get(targetVertex.getKey()) + .get(mapEntry.getKey()); + + if (leftValue != rightValue) { + result.transform((bool) -> false); + } + }); + }); - return res.unwrap(vl -> vl); + return result.unwrap(bool -> bool); } /** * Set the weight of an edge * - * @param src + * @param sourceVertex * The source node of the edge - * @param tgt + * @param targetVertex * The target node of the edge - * @param weight + * @param edgeWeight * The weight of the edge */ - public void setWeight(T src, T tgt, int weight) { - adjMap.get(src).put(tgt, weight); + public void setWeight(T sourceVertex, T targetVertex, int edgeWeight) { + adjacencyMap.get(sourceVertex).put(targetVertex, edgeWeight); } /** @@ -124,31 +131,33 @@ public class AdjacencyMap { * @return The new representation of this graph */ public Graph toGraph() { - Graph ret = new Graph<>(); + Graph returnedGraph = new Graph<>(); - adjMap.entrySet() - .forEach(src -> src.getValue().entrySet() - .forEach(tgt -> ret.addEdge(src.getKey(), - tgt.getKey(), tgt.getValue()))); + adjacencyMap.entrySet().forEach(sourceVertex -> sourceVertex + .getValue().entrySet() + .forEach(targetVertex -> returnedGraph.addEdge( + sourceVertex.getKey(), targetVertex.getKey(), + targetVertex.getValue()))); - return ret; + return returnedGraph; } /** * Convert an adjacency map back into a stream * - * @param os + * @param outputSource * The stream to convert to */ - public void toStream(OutputStream os) { - PrintStream ps = new PrintStream(os); - - adjMap.entrySet().forEach(src -> { - src.getValue().entrySet() - .forEach(tgt -> ps.printf("%d ", tgt.getValue())); - ps.println(); + public void toStream(OutputStream outputSource) { + PrintStream outputPrinter = new PrintStream(outputSource); + + adjacencyMap.entrySet().forEach(sourceVertex -> { + sourceVertex.getValue().entrySet() + .forEach(targetVertex -> outputPrinter.printf("%d ", + targetVertex.getValue())); + outputPrinter.println(); }); - ps.close(); + outputPrinter.close(); } } diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java index cf0764b..44aa8e7 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java @@ -22,16 +22,16 @@ public class Edge { /** * Create a new edge with set parameters * - * @param node1 + * @param initialNode * The initial node of the edge - * @param node2 + * @param terminalNode * The terminal node of the edge * @param distance * The distance between initial and terminal edge */ - public Edge(T node1, T node2, int distance) { - this.source = node1; - this.target = node2; + public Edge(T initialNode, T terminalNode, int distance) { + this.source = initialNode; + this.target = terminalNode; this.distance = distance; } 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 d7aff34..5172df5 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java +++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java @@ -29,44 +29,47 @@ public class Graph { /** * The backing representation of the graph */ - private final Map> graph; + private final Map> backingGraph; /** * Create a new graph */ public Graph() { - graph = new HashMap<>(); + backingGraph = new HashMap<>(); } /** * Add a edge to the graph * - * @param source + * @param sourceVertex * The source vertex for this edge - * @param target + * @param targetVertex * The target vertex for this edge * @param distance * The distance from the source vertex to the target vertex */ - public void addEdge(T source, T target, int distance) { + public void addEdge(T sourceVertex, T targetVertex, int distance) { // Can't add edges with a null source or target - if (source == null) { - throw new NullPointerException("The vertex 1 cannot be null"); + if (sourceVertex == null) { + throw new NullPointerException( + "The source vertex cannot be null"); } - if (target == null) { - throw new NullPointerException("The vertex 2 cannot be null"); + + if (targetVertex == null) { + throw new NullPointerException( + "The target vertex cannot be null"); } // Initialize adjacency list for vertices if necessary - if (!graph.containsKey(source)) { - graph.put(source, new HashMap()); + if (!backingGraph.containsKey(sourceVertex)) { + backingGraph.put(sourceVertex, new HashMap()); } - if (!graph.containsKey(target)) { - graph.put(target, new HashMap()); + if (!backingGraph.containsKey(targetVertex)) { + backingGraph.put(targetVertex, new HashMap()); } // Add the edge to the graph - graph.get(source).put(target, distance); + backingGraph.get(sourceVertex).put(targetVertex, distance); // Uncomment this to make the graph undirected // graph.get(target).put(source, distance); @@ -78,16 +81,17 @@ public class Graph { * * @param source * The vertex to test edges for - * @param bp + * @param edgeMatcher * The conditions an edge must match - * @param bc + * @param edgeAction * The action to execute for matching edges */ - public void forAllEdgesMatchingAt(T source, BiPredicate bp, - BiConsumer bc) { + public void forAllEdgesMatchingAt(T source, + BiPredicate edgeMatcher, + BiConsumer edgeAction) { getEdges(source).forEach((tgt, weight) -> { - if (bp.test(tgt, weight)) { - bc.accept(tgt, weight); + if (edgeMatcher.test(tgt, weight)) { + edgeAction.accept(tgt, weight); } }); } @@ -105,7 +109,7 @@ public class Graph { throw new NullPointerException("The source cannot be null."); } - return Collections.unmodifiableMap(graph.get(source)); + return Collections.unmodifiableMap(backingGraph.get(source)); } /** @@ -114,7 +118,7 @@ public class Graph { * @return The initial vertex of the graph */ public T getInitial() { - return graph.keySet().iterator().next(); + return backingGraph.keySet().iterator().next(); } /** @@ -123,51 +127,59 @@ public class Graph { * * @return a list of edges that constitute the MST */ - public List> getMinSpanTree() { + public List> getMinimumSpanningTree() { // Set of all of the currently available edges - Queue> availEdges = new PriorityQueue<>(10, - (e1, e2) -> e1.getDistance() - e2.getDistance()); + Queue> availableEdges = new PriorityQueue<>(10, + (leftEdge, rightEdge) -> leftEdge.getDistance() + - rightEdge.getDistance()); // The MST of the graph - List> minEdges = new ArrayList<>(); + List> minimumEdges = new ArrayList<>(); // The set of all of the visited vertices. - Set visited = new HashSet<>(); + Set visitedVertexes = new HashSet<>(); // Start at the initial vertex and visit it - IHolder src = new GenHolder<>(getInitial()); - visited.add(src.unwrap(vl -> vl)); + IHolder sourceVertex = new GenHolder<>(getInitial()); + + visitedVertexes.add(sourceVertex.unwrap(vertex -> vertex)); // Make sure we visit all the nodes - while (visited.size() != getVertexCount()) { + while (visitedVertexes.size() != getVertexCount()) { // Grab all edges adjacent to the provided edge - forAllEdgesMatchingAt(src.unwrap(vl -> vl), - (tgt, weight) -> !visited.contains(tgt), - (tgt, weight) -> availEdges.add(new Edge<>( - src.unwrap(vl -> vl), tgt, weight))); + forAllEdgesMatchingAt(sourceVertex.unwrap(vertex -> vertex), + (targetVertex, + vertexWeight) -> !visitedVertexes + .contains(targetVertex), + (targetVertex, + vertexWeight) -> availableEdges.add(new Edge<>( + sourceVertex.unwrap(vertex -> vertex), + targetVertex, vertexWeight))); // Get the edge with the minimum distance - IHolder> minEdge = new GenHolder<>(availEdges.poll()); + IHolder> minimumEdge = + new GenHolder<>(availableEdges.poll()); // Only consider edges where we haven't visited the target of // the edge - while (visited - .contains(minEdge.unwrap(vl -> vl.getTarget()))) { - minEdge.transform((vl) -> availEdges.poll()); + while (visitedVertexes.contains( + minimumEdge.unwrap(vertex -> vertex.getTarget()))) { + minimumEdge.transform((edge) -> availableEdges.poll()); } // Add it to our MST - minEdges.add(minEdge.unwrap(vl -> vl)); + minimumEdges.add(minimumEdge.unwrap(edge -> edge)); // Advance to the next node - src.transform((vl) -> minEdge.unwrap(vl1 -> vl1.getTarget())); + sourceVertex.transform((vertex) -> minimumEdge + .unwrap(edge -> edge.getTarget())); // Visit this node - visited.add(src.unwrap(vl -> vl)); + visitedVertexes.add(sourceVertex.unwrap(vertex -> vertex)); } - return minEdges; + return minimumEdges; } /** @@ -176,7 +188,7 @@ public class Graph { * @return A count of the vertices in this graph */ public int getVertexCount() { - return graph.size(); + return backingGraph.size(); } /** @@ -185,37 +197,40 @@ public class Graph { * @return A unmodifiable set of all the vertices in the graph. */ public Set getVertices() { - return Collections.unmodifiableSet(graph.keySet()); + return Collections.unmodifiableSet(backingGraph.keySet()); } /** * Remove the edge starting at the source and ending at the target * - * @param source + * @param sourceVertex * The source vertex for the edge - * @param target + * @param targetVertex * The target vertex for the edge */ - public void removeEdge(T source, T target) { + public void removeEdge(T sourceVertex, T targetVertex) { // Can't remove things w/ null vertices - if (source == null) { - throw new NullPointerException("The vertex 1 cannot be null"); + if (sourceVertex == null) { + throw new NullPointerException( + "The source vertex cannot be null"); } - if (target == null) { - throw new NullPointerException("The vertex 2 cannot be null"); + if (targetVertex == null) { + throw new NullPointerException( + "The target vertex cannot be null"); } // Can't remove if one vertice doesn't exists - if (!graph.containsKey(source)) { + if (!backingGraph.containsKey(sourceVertex)) { throw new NoSuchElementException( - "vertex " + source + " does not exist."); + "vertex " + sourceVertex + " does not exist."); } - if (!graph.containsKey(target)) { + + if (!backingGraph.containsKey(targetVertex)) { throw new NoSuchElementException( - "vertex " + target + " does not exist."); + "vertex " + targetVertex + " does not exist."); } - graph.get(source).remove(target); + backingGraph.get(sourceVertex).remove(targetVertex); // Uncomment this to turn the graph undirected // graph.get(target).remove(source); @@ -226,13 +241,17 @@ public class Graph { * * @return A adjacency map representing this graph */ - public AdjacencyMap toMap() { - AdjacencyMap aMap = new AdjacencyMap<>(graph.keySet()); + public AdjacencyMap toAdjacencyMap() { + AdjacencyMap adjacencyMap = + new AdjacencyMap<>(backingGraph.keySet()); - graph.entrySet().forEach(src -> src.getValue().forEach((tgt, - weight) -> aMap.setWeight(src.getKey(), tgt, weight))); + backingGraph.entrySet().forEach(sourceVertex -> sourceVertex + .getValue() + .forEach((targetVertex, vertexWeight) -> adjacencyMap + .setWeight(sourceVertex.getKey(), targetVertex, + vertexWeight))); - return aMap; + return adjacencyMap; } /** -- cgit v1.2.3