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.java47
-rw-r--r--base/src/main/java/bjc/utils/graph/Edge.java33
-rw-r--r--base/src/main/java/bjc/utils/graph/Graph.java62
3 files changed, 60 insertions, 82 deletions
diff --git a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
index e046fb5..978b21d 100644
--- a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
+++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -6,12 +6,12 @@ import java.io.PrintStream;
import java.util.InputMismatchException;
import java.util.Scanner;
-import bjc.data.IHolder;
+import bjc.data.Holder;
import bjc.data.Identity;
import bjc.funcdata.FunctionalList;
import bjc.funcdata.FunctionalMap;
-import bjc.funcdata.IList;
-import bjc.funcdata.IMap;
+import bjc.funcdata.ListEx;
+import bjc.funcdata.MapEx;
import bjc.utils.funcutils.FuncUtils;
/**
@@ -32,8 +32,7 @@ public class AdjacencyMap<T> {
* @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;
@@ -60,17 +59,16 @@ public class AdjacencyMap<T> {
throw imex;
}
- if (vertexCount <= 0)
- throw new InputMismatchException(
+ if (vertexCount <= 0) throw new InputMismatchException(
"The number of vertices must be greater than 0");
- final IList<Integer> vertices = new FunctionalList<>();
+ final ListEx<Integer> vertices = new FunctionalList<>();
FuncUtils.doTimes(vertexCount, vertexNo -> vertices.add(vertexNo));
adjacency = new AdjacencyMap<>(vertices);
- final IHolder<Integer> row = new Identity<>(0);
+ final Holder<Integer> row = new Identity<>(0);
input.forEachRemaining(strang -> {
readRow(adjacency, vertexCount, row, strang);
@@ -82,7 +80,7 @@ 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) {
+ final int vertexCount, final Holder<Integer> row, final String strang) {
final String[] parts = strang.split(" ");
if (parts.length != vertexCount) {
@@ -117,7 +115,7 @@ public class AdjacencyMap<T> {
}
/** The backing storage of the map */
- private final IMap<T, IMap<T, Integer>> adjacency = new FunctionalMap<>();
+ private final MapEx<T, MapEx<T, Integer>> adjacency = new FunctionalMap<>();
/**
* Create a new map from a set of vertices
@@ -125,12 +123,11 @@ public class AdjacencyMap<T> {
* @param vertices
* 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");
+ public AdjacencyMap(final ListEx<T> vertices) {
+ if (vertices == null) throw new NullPointerException("Vertices must not be null");
vertices.forEach(vertex -> {
- final IMap<T, Integer> row = new FunctionalMap<>();
+ final MapEx<T, Integer> row = new FunctionalMap<>();
vertices.forEach(target -> {
row.put(target, 0);
@@ -146,15 +143,13 @@ public class AdjacencyMap<T> {
* @return Whether or not the graph is directed
*/
public boolean isDirected() {
- final IHolder<Boolean> result = new Identity<>(true);
+ final Holder<Boolean> result = new Identity<>(true);
adjacency.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
- final int inverseValue = adjacency.get(targetKey).get(sourceKey);
+ final int inverseValue = adjacency.get(targetKey).get().get(sourceKey).get();
- if (targetValue != inverseValue) {
- result.replace(false);
- }
+ if (targetValue != inverseValue) result.replace(false);
});
});
@@ -172,11 +167,8 @@ public class AdjacencyMap<T> {
* 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 (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)) {
String msg = String.format("Source vertex %s isn't present in map", source);
@@ -188,7 +180,7 @@ public class AdjacencyMap<T> {
throw new IllegalArgumentException(msg);
}
- adjacency.get(source).put(target, weight);
+ adjacency.get(source).get().put(target, weight);
}
/**
@@ -215,8 +207,7 @@ public class AdjacencyMap<T> {
* 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 fe3d891..b48fcd0 100644
--- a/base/src/main/java/bjc/utils/graph/Edge.java
+++ b/base/src/main/java/bjc/utils/graph/Edge.java
@@ -28,11 +28,8 @@ public class Edge<T> {
* 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");
- }
+ 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;
@@ -41,27 +38,23 @@ public class Edge<T> {
@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;
+ 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)
+ 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))
+ } else if (target == null) {
+ if (other.target != null) return false;
+ } else if (!target.equals(other.target)) {
return false;
+ }
return true;
}
diff --git a/base/src/main/java/bjc/utils/graph/Graph.java b/base/src/main/java/bjc/utils/graph/Graph.java
index 8ff5647..f32e07f 100644
--- a/base/src/main/java/bjc/utils/graph/Graph.java
+++ b/base/src/main/java/bjc/utils/graph/Graph.java
@@ -10,11 +10,11 @@ import java.util.Set;
import java.util.function.BiConsumer;
import java.util.function.BiPredicate;
-import bjc.data.IHolder;
+import bjc.data.Holder;
import bjc.data.Identity;
import bjc.funcdata.FunctionalMap;
-import bjc.funcdata.IList;
-import bjc.funcdata.IMap;
+import bjc.funcdata.ListEx;
+import bjc.funcdata.MapEx;
/**
* A directed weighted graph, where the vertices have some arbitrary label.
@@ -47,7 +47,7 @@ public class Graph<T> {
}
/** The backing representation of the graph. */
- private final IMap<T, IMap<T, Integer>> backing;
+ private final MapEx<T, MapEx<T, Integer>> backing;
/** Create a new empty graph. */
public Graph() {
@@ -72,19 +72,14 @@ public class Graph<T> {
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");
- }
+ 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<T, Integer>());
- }
+ if (!backing.containsKey(source)) backing.put(source, new FunctionalMap<T, Integer>());
/* Add the edge to the graph. */
- backing.get(source).put(target, distance);
+ backing.get(source).get().put(target, distance);
/* Handle possible directed edges. */
if (!directed) {
@@ -92,7 +87,7 @@ public class Graph<T> {
backing.put(target, new FunctionalMap<T, Integer>());
}
- backing.get(target).put(source, distance);
+ backing.get(target).get().put(source, distance);
}
}
@@ -110,16 +105,11 @@ public class Graph<T> {
*/
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) {
- throw new NullPointerException("Action must not be null");
- }
+ 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);
- }
+ if (matcher.test(target, weight)) action.accept(target, weight);
});
}
@@ -130,14 +120,15 @@ public class Graph<T> {
* 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) {
+ public MapEx<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);
+ return backing.get(source).get();
}
/**
@@ -168,7 +159,7 @@ public class Graph<T> {
final Set<T> visited = new HashSet<>();
/* Start at the initial vertex and visit it */
- final IHolder<T> source = new Identity<>(getInitial());
+ final Holder<T> source = new Identity<>(getInitial());
visited.add(source.getValue());
@@ -176,14 +167,17 @@ public class Graph<T> {
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);
+ forAllEdgesMatchingAt(source.getValue(),
+ (target, weight) -> !visited.contains(target),
+ (target, weight) -> {
+ final T vert = source.unwrap(vertex -> vertex);
- available.add(new Edge<>(vert, target, weight));
- });
+ available.add(new Edge<>(vert, target, weight));
+ }
+ );
/* Get the edge with the minimum distance. */
- final IHolder<Edge<T>> minimum = new Identity<>(available.poll());
+ final Holder<Edge<T>> minimum = new Identity<>(available.poll());
/*
* Only consider edges where we haven't visited the target of the edge.
@@ -219,7 +213,7 @@ public class Graph<T> {
*
* @return A unmodifiable set of all the vertices in the graph.
*/
- public IList<T> getVertices() {
+ public ListEx<T> getVertices() {
return backing.keyList();
}
@@ -253,7 +247,7 @@ public class Graph<T> {
throw new NoSuchElementException(msg);
}
- backing.get(source).remove(target);
+ backing.get(source).get().remove(target);
/*
* Uncomment this to turn the graph undirected
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-11 15:32:38 +0000