summaryrefslogtreecommitdiff
path: root/BJC-Utils2/src/main/java/bjc/utils/graph
diff options
context:
space:
mode:
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/graph')
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java76
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java30
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java39
3 files changed, 73 insertions, 72 deletions
diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
index 9d415b1..446ab5b 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -1,5 +1,11 @@
package bjc.utils.graph;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.io.PrintStream;
+import java.util.InputMismatchException;
+import java.util.Scanner;
+
import bjc.utils.data.IHolder;
import bjc.utils.data.Identity;
import bjc.utils.funcdata.FunctionalList;
@@ -8,12 +14,6 @@ import bjc.utils.funcdata.IList;
import bjc.utils.funcdata.IMap;
import bjc.utils.funcutils.FuncUtils;
-import java.io.InputStream;
-import java.io.OutputStream;
-import java.io.PrintStream;
-import java.util.InputMismatchException;
-import java.util.Scanner;
-
/**
* An adjacency map representing a graph
*
@@ -30,24 +30,24 @@ public class AdjacencyMap<T> {
* The stream of text to read in
* @return An adjacency map defined by the text
*/
- public static AdjacencyMap<Integer> fromStream(InputStream stream) {
- if(stream == null) throw new NullPointerException("Input source must not be null");
+ public static AdjacencyMap<Integer> fromStream(final InputStream stream) {
+ 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;
- String possible = input.next();
+ final String possible = input.next();
try {
// First, read in number of vertices
vertexCount = Integer.parseInt(possible);
- } catch(NumberFormatException nfex) {
- InputMismatchException imex = new InputMismatchException(
+ } catch (final NumberFormatException nfex) {
+ final InputMismatchException imex = new InputMismatchException(
"The first line must contain the number of vertices. " + possible
+ " is not a valid number");
@@ -56,16 +56,16 @@ public class AdjacencyMap<T> {
throw imex;
}
- if(vertexCount <= 0)
+ if (vertexCount <= 0)
throw new InputMismatchException("The number of vertices must be greater than 0");
- IList<Integer> vertices = new FunctionalList<>();
+ final IList<Integer> vertices = new FunctionalList<>();
FuncUtils.doTimes(vertexCount, (vertexNo) -> vertices.add(vertexNo));
adjacency = new AdjacencyMap<>(vertices);
- IHolder<Integer> row = new Identity<>(0);
+ final IHolder<Integer> row = new Identity<>(0);
input.forEachRemaining((strang) -> {
readRow(adjacency, vertexCount, row, strang);
@@ -75,22 +75,22 @@ public class AdjacencyMap<T> {
return adjacency;
}
- private static void readRow(AdjacencyMap<Integer> adjacency, int vertexCount, IHolder<Integer> row,
- String strang) {
- String[] parts = strang.split(" ");
+ 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)
+ if (parts.length != vertexCount)
throw new InputMismatchException("Must specify a weight for all " + vertexCount + " vertices");
int column = 0;
- for(String part : parts) {
+ for (final String part : parts) {
int weight;
try {
weight = Integer.parseInt(part);
- } catch(NumberFormatException nfex) {
- InputMismatchException imex = new InputMismatchException(
+ } catch (final NumberFormatException nfex) {
+ final InputMismatchException imex = new InputMismatchException(
"" + part + " is not a valid weight.");
imex.initCause(nfex);
@@ -109,7 +109,7 @@ public class AdjacencyMap<T> {
/**
* The backing storage of the map
*/
- private IMap<T, IMap<T, Integer>> adjacency = new FunctionalMap<>();
+ private final IMap<T, IMap<T, Integer>> adjacency = new FunctionalMap<>();
/**
* Create a new map from a set of vertices
@@ -117,11 +117,11 @@ public class AdjacencyMap<T> {
* @param vertices
* The set of vertices to create a map from
*/
- public AdjacencyMap(IList<T> vertices) {
- if(vertices == null) throw new NullPointerException("Vertices must not be null");
+ public AdjacencyMap(final IList<T> vertices) {
+ if (vertices == null) throw new NullPointerException("Vertices must not be null");
vertices.forEach(vertex -> {
- IMap<T, Integer> row = new FunctionalMap<>();
+ final IMap<T, Integer> row = new FunctionalMap<>();
vertices.forEach(target -> {
row.put(target, 0);
@@ -137,13 +137,13 @@ public class AdjacencyMap<T> {
* @return Whether or not the graph is directed
*/
public boolean isDirected() {
- IHolder<Boolean> result = new Identity<>(true);
+ final IHolder<Boolean> result = new Identity<>(true);
adjacency.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
- int inverseValue = adjacency.get(targetKey).get(sourceKey);
+ final int inverseValue = adjacency.get(targetKey).get(sourceKey);
- if(targetValue != inverseValue) {
+ if (targetValue != inverseValue) {
result.replace(false);
}
});
@@ -162,14 +162,14 @@ public class AdjacencyMap<T> {
* @param weight
* The weight of the edge
*/
- public void setWeight(T source, T target, int weight) {
- if(source == null)
+ 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");
+ else if (target == null) throw new NullPointerException("Target vertex must not be null");
- if(!adjacency.containsKey(source))
+ if (!adjacency.containsKey(source))
throw new IllegalArgumentException("Source vertex " + source + " isn't present in map");
- else if(!adjacency.containsKey(target))
+ else if (!adjacency.containsKey(target))
throw new IllegalArgumentException("Target vertex " + target + " isn't present in map");
adjacency.get(source).put(target, weight);
@@ -181,7 +181,7 @@ public class AdjacencyMap<T> {
* @return The new representation of this graph
*/
public Graph<T> toGraph() {
- Graph<T> ret = new Graph<>();
+ final Graph<T> ret = new Graph<>();
adjacency.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
@@ -198,10 +198,10 @@ public class AdjacencyMap<T> {
* @param sink
* The stream to convert to
*/
- public void toStream(OutputStream sink) {
- if(sink == null) throw new NullPointerException("Output source must not be null");
+ public void toStream(final OutputStream sink) {
+ if (sink == null) throw new NullPointerException("Output source must not be null");
- PrintStream outputPrinter = new PrintStream(sink);
+ final PrintStream outputPrinter = new PrintStream(sink);
adjacency.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
index 37aff29..0152e3d 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
@@ -29,10 +29,10 @@ public class Edge<T> {
* @param distance
* The distance between initial and terminal edge
*/
- public Edge(T initial, T terminal, int distance) {
- if(initial == null)
+ 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");
+ else if (terminal == null) throw new NullPointerException("Terminal node must not be null");
this.source = initial;
this.target = terminal;
@@ -40,25 +40,25 @@ public class Edge<T> {
}
@Override
- public boolean equals(Object obj) {
- if(this == obj)
+ public boolean equals(final Object 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 {
- Edge<?> other = (Edge<?>) obj;
+ 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;
}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
index ff36b2b..280a7f5 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
@@ -1,11 +1,5 @@
package bjc.utils.graph;
-import bjc.utils.data.IHolder;
-import bjc.utils.data.Identity;
-import bjc.utils.funcdata.FunctionalMap;
-import bjc.utils.funcdata.IList;
-import bjc.utils.funcdata.IMap;
-
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
@@ -16,6 +10,12 @@ import java.util.Set;
import java.util.function.BiConsumer;
import java.util.function.BiPredicate;
+import bjc.utils.data.IHolder;
+import bjc.utils.data.Identity;
+import bjc.utils.funcdata.FunctionalMap;
+import bjc.utils.funcdata.IList;
+import bjc.utils.funcdata.IMap;
+
/**
* A directed weighted graph, where the vertices have some arbitrary label
*
@@ -35,8 +35,8 @@ public class Graph<T> {
* The list of edges to build from
* @return A graph built from the provided edge-list
*/
- public static <E> Graph<E> fromEdgeList(List<Edge<E>> edges) {
- Graph<E> g = new Graph<>();
+ public static <E> Graph<E> fromEdgeList(final List<Edge<E>> edges) {
+ final Graph<E> g = new Graph<>();
edges.forEach(edge -> {
g.addEdge(edge.getSource(), edge.getTarget(), edge.getDistance(), true);
@@ -70,7 +70,7 @@ public class Graph<T> {
* @param directed
* Whether or not
*/
- public void addEdge(T source, T target, int distance, 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)
throw new NullPointerException("The source vertex cannot be null");
@@ -105,7 +105,8 @@ public class Graph<T> {
* @param action
* The action to execute for matching edges
*/
- public void forAllEdgesMatchingAt(T source, BiPredicate<T, Integer> matcher, BiConsumer<T, Integer> action) {
+ 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");
@@ -124,7 +125,7 @@ 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(T source) {
+ public IMap<T, Integer> getEdges(final T source) {
// Can't find edges for a null source
if (source == null)
throw new NullPointerException("The source cannot be null.");
@@ -153,17 +154,17 @@ public class Graph<T> {
*/
public List<Edge<T>> getMinimumSpanningTree() {
// Set of all of the currently available edges
- Queue<Edge<T>> available = new PriorityQueue<>(10,
+ final Queue<Edge<T>> available = new PriorityQueue<>(10,
(left, right) -> left.getDistance() - right.getDistance());
// The MST of the graph
- List<Edge<T>> minimums = new ArrayList<>();
+ final List<Edge<T>> minimums = new ArrayList<>();
// The set of all of the visited vertices.
- Set<T> visited = new HashSet<>();
+ final Set<T> visited = new HashSet<>();
// Start at the initial vertex and visit it
- IHolder<T> source = new Identity<>(getInitial());
+ final IHolder<T> source = new Identity<>(getInitial());
visited.add(source.getValue());
@@ -174,13 +175,13 @@ public class Graph<T> {
forAllEdgesMatchingAt(source.getValue(), (target, weight) -> {
return !visited.contains(target);
}, (target, weight) -> {
- T vert = source.unwrap(vertex -> vertex);
+ final T vert = source.unwrap(vertex -> vertex);
available.add(new Edge<>(vert, target, weight));
});
// Get the edge with the minimum distance
- IHolder<Edge<T>> minimum = new Identity<>(available.poll());
+ final IHolder<Edge<T>> minimum = new Identity<>(available.poll());
// Only consider edges where we haven't visited the
// target of
@@ -228,7 +229,7 @@ public class Graph<T> {
* @param target
* The target vertex for the edge
*/
- public void removeEdge(T source, T target) {
+ public void removeEdge(final T source, final T target) {
// Can't remove things w/ null vertices
if (source == null)
throw new NullPointerException("The source vertex cannot be null");
@@ -253,7 +254,7 @@ public class Graph<T> {
* @return A adjacency map representing this graph
*/
public AdjacencyMap<T> toAdjacencyMap() {
- AdjacencyMap<T> adjacency = new AdjacencyMap<>(backing.keyList());
+ final AdjacencyMap<T> adjacency = new AdjacencyMap<>(backing.keyList());
backing.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 09:27:56 +0000