summaryrefslogtreecommitdiff
path: root/base/src/main/java/bjc/utils/graph/Graph.java
diff options
context:
space:
mode:
Diffstat (limited to 'base/src/main/java/bjc/utils/graph/Graph.java')
-rw-r--r--base/src/main/java/bjc/utils/graph/Graph.java62
1 files changed, 28 insertions, 34 deletions
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