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.java65
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java48
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java77
3 files changed, 81 insertions, 109 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 5640ab6..9d415b1 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -1,11 +1,5 @@
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;
@@ -14,9 +8,15 @@ 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
- *
+ *
* @author ben
*
* @param <T>
@@ -25,20 +25,18 @@ import bjc.utils.funcutils.FuncUtils;
public class AdjacencyMap<T> {
/**
* Create an adjacency map from a stream of text
- *
+ *
* @param stream
* 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");
- }
+ 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;
@@ -48,7 +46,7 @@ public class AdjacencyMap<T> {
try {
// First, read in number of vertices
vertexCount = Integer.parseInt(possible);
- } catch (NumberFormatException nfex) {
+ } catch(NumberFormatException nfex) {
InputMismatchException imex = new InputMismatchException(
"The first line must contain the number of vertices. " + possible
+ " is not a valid number");
@@ -58,9 +56,8 @@ 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<>();
@@ -82,18 +79,17 @@ public class AdjacencyMap<T> {
String strang) {
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(String part : parts) {
int weight;
try {
weight = Integer.parseInt(part);
- } catch (NumberFormatException nfex) {
+ } catch(NumberFormatException nfex) {
InputMismatchException imex = new InputMismatchException(
"" + part + " is not a valid weight.");
@@ -117,14 +113,12 @@ public class AdjacencyMap<T> {
/**
* Create a new map from a set of vertices
- *
+ *
* @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");
- }
+ if(vertices == null) throw new NullPointerException("Vertices must not be null");
vertices.forEach(vertex -> {
IMap<T, Integer> row = new FunctionalMap<>();
@@ -139,7 +133,7 @@ public class AdjacencyMap<T> {
/**
* Check if the graph is directed
- *
+ *
* @return Whether or not the graph is directed
*/
public boolean isDirected() {
@@ -149,7 +143,7 @@ public class AdjacencyMap<T> {
sourceValue.forEach((targetKey, targetValue) -> {
int inverseValue = adjacency.get(targetKey).get(sourceKey);
- if (targetValue != inverseValue) {
+ if(targetValue != inverseValue) {
result.replace(false);
}
});
@@ -160,7 +154,7 @@ public class AdjacencyMap<T> {
/**
* Set the weight of an edge
- *
+ *
* @param source
* The source node of the edge
* @param target
@@ -169,24 +163,21 @@ public class AdjacencyMap<T> {
* The weight of the edge
*/
public void setWeight(T source, T target, int weight) {
- if (source == 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");
- }
+ 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);
}
/**
* Convert this to a different graph representation
- *
+ *
* @return The new representation of this graph
*/
public Graph<T> toGraph() {
@@ -203,14 +194,12 @@ public class AdjacencyMap<T> {
/**
* Convert an adjacency map back into a stream
- *
+ *
* @param sink
* The stream to convert to
*/
public void toStream(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");
PrintStream outputPrinter = new PrintStream(sink);
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 c77c0ba..37aff29 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
@@ -2,7 +2,7 @@ package bjc.utils.graph;
/**
* An edge in a weighted graph
- *
+ *
* @author ben
*
* @param <T>
@@ -21,7 +21,7 @@ public class Edge<T> {
/**
* Create a new edge with set parameters
- *
+ *
* @param initial
* The initial node of the edge
* @param terminal
@@ -30,11 +30,9 @@ public class Edge<T> {
* The distance between initial and terminal edge
*/
public Edge(T initial, T terminal, int distance) {
- if (initial == 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");
- }
+ else if(terminal == null) throw new NullPointerException("Terminal node must not be null");
this.source = initial;
this.target = terminal;
@@ -43,30 +41,24 @@ public class Edge<T> {
@Override
public boolean equals(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 {
+ else {
Edge<?> other = (Edge<?>) obj;
- if (distance != other.distance) {
- return false;
- } else if (source == null) {
- if (other.source != null) {
- return false;
- }
- } else if (!source.equals(other.source)) {
+ if(distance != other.distance)
return false;
- } else if (target == null) {
- if (other.target != null) {
- return false;
- }
- } else if (!target.equals(other.target)) {
+ 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;
return true;
}
@@ -74,7 +66,7 @@ public class Edge<T> {
/**
* Get the distance in this edge
- *
+ *
* @return The distance between the initial and terminal nodes of this
* edge
*/
@@ -84,7 +76,7 @@ public class Edge<T> {
/**
* Get the initial node of an edge
- *
+ *
* @return The initial node of this edge
*/
public T getSource() {
@@ -93,7 +85,7 @@ public class Edge<T> {
/**
* Get the target node of an edge
- *
+ *
* @return The target node of this edge
*/
public T getTarget() {
@@ -107,8 +99,8 @@ public class Edge<T> {
int result = 1;
result = prime * result + distance;
- result = prime * result + ((source == null) ? 0 : source.hashCode());
- result = prime * result + ((target == null) ? 0 : target.hashCode());
+ result = prime * result + (source == null ? 0 : source.hashCode());
+ result = prime * result + (target == null ? 0 : target.hashCode());
return result;
}
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 70fb555..694aa02 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
@@ -1,5 +1,11 @@
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;
@@ -10,15 +16,9 @@ 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
- *
+ *
* @author ben
*
* @param <T>
@@ -27,10 +27,10 @@ import bjc.utils.funcdata.IMap;
public class Graph<T> {
/**
* Create a graph from a list of edges
- *
+ *
* @param <E>
* The type of data stored in the edges
- *
+ *
* @param edges
* The list of edges to build from
* @return A graph built from the provided edge-list
@@ -59,7 +59,7 @@ public class Graph<T> {
/**
* Add a edge to the graph
- *
+ *
* @param source
* The source vertex for this edge
* @param target
@@ -72,14 +72,12 @@ public class Graph<T> {
*/
public void addEdge(T source, T target, int distance, 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) {
- throw new NullPointerException("The target 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)) {
+ if(!backing.containsKey(source)) {
backing.put(source, new FunctionalMap<T, Integer>());
}
@@ -87,8 +85,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>());
}
@@ -99,7 +97,7 @@ public class Graph<T> {
/**
* Execute an action for all edges of a specific vertex matching
* conditions
- *
+ *
* @param source
* The vertex to test edges for
* @param matcher
@@ -108,14 +106,12 @@ public class Graph<T> {
* The action to execute for matching edges
*/
public void forAllEdgesMatchingAt(T source, BiPredicate<T, Integer> matcher, BiConsumer<T, Integer> action) {
- if (matcher == null) {
+ if(matcher == null)
throw new NullPointerException("Matcher must not be null");
- } else if (action == null) {
- throw new NullPointerException("Action 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)) {
+ if(matcher.test(target, weight)) {
action.accept(target, weight);
}
});
@@ -123,25 +119,24 @@ public class Graph<T> {
/**
* Get all the edges that begin at a particular source vertex
- *
+ *
* @param 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(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);
}
/**
* Get the initial vertex of the graph
- *
+ *
* @return The initial vertex of the graph
*/
public T getInitial() {
@@ -153,7 +148,7 @@ public class Graph<T> {
*
* If the graph is non-connected, this will lead to unpredictable
* results.
- *
+ *
* @return a list of edges that constitute the MST
*/
public List<Edge<T>> getMinimumSpanningTree() {
@@ -173,7 +168,7 @@ 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) -> {
@@ -188,7 +183,7 @@ public class Graph<T> {
// Only consider edges where we haven't visited the
// target of
// the edge
- while (visited.contains(minimum.getValue())) {
+ while(visited.contains(minimum.getValue())) {
minimum.transform((edge) -> available.poll());
}
@@ -207,7 +202,7 @@ public class Graph<T> {
/**
* Get the count of the vertices in this graph
- *
+ *
* @return A count of the vertices in this graph
*/
public int getVertexCount() {
@@ -216,7 +211,7 @@ public class Graph<T> {
/**
* Get all of the vertices in this graph.
- *
+ *
* @return A unmodifiable set of all the vertices in the graph.
*/
public IList<T> getVertices() {
@@ -225,7 +220,7 @@ public class Graph<T> {
/**
* Remove the edge starting at the source and ending at the target
- *
+ *
* @param source
* The source vertex for the edge
* @param target
@@ -233,20 +228,16 @@ public class Graph<T> {
*/
public void removeEdge(T source, 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) {
- throw new NullPointerException("The target vertex cannot be 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))
throw new NoSuchElementException("vertex " + source + " does not exist.");
- }
- if (!backing.containsKey(target)) {
+ if(!backing.containsKey(target))
throw new NoSuchElementException("vertex " + target + " does not exist.");
- }
backing.get(source).remove(target);
@@ -256,7 +247,7 @@ public class Graph<T> {
/**
* Convert a graph into a adjacency map/matrix
- *
+ *
* @return A adjacency map representing this graph
*/
public AdjacencyMap<T> toAdjacencyMap() {
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 17:01:38 +0000