From c82e3b3b2de0633317ec8fc85925e91422820597 Mon Sep 17 00:00:00 2001 From: "Benjamin J. Culkin" Date: Sun, 8 Oct 2017 22:39:59 -0300 Subject: Start splitting into maven modules --- .../main/java/bjc/utils/graph/AdjacencyMap.java | 216 +++++++++++++++++ base/src/main/java/bjc/utils/graph/Edge.java | 112 +++++++++ base/src/main/java/bjc/utils/graph/Graph.java | 267 +++++++++++++++++++++ 3 files changed, 595 insertions(+) create mode 100644 base/src/main/java/bjc/utils/graph/AdjacencyMap.java create mode 100644 base/src/main/java/bjc/utils/graph/Edge.java create mode 100644 base/src/main/java/bjc/utils/graph/Graph.java (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 new file mode 100644 index 0000000..446ab5b --- /dev/null +++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java @@ -0,0 +1,216 @@ +package bjc.utils.graph; + +import java.io.InputStream; +import java.io.OutputStream; +import java.io.PrintStream; +import java.util.InputMismatchException; +import java.util.Scanner; + +import bjc.utils.data.IHolder; +import bjc.utils.data.Identity; +import bjc.utils.funcdata.FunctionalList; +import bjc.utils.funcdata.FunctionalMap; +import bjc.utils.funcdata.IList; +import bjc.utils.funcdata.IMap; +import bjc.utils.funcutils.FuncUtils; + +/** + * An adjacency map representing a graph + * + * @author ben + * + * @param + * 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 + */ + public static AdjacencyMap fromStream(final InputStream stream) { + if (stream == null) throw new NullPointerException("Input source must not be null"); + + // Create the adjacency map + AdjacencyMap adjacency; + + try (Scanner input = new Scanner(stream)) { + input.useDelimiter("\n"); + + int vertexCount; + + final String possible = input.next(); + + try { + // 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"); + + imex.initCause(nfex); + + throw imex; + } + + if (vertexCount <= 0) + throw new InputMismatchException("The number of vertices must be greater than 0"); + + final IList vertices = new FunctionalList<>(); + + FuncUtils.doTimes(vertexCount, (vertexNo) -> vertices.add(vertexNo)); + + adjacency = new AdjacencyMap<>(vertices); + + final IHolder row = new Identity<>(0); + + input.forEachRemaining((strang) -> { + readRow(adjacency, vertexCount, row, strang); + }); + } + + return adjacency; + } + + 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"); + + int column = 0; + + for (final String part : parts) { + int weight; + + try { + weight = Integer.parseInt(part); + } catch (final NumberFormatException nfex) { + final InputMismatchException imex = new InputMismatchException( + "" + part + " is not a valid weight."); + + imex.initCause(nfex); + + throw imex; + } + + adjacency.setWeight(row.getValue(), column, weight); + + column++; + } + + row.transform((rowNumber) -> rowNumber + 1); + } + + /** + * 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 + */ + public AdjacencyMap(final IList vertices) { + if (vertices == null) throw new NullPointerException("Vertices must not be null"); + + vertices.forEach(vertex -> { + final IMap row = new FunctionalMap<>(); + + vertices.forEach(target -> { + row.put(target, 0); + }); + + adjacency.put(vertex, row); + }); + } + + /** + * Check if the graph is directed + * + * @return Whether or not the graph is directed + */ + public boolean isDirected() { + final IHolder result = new Identity<>(true); + + adjacency.forEach((sourceKey, sourceValue) -> { + sourceValue.forEach((targetKey, targetValue) -> { + final int inverseValue = adjacency.get(targetKey).get(sourceKey); + + if (targetValue != inverseValue) { + result.replace(false); + } + }); + }); + + return result.getValue(); + } + + /** + * Set the weight of an edge + * + * @param source + * The source node of the edge + * @param target + * The target node of the edge + * @param weight + * The weight of the edge + */ + public void setWeight(final T source, final T target, final int weight) { + 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"); + + 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"); + + adjacency.get(source).put(target, weight); + } + + /** + * Convert this to a different graph representation + * + * @return The new representation of this graph + */ + public Graph toGraph() { + final Graph ret = new Graph<>(); + + adjacency.forEach((sourceKey, sourceValue) -> { + sourceValue.forEach((targetKey, targetValue) -> { + ret.addEdge(sourceKey, targetKey, targetValue, true); + }); + }); + + return ret; + } + + /** + * Convert an adjacency map back into a stream + * + * @param sink + * The stream to convert to + */ + public void toStream(final OutputStream sink) { + if (sink == null) throw new NullPointerException("Output source must not be null"); + + final PrintStream outputPrinter = new PrintStream(sink); + + adjacency.forEach((sourceKey, sourceValue) -> { + sourceValue.forEach((targetKey, targetValue) -> { + outputPrinter.printf("%d", targetValue); + }); + + outputPrinter.println(); + }); + + outputPrinter.close(); + } +} diff --git a/base/src/main/java/bjc/utils/graph/Edge.java b/base/src/main/java/bjc/utils/graph/Edge.java new file mode 100644 index 0000000..0152e3d --- /dev/null +++ b/base/src/main/java/bjc/utils/graph/Edge.java @@ -0,0 +1,112 @@ +package bjc.utils.graph; + +/** + * An edge in a weighted graph + * + * @author ben + * + * @param + * The type of the nodes in the graph + */ +public class Edge { + /* + * The distance from initial to terminal node + */ + private final int distance; + + /* + * The initial and terminal nodes of this edge + */ + private final T source, target; + + /** + * Create a new edge with set parameters + * + * @param initial + * The initial node of the edge + * @param terminal + * The terminal node of the edge + * @param distance + * The distance between initial and terminal edge + */ + public Edge(final T initial, final T terminal, final int distance) { + 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"); + + this.source = initial; + this.target = terminal; + this.distance = distance; + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) + return true; + else if (obj == null) + return false; + else if (getClass() != obj.getClass()) + return false; + else { + final Edge other = (Edge) obj; + + if (distance != other.distance) + return false; + 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; + + return true; + } + } + + /** + * Get the distance in 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 + * + * @return The initial node of this edge + */ + public T getSource() { + return source; + } + + /** + * Get the target node of an edge + * + * @return The target node of this edge + */ + public T getTarget() { + return target; + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + + result = prime * result + distance; + result = prime * result + (source == null ? 0 : source.hashCode()); + result = prime * result + (target == null ? 0 : target.hashCode()); + + return result; + } + + @Override + public String toString() { + return " first vertex " + source + " to vertex " + target + " with distance: " + distance; + } +} diff --git a/base/src/main/java/bjc/utils/graph/Graph.java b/base/src/main/java/bjc/utils/graph/Graph.java new file mode 100644 index 0000000..280a7f5 --- /dev/null +++ b/base/src/main/java/bjc/utils/graph/Graph.java @@ -0,0 +1,267 @@ +package bjc.utils.graph; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Set; +import java.util.function.BiConsumer; +import java.util.function.BiPredicate; + +import bjc.utils.data.IHolder; +import bjc.utils.data.Identity; +import bjc.utils.funcdata.FunctionalMap; +import bjc.utils.funcdata.IList; +import bjc.utils.funcdata.IMap; + +/** + * A directed weighted graph, where the vertices have some arbitrary label + * + * @author ben + * + * @param + * The label for vertices + */ +public class Graph { + /** + * Create a graph from a list of edges + * + * @param + * 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 + */ + public static Graph fromEdgeList(final List> edges) { + final Graph g = new Graph<>(); + + edges.forEach(edge -> { + g.addEdge(edge.getSource(), edge.getTarget(), edge.getDistance(), true); + }); + + return g; + } + + /** + * The backing representation of the graph + */ + private final IMap> backing; + + /** + * Create a new graph + */ + public Graph() { + backing = new FunctionalMap<>(); + } + + /** + * Add a edge to the graph + * + * @param source + * The source vertex for this edge + * @param target + * The target vertex for this edge + * @param distance + * The distance from the source vertex to the target + * vertex + * @param directed + * Whether 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) + throw new NullPointerException("The source vertex cannot be 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)) { + backing.put(source, new FunctionalMap()); + } + + // Add the edge to the graph + backing.get(source).put(target, distance); + + // Handle possible directed edges + if (!directed) { + if (!backing.containsKey(target)) { + backing.put(target, new FunctionalMap()); + } + + backing.get(target).put(source, distance); + } + } + + /** + * Execute an action for all edges of a specific vertex matching + * conditions + * + * @param source + * The vertex to test edges for + * @param matcher + * The conditions an edge must match + * @param action + * The action to execute for matching edges + */ + public void forAllEdgesMatchingAt(final T source, final BiPredicate matcher, + final BiConsumer action) { + if (matcher == null) + throw new NullPointerException("Matcher 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)) { + action.accept(target, weight); + } + }); + } + + /** + * 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 + */ + public IMap getEdges(final T 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)) + throw new IllegalArgumentException("Vertex " + source + " is not in graph"); + + return backing.get(source); + } + + /** + * Get the initial vertex of the graph + * + * @return The initial vertex of the graph + */ + public T getInitial() { + return backing.keyList().first(); + } + + /** + * Uses Prim's algorothm to calculate a MST for the graph. + * + * If the graph is non-connected, this will lead to unpredictable + * results. + * + * @return a list of edges that constitute the MST + */ + public List> getMinimumSpanningTree() { + // 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 + final List> minimums = new ArrayList<>(); + + // The set of all of the visited vertices. + final Set visited = new HashSet<>(); + + // 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 + while (visited.size() != getVertexCount()) { + // Grab all edges adjacent to the provided edge + + forAllEdgesMatchingAt(source.getValue(), (target, weight) -> { + return !visited.contains(target); + }, (target, weight) -> { + final T vert = source.unwrap(vertex -> vertex); + + available.add(new Edge<>(vert, target, weight)); + }); + + // 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 + while (visited.contains(minimum.getValue().getTarget())) { + minimum.transform((edge) -> available.poll()); + } + + // Add it to our MST + minimums.add(minimum.getValue()); + + // Advance to the next node + source.transform((vertex) -> minimum.unwrap(edge -> edge.getTarget())); + + // Visit this node + visited.add(source.getValue()); + } + + return minimums; + } + + /** + * Get the count of the vertices in this graph + * + * @return A count of the vertices in this graph + */ + public int getVertexCount() { + return backing.size(); + } + + /** + * Get all of the vertices in this 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 + * + * @param source + * The source vertex for the edge + * @param target + * 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) + throw new NullPointerException("The source 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."); + + if (!backing.containsKey(target)) + throw new NoSuchElementException("vertex " + target + " does not exist."); + + backing.get(source).remove(target); + + // Uncomment this to turn the graph undirected + // graph.get(target).remove(source); + } + + /** + * Convert a graph into a adjacency map/matrix + * + * @return A adjacency map representing this graph + */ + public AdjacencyMap toAdjacencyMap() { + final AdjacencyMap adjacency = new AdjacencyMap<>(backing.keyList()); + + backing.forEach((sourceKey, sourceValue) -> { + sourceValue.forEach((targetKey, targetValue) -> { + adjacency.setWeight(sourceKey, targetKey, targetValue); + }); + }); + + return adjacency; + } +} -- cgit v1.2.3