From 6186f1d87c5e170fa89aa327001706b0692526fc Mon Sep 17 00:00:00 2001 From: Ben Culkin Date: Fri, 16 Sep 2022 18:58:38 -0400 Subject: Convert graph weights to labels --- .../main/java/bjc/utils/graph/AdjacencyMap.java | 46 +++++---- base/src/main/java/bjc/utils/graph/Edge.java | 83 +++++++---------- base/src/main/java/bjc/utils/graph/Graph.java | 103 +++++---------------- 3 files changed, 76 insertions(+), 156 deletions(-) (limited to 'base/src') diff --git a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java index 978b21d..04fe4c8 100644 --- a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java +++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java @@ -22,7 +22,7 @@ import bjc.utils.funcutils.FuncUtils; * @param * The type of the nodes in the graph */ -public class AdjacencyMap { +public class AdjacencyMap { /** * Create an adjacency map from a stream of text * @@ -31,11 +31,11 @@ public class AdjacencyMap { * * @return An adjacency map defined by the text */ - public static AdjacencyMap fromStream(final InputStream stream) { + 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; + AdjacencyMap adjacency; try (Scanner input = new Scanner(stream)) { input.useDelimiter("\n"); @@ -79,7 +79,7 @@ public class AdjacencyMap { } /* Read a row of edges. */ - private static void readRow(final AdjacencyMap adjacency, + private static void readRow(final AdjacencyMap adjacency, final int vertexCount, final Holder row, final String strang) { final String[] parts = strang.split(" "); @@ -106,7 +106,7 @@ public class AdjacencyMap { throw imex; } - adjacency.setWeight(row.getValue(), column, weight); + adjacency.setLabel(row.getValue(), column, weight); column++; } @@ -115,7 +115,7 @@ public class AdjacencyMap { } /** The backing storage of the map */ - private final MapEx> adjacency = new FunctionalMap<>(); + private final MapEx> adjacency = new FunctionalMap<>(); /** * Create a new map from a set of vertices @@ -127,10 +127,10 @@ public class AdjacencyMap { if (vertices == null) throw new NullPointerException("Vertices must not be null"); vertices.forEach(vertex -> { - final MapEx row = new FunctionalMap<>(); + final MapEx row = new FunctionalMap<>(); vertices.forEach(target -> { - row.put(target, 0); + row.put(target, null); }); adjacency.put(vertex, row); @@ -147,7 +147,7 @@ public class AdjacencyMap { adjacency.forEach((sourceKey, sourceValue) -> { sourceValue.forEach((targetKey, targetValue) -> { - final int inverseValue = adjacency.get(targetKey).get().get(sourceKey).get(); + final W inverseValue = adjacency.get(targetKey).get().get(sourceKey).get(); if (targetValue != inverseValue) result.replace(false); }); @@ -157,16 +157,16 @@ public class AdjacencyMap { } /** - * Set the weight of an edge. + * Set the label of an edge. * * @param source * The source node of the edge. * @param target * The target node of the edge. - * @param weight + * @param label * The weight of the edge. */ - public void setWeight(final T source, final T target, final int weight) { + public void setLabel(final T source, final T target, final W label) { 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"); @@ -180,7 +180,7 @@ public class AdjacencyMap { throw new IllegalArgumentException(msg); } - adjacency.get(source).get().put(target, weight); + adjacency.get(source).get().put(target, label); } /** @@ -188,8 +188,8 @@ public class AdjacencyMap { * * @return The new representation of this graph. */ - public Graph toGraph() { - final Graph ret = new Graph<>(); + public Graph toGraph() { + final Graph ret = new Graph<>(); adjacency.forEach((sourceKey, sourceValue) -> { sourceValue.forEach((targetKey, targetValue) -> { @@ -209,16 +209,14 @@ public class AdjacencyMap { public void toStream(final OutputStream sink) { if (sink == null) throw new NullPointerException("Output source must not be null"); - final PrintStream outputPrinter = new PrintStream(sink); + try (PrintStream outputPrinter = new PrintStream(sink)) { + adjacency.forEach((sourceKey, sourceValue) -> { + sourceValue.forEach((targetKey, targetValue) -> { + outputPrinter.printf("%d", targetValue); + }); - adjacency.forEach((sourceKey, sourceValue) -> { - sourceValue.forEach((targetKey, targetValue) -> { - outputPrinter.printf("%d", targetValue); + outputPrinter.println(); }); - - 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 index b48fcd0..5b0eba3 100644 --- a/base/src/main/java/bjc/utils/graph/Edge.java +++ b/base/src/main/java/bjc/utils/graph/Edge.java @@ -1,16 +1,17 @@ package bjc.utils.graph; +import java.util.Objects; + /** * An edge in a weighted graph. * * @author ben * - * @param - * The type of the nodes in the graph. + * @param The type of the nodes in the graph. */ -public class Edge { +public class Edge { /* The distance from initial to terminal node. */ - private final int distance; + private final W distance; /* The initial and terminal nodes of this edge. */ private final T source, target; @@ -18,54 +19,29 @@ public class Edge { /** * Create a new edge with set parameters. * - * @param initial - * The initial node of the edge. + * @param initial The initial node of the edge. * - * @param terminal - * The terminal node of the edge. + * @param terminal The terminal node of the edge. * - * @param distance - * The distance between initial and terminal 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"); + public Edge(final T initial, final T terminal, final W 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() { + public W getDistance() { return distance; } @@ -88,24 +64,27 @@ public class Edge { } @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()); + public String toString() { + String msg = String.format("source vertex %s to target vertex %s with distance: %s", source, target, distance); - return result; + return msg; } @Override - public String toString() { - String msg - = String.format("source vertex %s to target vertex %s with distance: %s", - source, target, distance); + public int hashCode() { + return Objects.hash(distance, source, target); + } - return msg; + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + Edge other = (Edge) obj; + return Objects.equals(distance, other.distance) && Objects.equals(source, other.source) + && Objects.equals(target, other.target); } } diff --git a/base/src/main/java/bjc/utils/graph/Graph.java b/base/src/main/java/bjc/utils/graph/Graph.java index f32e07f..81653fc 100644 --- a/base/src/main/java/bjc/utils/graph/Graph.java +++ b/base/src/main/java/bjc/utils/graph/Graph.java @@ -21,10 +21,10 @@ import bjc.funcdata.MapEx; * * @author ben * - * @param + * @param * The label for vertices. */ -public class Graph { +public class Graph { /** * Create a graph from a list of edges. * @@ -36,8 +36,8 @@ public class Graph { * * @return A graph built from the provided edge-list. */ - public static Graph fromEdgeList(final List> edges) { - final Graph g = new Graph<>(); + public static Graph fromEdgeList(final List> edges) { + final Graph g = new Graph<>(); edges.forEach(edge -> { g.addEdge(edge.getSource(), edge.getTarget(), edge.getDistance(), true); @@ -47,7 +47,7 @@ public class Graph { } /** The backing representation of the graph. */ - private final MapEx> backing; + private final MapEx> backing; /** Create a new empty graph. */ public Graph() { @@ -63,31 +63,31 @@ public class Graph { * @param target * The target vertex for this edge. * - * @param distance + * @param label * The distance from the source vertex to the target vertex. * * @param directed * Whether or not the edge is directed or not. */ - public void addEdge(final T source, final T target, final int distance, + public void addEdge(final VertexLabel source, final VertexLabel target, final EdgeLabel label, 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()); + if (!backing.containsKey(source)) backing.put(source, new FunctionalMap()); /* Add the edge to the graph. */ - backing.get(source).get().put(target, distance); + backing.get(source).get().put(target, label); /* Handle possible directed edges. */ if (!directed) { if (!backing.containsKey(target)) { - backing.put(target, new FunctionalMap()); + backing.put(target, new FunctionalMap()); } - backing.get(target).get().put(source, distance); + backing.get(target).get().put(source, label); } } @@ -103,13 +103,13 @@ public class Graph { * @param action * The action to execute for matching edges. */ - public void forAllEdgesMatchingAt(final T source, - final BiPredicate matcher, final BiConsumer action) { + public void forAllEdgesMatchingAt(final VertexLabel 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); + getEdges(source).forEach((target, label) -> { + if (matcher.test(target, label)) action.accept(target, label); }); } @@ -120,7 +120,7 @@ public class Graph { * The vertex to use as a source. * @return All of the edges with the specified vertex as a source. */ - public MapEx getEdges(final T source) { + public MapEx getEdges(final VertexLabel source) { /* Can't find edges for a null source. */ if (source == null) { throw new NullPointerException("The source cannot be null."); @@ -136,68 +136,11 @@ public class Graph { * * @return The initial vertex of the graph. */ - public T getInitial() { + public VertexLabel 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 Holder 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) -> !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 Holder> 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. @@ -213,7 +156,7 @@ public class Graph { * * @return A unmodifiable set of all the vertices in the graph. */ - public ListEx getVertices() { + public ListEx getVertices() { return backing.keyList(); } @@ -226,7 +169,7 @@ public class Graph { * @param target * The target vertex for the edge. */ - public void removeEdge(final T source, final T target) { + public void removeEdge(final VertexLabel source, final VertexLabel target) { /* Can't remove things w/ null vertices. */ if (source == null) { throw new NullPointerException("The source vertex cannot be null"); @@ -261,12 +204,12 @@ public class Graph { * * @return A adjacency map representing this graph. */ - public AdjacencyMap toAdjacencyMap() { - final AdjacencyMap adjacency = new AdjacencyMap<>(backing.keyList()); + public AdjacencyMap toAdjacencyMap() { + final AdjacencyMap adjacency = new AdjacencyMap<>(backing.keyList()); backing.forEach((sourceKey, sourceValue) -> { sourceValue.forEach((targetKey, targetValue) -> { - adjacency.setWeight(sourceKey, targetKey, targetValue); + adjacency.setLabel(sourceKey, targetKey, targetValue); }); }); -- cgit v1.2.3