summaryrefslogtreecommitdiff
path: root/base/src/main/java/bjc/utils/graph
diff options
context:
space:
mode:
authorbjculkin <bjculkin@mix.wvu.edu>2018-02-12 22:45:04 -0500
committerbjculkin <bjculkin@mix.wvu.edu>2018-02-12 22:45:04 -0500
commitdf94066e3af02ff02d5ab4d033a3d603f743234c (patch)
tree168a1edaf58d386c175ffb601e9d4da8e13d31e2 /base/src/main/java/bjc/utils/graph
parentae51c587c53f7ca311e556e3cbd0c5566d6c2843 (diff)
Formatting pass
Diffstat (limited to 'base/src/main/java/bjc/utils/graph')
-rw-r--r--base/src/main/java/bjc/utils/graph/AdjacencyMap.java53
-rw-r--r--base/src/main/java/bjc/utils/graph/Edge.java49
-rw-r--r--base/src/main/java/bjc/utils/graph/Graph.java84
3 files changed, 87 insertions, 99 deletions
diff --git a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
index 1598b25..965eccc 100644
--- a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
+++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -20,25 +20,24 @@ 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
+ * @return An adjacency map defined by the text
*/
public static AdjacencyMap<Integer> fromStream(final 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,8 +47,8 @@ public class AdjacencyMap<T> {
try {
/* First, read in number of vertices. */
vertexCount = Integer.parseInt(possible);
- } catch (final NumberFormatException nfex) {
- String msg = String.format(
+ } catch(final NumberFormatException nfex) {
+ String msg = String.format(
"The first line must contain the number of vertices. %s is not a valid number",
possible);
@@ -60,7 +59,7 @@ public class AdjacencyMap<T> {
throw imex;
}
- if (vertexCount <= 0)
+ if(vertexCount <= 0)
throw new InputMismatchException("The number of vertices must be greater than 0");
final IList<Integer> vertices = new FunctionalList<>();
@@ -84,7 +83,7 @@ public class AdjacencyMap<T> {
final IHolder<Integer> row, final String strang) {
final String[] parts = strang.split(" ");
- if (parts.length != vertexCount) {
+ if(parts.length != vertexCount) {
String msg = String.format("Must specify a weight for all %d vertices", vertexCount);
throw new InputMismatchException(msg);
@@ -92,12 +91,12 @@ public class AdjacencyMap<T> {
int column = 0;
- for (final String part : parts) {
+ for(final String part : parts) {
int weight;
try {
weight = Integer.parseInt(part);
- } catch (final NumberFormatException nfex) {
+ } catch(final NumberFormatException nfex) {
String msg = String.format("%d is not a valid weight.", part);
final InputMismatchException imex = new InputMismatchException(msg);
@@ -121,10 +120,10 @@ 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(final 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 -> {
final IMap<T, Integer> row = new FunctionalMap<>();
@@ -140,8 +139,7 @@ public class AdjacencyMap<T> {
/**
* Check if the graph is directed
*
- * @return
- * Whether or not the graph is directed
+ * @return Whether or not the graph is directed
*/
public boolean isDirected() {
final IHolder<Boolean> result = new Identity<>(true);
@@ -150,7 +148,7 @@ public class AdjacencyMap<T> {
sourceValue.forEach((targetKey, targetValue) -> {
final int inverseValue = adjacency.get(targetKey).get(sourceKey);
- if (targetValue != inverseValue) {
+ if(targetValue != inverseValue) {
result.replace(false);
}
});
@@ -163,24 +161,24 @@ 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(final T source, final T target, final int weight) {
- if (source == null) {
+ if(source == null) {
throw new NullPointerException("Source vertex must not be null");
- } else if (target == null) {
+ } else if(target == null) {
throw new NullPointerException("Target vertex must not be null");
}
- if (!adjacency.containsKey(source)) {
+ if(!adjacency.containsKey(source)) {
String msg = String.format("Source vertex %s isn't present in map", source);
throw new IllegalArgumentException(msg);
- } else if (!adjacency.containsKey(target)) {
+ } else if(!adjacency.containsKey(target)) {
String msg = String.format("Target vertex %s isn't present in map", target);
throw new IllegalArgumentException(msg);
@@ -192,8 +190,7 @@ public class AdjacencyMap<T> {
/**
* Convert this to a different graph representation.
*
- * @return
- * The new representation of this graph.
+ * @return The new representation of this graph.
*/
public Graph<T> toGraph() {
final Graph<T> ret = new Graph<>();
@@ -211,10 +208,10 @@ 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(final 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");
final PrintStream outputPrinter = new PrintStream(sink);
diff --git a/base/src/main/java/bjc/utils/graph/Edge.java b/base/src/main/java/bjc/utils/graph/Edge.java
index 9236464..e7e7b36 100644
--- a/base/src/main/java/bjc/utils/graph/Edge.java
+++ b/base/src/main/java/bjc/utils/graph/Edge.java
@@ -6,10 +6,10 @@ 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. */
+ /* The distance from initial to terminal node. */
private final int distance;
/* The initial and terminal nodes of this edge. */
@@ -19,18 +19,18 @@ public class Edge<T> {
* 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(final T initial, final T terminal, final int distance) {
- if (initial == null) {
+ if(initial == null) {
throw new NullPointerException("Initial node must not be null");
- } else if (terminal == null) {
+ } else if(terminal == null) {
throw new NullPointerException("Terminal node must not be null");
}
@@ -41,24 +41,24 @@ public class Edge<T> {
@Override
public boolean equals(final 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 {
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;
}
@@ -67,9 +67,8 @@ public class Edge<T> {
/**
* Get the distance in this edge.
*
- * @return
- * The distance between the initial and terminal nodes of this
- * edge.
+ * @return The distance between the initial and terminal nodes of this
+ * edge.
*/
public int getDistance() {
return distance;
@@ -78,8 +77,7 @@ public class Edge<T> {
/**
* Get the initial node of an edge.
*
- * @return
- * The initial node of this edge.
+ * @return The initial node of this edge.
*/
public T getSource() {
return source;
@@ -88,8 +86,7 @@ public class Edge<T> {
/**
* Get the target node of an edge.
*
- * @return
- * The target node of this edge.
+ * @return The target node of this edge.
*/
public T getTarget() {
return target;
@@ -110,8 +107,8 @@ public class Edge<T> {
@Override
public String toString() {
- String msg = String.format("source vertex %s to target vertex %s with distance: %s",
- source, target, distance);
+ String msg = String.format("source vertex %s to target vertex %s with distance: %s", source, target,
+ distance);
return msg;
}
diff --git a/base/src/main/java/bjc/utils/graph/Graph.java b/base/src/main/java/bjc/utils/graph/Graph.java
index d00dbae..83c2dc2 100644
--- a/base/src/main/java/bjc/utils/graph/Graph.java
+++ b/base/src/main/java/bjc/utils/graph/Graph.java
@@ -22,20 +22,19 @@ 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.
+ * @return A graph built from the provided edge-list.
*/
public static <E> Graph<E> fromEdgeList(final List<Edge<E>> edges) {
final Graph<E> g = new Graph<>();
@@ -59,27 +58,27 @@ 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 the edge is directed or not.
+ * Whether or not the edge is directed or not.
*/
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) {
+ if(source == null) {
throw new NullPointerException("The source vertex cannot be null");
- } else if (target == 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 +86,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>());
}
@@ -101,24 +100,24 @@ 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(final T source, final BiPredicate<T, Integer> matcher,
final BiConsumer<T, Integer> action) {
- if (matcher == null) {
+ if(matcher == null) {
throw new NullPointerException("Matcher must not be null");
- } else if (action == 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);
}
});
@@ -128,15 +127,14 @@ 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.
+ * 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) {
/* 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);
@@ -145,8 +143,7 @@ public class Graph<T> {
/**
* Get the initial vertex of the graph.
*
- * @return
- * The initial vertex of the graph.
+ * @return The initial vertex of the graph.
*/
public T getInitial() {
return backing.keyList().first();
@@ -158,8 +155,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.
+ * @return A list of edges that constitute the MST.
*/
public List<Edge<T>> getMinimumSpanningTree() {
/* Set of all of the currently available edges. */
@@ -178,7 +174,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) -> {
@@ -194,9 +190,9 @@ public class Graph<T> {
/*
* Only consider edges where we haven't visited the
- * target of the edge.
+ * target of the edge.
*/
- while (visited.contains(minimum.getValue().getTarget())) {
+ while(visited.contains(minimum.getValue().getTarget())) {
minimum.transform((edge) -> available.poll());
}
@@ -216,8 +212,7 @@ public class Graph<T> {
/**
* Get the count of the vertices in this graph.
*
- * @return
- * A count of the vertices in this graph.
+ * @return A count of the vertices in this graph.
*/
public int getVertexCount() {
return backing.size();
@@ -226,8 +221,7 @@ public class Graph<T> {
/**
* Get all of the vertices in this graph.
*
- * @return
- * A unmodifiable set of all the vertices in the graph.
+ * @return A unmodifiable set of all the vertices in the graph.
*/
public IList<T> getVertices() {
return backing.keyList();
@@ -237,27 +231,27 @@ 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(final T source, final 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) {
+ } 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)) {
String msg = String.format("vertex %s does not exist", source);
throw new NoSuchElementException(msg);
}
- if (!backing.containsKey(target)) {
+ if(!backing.containsKey(target)) {
String msg = String.format("vertex %s does not exist", target);
throw new NoSuchElementException(msg);
@@ -265,7 +259,8 @@ public class Graph<T> {
backing.get(source).remove(target);
- /* Uncomment this to turn the graph undirected
+ /*
+ * Uncomment this to turn the graph undirected
*
* graph.get(target).remove(source);
*/
@@ -274,8 +269,7 @@ public class Graph<T> {
/**
* Convert a graph into a adjacency map/matrix.
*
- * @return
- * A adjacency map representing this graph.
+ * @return A adjacency map representing this graph.
*/
public AdjacencyMap<T> toAdjacencyMap() {
final AdjacencyMap<T> adjacency = new AdjacencyMap<>(backing.keyList());