diff options
Diffstat (limited to 'base/src/main/java/bjc/utils/graph/Graph.java')
| -rw-r--r-- | base/src/main/java/bjc/utils/graph/Graph.java | 62 |
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 |
