summaryrefslogtreecommitdiff
path: root/BJC-Utils2/src/main/java/bjc/utils/graph
diff options
context:
space:
mode:
authorEVE <EVE@EVE-PC>2017-03-13 16:42:21 -0400
committerEVE <EVE@EVE-PC>2017-03-13 16:42:21 -0400
commit27bf571d6413c3cc6a5d664b5bddd38d21d7b1cd (patch)
tree847fb52acb091c1c613d37b8477094d5762c6988 /BJC-Utils2/src/main/java/bjc/utils/graph
parentaa807a96cae2c47259fb38f710640883060339e9 (diff)
Formatting
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/graph')
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java48
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java27
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java86
3 files changed, 66 insertions, 95 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 c04aa23..5640ab6 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -20,20 +20,19 @@ import bjc.utils.funcutils.FuncUtils;
* @author ben
*
* @param <T>
- * The type of the nodes in the graph
+ * The type of the nodes in the graph
*/
public class AdjacencyMap<T> {
/**
* Create an adjacency map from a stream of text
*
* @param stream
- * The stream of text to read in
+ * 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");
+ throw new NullPointerException("Input source must not be null");
}
// Create the adjacency map
@@ -51,8 +50,7 @@ public class AdjacencyMap<T> {
vertexCount = Integer.parseInt(possible);
} catch (NumberFormatException nfex) {
InputMismatchException imex = new InputMismatchException(
- "The first line must contain the number of vertices. "
- + possible
+ "The first line must contain the number of vertices. " + possible
+ " is not a valid number");
imex.initCause(nfex);
@@ -61,8 +59,7 @@ public class AdjacencyMap<T> {
}
if (vertexCount <= 0) {
- throw new InputMismatchException(
- "The number of vertices must be greater than 0");
+ throw new InputMismatchException("The number of vertices must be greater than 0");
}
IList<Integer> vertices = new FunctionalList<>();
@@ -81,14 +78,12 @@ public class AdjacencyMap<T> {
return adjacency;
}
- private static void readRow(AdjacencyMap<Integer> adjacency,
- int vertexCount, IHolder<Integer> row, String strang) {
+ private static void readRow(AdjacencyMap<Integer> adjacency, int vertexCount, IHolder<Integer> row,
+ String strang) {
String[] parts = strang.split(" ");
if (parts.length != vertexCount) {
- throw new InputMismatchException(
- "Must specify a weight for all " + vertexCount
- + " vertices");
+ throw new InputMismatchException("Must specify a weight for all " + vertexCount + " vertices");
}
int column = 0;
@@ -124,7 +119,7 @@ public class AdjacencyMap<T> {
* Create a new map from a set of vertices
*
* @param vertices
- * The set of vertices to create a map from
+ * The set of vertices to create a map from
*/
public AdjacencyMap(IList<T> vertices) {
if (vertices == null) {
@@ -167,27 +162,23 @@ public class AdjacencyMap<T> {
* Set the weight of an edge
*
* @param source
- * The source node of the edge
+ * The source node of the edge
* @param target
- * The target node of the edge
+ * The target node of the edge
* @param weight
- * The weight of the edge
+ * The weight of the edge
*/
public void setWeight(T source, T target, 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");
+ 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)) {
- throw new IllegalArgumentException("Source vertex "
- + source + " isn't present in map");
+ throw new IllegalArgumentException("Source vertex " + source + " isn't present in map");
} else if (!adjacency.containsKey(target)) {
- throw new IllegalArgumentException("Target vertex "
- + target+ " isn't present in map");
+ throw new IllegalArgumentException("Target vertex " + target + " isn't present in map");
}
adjacency.get(source).put(target, weight);
@@ -214,12 +205,11 @@ public class AdjacencyMap<T> {
* Convert an adjacency map back into a stream
*
* @param sink
- * The stream to convert to
+ * The stream to convert to
*/
public void toStream(OutputStream sink) {
if (sink == null) {
- throw new NullPointerException(
- "Output source must not be 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 2ad4132..c77c0ba 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
@@ -6,36 +6,34 @@ package bjc.utils.graph;
* @author ben
*
* @param <T>
- * The type of the nodes in the graph
+ * The type of the nodes in the graph
*/
public class Edge<T> {
/*
* The distance from initial to terminal node
*/
- private final int distance;
+ private final int distance;
/*
* The initial and terminal nodes of this edge
*/
- private final T source, target;
+ private final T source, target;
/**
* Create a new edge with set parameters
*
* @param initial
- * The initial node of the edge
+ * The initial node of the edge
* @param terminal
- * The terminal node of the edge
+ * The terminal node of the edge
* @param distance
- * The distance between initial and terminal edge
+ * The distance between initial and terminal edge
*/
public Edge(T initial, T terminal, int distance) {
if (initial == null) {
- throw new NullPointerException(
- "Initial node must not be null");
+ throw new NullPointerException("Initial node must not be null");
} else if (terminal == null) {
- throw new NullPointerException(
- "Terminal node must not be null");
+ throw new NullPointerException("Terminal node must not be null");
}
this.source = initial;
@@ -109,17 +107,14 @@ 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;
}
@Override
public String toString() {
- return " first vertex " + source + " to vertex " + target
- + " with distance: " + distance;
+ return " first vertex " + source + " to vertex " + target + " with distance: " + distance;
}
}
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 66fe580..70fb555 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
@@ -22,25 +22,24 @@ import bjc.utils.funcdata.IMap;
* @author ben
*
* @param <T>
- * The label for vertices
+ * The label for vertices
*/
public class Graph<T> {
/**
* Create a graph from a list of edges
*
* @param <E>
- * The type of data stored in the edges
+ * The type of data stored in the edges
*
* @param edges
- * The list of edges to build from
+ * 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<>();
edges.forEach(edge -> {
- g.addEdge(edge.getSource(), edge.getTarget(),
- edge.getDistance(), true);
+ g.addEdge(edge.getSource(), edge.getTarget(), edge.getDistance(), true);
});
return g;
@@ -62,29 +61,26 @@ public class Graph<T> {
* Add a edge to the graph
*
* @param source
- * The source vertex for this edge
+ * The source vertex for this edge
* @param target
- * The target vertex for this edge
+ * The target vertex for this edge
* @param distance
- * The distance from the source vertex to the target vertex
+ * The distance from the source vertex to the target
+ * vertex
* @param directed
- * Whether or not
+ * Whether or not
*/
- public void addEdge(T source, T target, int distance,
- boolean directed) {
+ public void addEdge(T source, T target, int distance, boolean directed) {
// Can't add edges with a null source or target
if (source == null) {
- throw new NullPointerException(
- "The source vertex cannot be null");
+ throw new NullPointerException("The source vertex cannot be null");
} else if (target == null) {
- throw new NullPointerException(
- "The target vertex cannot be 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>());
+ backing.put(source, new FunctionalMap<T, Integer>());
}
// Add the edge to the graph
@@ -93,8 +89,7 @@ public class Graph<T> {
// Handle possible directed edges
if (!directed) {
if (!backing.containsKey(target)) {
- backing.put(target,
- new FunctionalMap<T, Integer>());
+ backing.put(target, new FunctionalMap<T, Integer>());
}
backing.get(target).put(source, distance);
@@ -106,15 +101,13 @@ public class Graph<T> {
* conditions
*
* @param source
- * The vertex to test edges for
+ * The vertex to test edges for
* @param matcher
- * The conditions an edge must match
+ * The conditions an edge must match
* @param action
- * The action to execute for matching edges
+ * The action to execute for matching edges
*/
- public void forAllEdgesMatchingAt(T source,
- BiPredicate<T, Integer> matcher,
- BiConsumer<T, Integer> action) {
+ public void forAllEdgesMatchingAt(T source, BiPredicate<T, Integer> matcher, BiConsumer<T, Integer> action) {
if (matcher == null) {
throw new NullPointerException("Matcher must not be null");
} else if (action == null) {
@@ -132,7 +125,7 @@ public class Graph<T> {
* Get all the edges that begin at a particular source vertex
*
* @param source
- * The vertex to use as a 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) {
@@ -140,8 +133,7 @@ public class Graph<T> {
if (source == null) {
throw new NullPointerException("The source cannot be null.");
} else if (!backing.containsKey(source)) {
- throw new IllegalArgumentException(
- "Vertex " + source + " is not in graph");
+ throw new IllegalArgumentException("Vertex " + source + " is not in graph");
}
return backing.get(source);
@@ -159,7 +151,8 @@ public class Graph<T> {
/**
* Uses Prim's algorothm to calculate a MST for the graph.
*
- * If the graph is non-connected, this will lead to unpredictable results.
+ * If the graph is non-connected, this will lead to unpredictable
+ * results.
*
* @return a list of edges that constitute the MST
*/
@@ -183,19 +176,17 @@ public class Graph<T> {
while (visited.size() != getVertexCount()) {
// Grab all edges adjacent to the provided edge
- forAllEdgesMatchingAt(source.getValue(),
- (target, weight) -> {
- return !visited.contains(target);
- }, (target, weight) -> {
- available.add(new Edge<>(
- source.unwrap(vertex -> vertex),
- target, weight));
- });
+ forAllEdgesMatchingAt(source.getValue(), (target, weight) -> {
+ return !visited.contains(target);
+ }, (target, weight) -> {
+ available.add(new Edge<>(source.unwrap(vertex -> vertex), target, weight));
+ });
// Get the edge with the minimum distance
IHolder<Edge<T>> minimum = new Identity<>(available.poll());
- // Only consider edges where we haven't visited the target of
+ // Only consider edges where we haven't visited the
+ // target of
// the edge
while (visited.contains(minimum.getValue())) {
minimum.transform((edge) -> available.poll());
@@ -236,29 +227,25 @@ public class Graph<T> {
* Remove the edge starting at the source and ending at the target
*
* @param source
- * The source vertex for the edge
+ * The source vertex for the edge
* @param target
- * The target vertex for the edge
+ * The target vertex for the edge
*/
public void removeEdge(T source, T target) {
// Can't remove things w/ null vertices
if (source == null) {
- throw new NullPointerException(
- "The source vertex cannot be null");
+ throw new NullPointerException("The source vertex cannot be null");
} else if (target == null) {
- throw new NullPointerException(
- "The target vertex cannot be null");
+ throw new NullPointerException("The target vertex cannot be null");
}
// Can't remove if one vertice doesn't exists
if (!backing.containsKey(source)) {
- throw new NoSuchElementException(
- "vertex " + source + " does not exist.");
+ throw new NoSuchElementException("vertex " + source + " does not exist.");
}
if (!backing.containsKey(target)) {
- throw new NoSuchElementException(
- "vertex " + target + " does not exist.");
+ throw new NoSuchElementException("vertex " + target + " does not exist.");
}
backing.get(source).remove(target);
@@ -273,8 +260,7 @@ public class Graph<T> {
* @return A adjacency map representing this graph
*/
public AdjacencyMap<T> toAdjacencyMap() {
- AdjacencyMap<T> adjacency = new AdjacencyMap<>(
- backing.keyList());
+ AdjacencyMap<T> adjacency = new AdjacencyMap<>(backing.keyList());
backing.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {