summaryrefslogtreecommitdiff
path: root/base/src/main/java/bjc/utils/graph
diff options
context:
space:
mode:
Diffstat (limited to 'base/src/main/java/bjc/utils/graph')
-rw-r--r--base/src/main/java/bjc/utils/graph/AdjacencyMap.java61
-rw-r--r--base/src/main/java/bjc/utils/graph/Edge.java43
-rw-r--r--base/src/main/java/bjc/utils/graph/Graph.java82
3 files changed, 95 insertions, 91 deletions
diff --git a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
index ee360bd..d818ca1 100644
--- a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
+++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -20,24 +20,25 @@ 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
*/
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;
@@ -47,7 +48,7 @@ public class AdjacencyMap<T> {
try {
/* First, read in number of vertices. */
vertexCount = Integer.parseInt(possible);
- } catch(final NumberFormatException nfex) {
+ } catch (final NumberFormatException nfex) {
String msg = String.format(
"The first line must contain the number of vertices. %s is not a valid number",
possible);
@@ -59,18 +60,19 @@ public class AdjacencyMap<T> {
throw imex;
}
- if(vertexCount <= 0)
- throw new InputMismatchException("The number of vertices must be greater than 0");
+ if (vertexCount <= 0)
+ throw new InputMismatchException(
+ "The number of vertices must be greater than 0");
final IList<Integer> vertices = new FunctionalList<>();
- FuncUtils.doTimes(vertexCount, (vertexNo) -> vertices.add(vertexNo));
+ FuncUtils.doTimes(vertexCount, vertexNo -> vertices.add(vertexNo));
adjacency = new AdjacencyMap<>(vertices);
final IHolder<Integer> row = new Identity<>(0);
- input.forEachRemaining((strang) -> {
+ input.forEachRemaining(strang -> {
readRow(adjacency, vertexCount, row, strang);
});
}
@@ -79,24 +81,25 @@ public class AdjacencyMap<T> {
}
/* Read a row of edges. */
- private static void readRow(final AdjacencyMap<Integer> adjacency, final int vertexCount,
- final IHolder<Integer> row, final String strang) {
+ private static void readRow(final AdjacencyMap<Integer> adjacency,
+ final int vertexCount, final IHolder<Integer> row, final String strang) {
final String[] parts = strang.split(" ");
- if(parts.length != vertexCount) {
- String msg = String.format("Must specify a weight for all %d vertices", vertexCount);
+ if (parts.length != vertexCount) {
+ String msg = String.format("Must specify a weight for all %d vertices",
+ vertexCount);
throw new InputMismatchException(msg);
}
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);
@@ -110,7 +113,7 @@ public class AdjacencyMap<T> {
column++;
}
- row.transform((rowNumber) -> rowNumber + 1);
+ row.transform(rowNumber -> rowNumber + 1);
}
/** The backing storage of the map */
@@ -120,10 +123,11 @@ 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<>();
@@ -148,7 +152,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);
}
});
@@ -161,24 +165,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);
@@ -208,10 +212,11 @@ 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 e7e7b36..fe3d891 100644
--- a/base/src/main/java/bjc/utils/graph/Edge.java
+++ b/base/src/main/java/bjc/utils/graph/Edge.java
@@ -6,7 +6,7 @@ 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. */
@@ -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,27 @@ 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,8 +70,7 @@ 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;
@@ -107,8 +109,9 @@ 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 e092623..8ff5647 100644
--- a/base/src/main/java/bjc/utils/graph/Graph.java
+++ b/base/src/main/java/bjc/utils/graph/Graph.java
@@ -22,17 +22,17 @@ import bjc.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.
*/
@@ -58,27 +58,28 @@ 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) {
+ 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>());
}
@@ -86,8 +87,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>());
}
@@ -96,28 +97,27 @@ public class Graph<T> {
}
/**
- * Execute an action for all edges of a specific vertex matching
- * conditions.
+ * Execute an action for all edges of a specific vertex matching 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) {
+ public void forAllEdgesMatchingAt(final T source,
+ final BiPredicate<T, Integer> matcher, final BiConsumer<T, Integer> action) {
+ 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);
}
});
@@ -127,14 +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.
+ * 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);
@@ -152,8 +152,7 @@ public class Graph<T> {
/**
* Uses Prim's algorothm to calculate a MST for the graph.
*
- * If the graph is non-connected, this will lead to unpredictable
- * results.
+ * If the graph is non-connected, this will lead to unpredictable results.
*
* @return A list of edges that constitute the MST.
*/
@@ -174,12 +173,10 @@ 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) -> {
- return !visited.contains(target);
- }, (target, weight) -> {
+ forAllEdgesMatchingAt(source.getValue(), (target, weight) -> !visited.contains(target), (target, weight) -> {
final T vert = source.unwrap(vertex -> vertex);
available.add(new Edge<>(vert, target, weight));
@@ -189,18 +186,17 @@ public class Graph<T> {
final IHolder<Edge<T>> 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());
+ 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()));
+ source.transform(vertex -> minimum.unwrap(edge -> edge.getTarget()));
/* Visit this node. */
visited.add(source.getValue());
@@ -231,27 +227,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);
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 06:06:21 +0000