Updates to various things, and addition of a graph class.

4 files changed, 441 insertions, 0 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
new file mode 100644
index 0000000..7a79233
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -0,0 +1,100 @@
+package bjc.utils.graph;
+
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.io.PrintStream;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Scanner;
+import java.util.Set;
+import java.util.stream.IntStream;
+
+public class AdjacencyMap<T> {
+	private Map<T, Map<T, Integer>> adjMap;
+
+	public AdjacencyMap(Set<T> vertices) {
+		vertices.forEach(src -> {
+			Map<T, Integer> srcRow = new HashMap<>();
+
+			vertices.forEach(tgt -> srcRow.put(tgt, 0));
+
+			adjMap.put(src, srcRow);
+		});
+	}
+
+	public boolean isDirected() {
+		GenHolder<Boolean> res = new GenHolder<>(true);
+
+		adjMap.entrySet()
+				.forEach(src -> src.getValue().entrySet().forEach(tgt -> {
+					int lhs = tgt.getValue();
+					int rhs = adjMap.get(tgt.getKey()).get(src.getKey());
+
+					if (lhs != rhs) {
+						res.held = false;
+					}
+				}));
+
+		return res.held;
+	}
+
+	public void setWeight(T src, T tgt, int weight) {
+		adjMap.get(src).put(tgt, weight);
+	}
+
+	public Graph<T> toGraph() {
+		Graph<T> ret = new Graph<>();
+
+		adjMap.entrySet()
+				.forEach(src -> src.getValue().entrySet()
+						.forEach(tgt -> ret.addEdge(src.getKey(),
+								tgt.getKey(), tgt.getValue())));
+
+		return ret;
+	}
+
+	public static AdjacencyMap<Integer> fromStream(InputStream stream) {
+		Scanner scn = new Scanner(stream);
+		scn.useDelimiter("\n");
+
+		// First, read in number of vertices
+		int numVertices = Integer.parseInt(scn.next());
+
+		Set<Integer> vertices = new HashSet<>();
+		IntStream.range(0, numVertices).forEach(e -> vertices.add(e));
+
+		// Create the adjacency map
+		AdjacencyMap<Integer> aMap = new AdjacencyMap<>(vertices);
+
+		GenHolder<Integer> row = new GenHolder<>(0);
+
+		scn.forEachRemaining((strang) -> {
+			String[] parts = strang.split(" ");
+			int col = 0;
+
+			for (String part : parts) {
+				aMap.setWeight(row.held, col, Integer.parseInt(part));
+
+				col++;
+			}
+
+			row.held++;
+		});
+
+		scn.close();
+
+		return aMap;
+	}
+
+	public void toStream(OutputStream os) {
+		PrintStream ps = new PrintStream(os);
+
+		adjMap.entrySet().forEach(src -> {
+			src.getValue().entrySet()
+					.forEach(tgt -> ps.printf("%d ", tgt.getValue()));
+			ps.println();
+		});
+		ps.close();
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
new file mode 100644
index 0000000..9fb20c0
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Edge.java
@@ -0,0 +1,30 @@
+package bjc.utils.graph;
+
+public class Edge<T> {
+	private final T		source, target;
+	private final int	distance;
+
+	public Edge(T node1, T node2, int distance) {
+		this.source = node1;
+		this.target = node2;
+		this.distance = distance;
+	}
+
+	public T getSource() {
+		return source;
+	}
+
+	public T getTarget() {
+		return target;
+	}
+
+	public int getDistance() {
+		return distance;
+	}
+
+	@Override
+	public String toString() {
+		return " first vertex " + source + " to vertex " + target
+				+ " with distance: " + distance;
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/GenHolder.java b/BJC-Utils2/src/main/java/bjc/utils/graph/GenHolder.java
new file mode 100644
index 0000000..df363fa
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/GenHolder.java
@@ -0,0 +1,75 @@
+package bjc.utils.graph;
+
+import java.util.function.Function;
+
+/**
+ * Holds a single value of a specific type. This is used for indirect
+ * references to data, and more specifically for accessing non-final
+ * variables from a lambda. AKA the identity monad
+ * 
+ * @author ben
+ *
+ * @param <T>
+ *            The type of the data being held
+ */
+public class GenHolder<T> {
+	/**
+	 * The state this holder is responsible for.
+	 */
+	public T held;
+
+	/**
+	 * Creates a new empty holder, with its state set to null
+	 */
+	public GenHolder() {
+		held = null;
+	}
+
+	/**
+	 * Creates a new holder, with its state initialized to the provided
+	 * value
+	 * 
+	 * @param held
+	 *            The state to initialize this holder to.
+	 */
+	public GenHolder(T hld) {
+		held = hld;
+	}
+
+	/**
+	 * Apply the given transformation to the held value. Returns the holder
+	 * for allowing chaining of transforms
+	 * 
+	 * @param f
+	 *            The transform to apply to the value
+	 * @return The holder
+	 */
+	public GenHolder<T> transform(Function<T, T> f) {
+		held = f.apply(held);
+
+		return this;
+	}
+
+	/**
+	 * Return the result of applying the given transformation to the held
+	 * value Doesn't change the held value
+	 * 
+	 * @param f
+	 *            The transformation to apply
+	 * @return A holder with the transformed value
+	 */
+	public <NewT> GenHolder<NewT> map(Function<T, NewT> f) {
+		return new GenHolder<NewT>(f.apply(held));
+	}
+
+	/**
+	 * Returns a raw mapped value, not contained in a GenHolder
+	 * 
+	 * @param f
+	 *            The function to use for mapping the value
+	 * @return The mapped value outside of a GenHolder
+	 */
+	public <E> E unwrap(Function<T, E> f) {
+		return f.apply(held);
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
new file mode 100644
index 0000000..69e42e4
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/graph/Graph.java
@@ -0,0 +1,236 @@
+package bjc.utils.graph;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.PriorityQueue;
+import java.util.Queue;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.BiPredicate;
+
+/**
+ * A directed weighted graph, where the vertices have some arbitrary label
+ * 
+ * @author ben
+ *
+ * @param <T>
+ *            The label for vertices
+ */
+public class Graph<T> {
+
+	private final Map<T, Map<T, Integer>> graph;
+
+	/**
+	 * Create a new graph
+	 */
+	public Graph() {
+		graph = new HashMap<T, Map<T, Integer>>();
+	}
+
+	/**
+	 * Add a edge to the graph
+	 * 
+	 * @param source
+	 *            The source vertex for this edge
+	 * @param target
+	 *            The target vertex for this edge
+	 * @param distance
+	 *            The distance from the source vertex to the target vertex
+	 */
+	public void addEdge(T source, T target, int distance) {
+		// Can't add edges with a null source or target
+		if (source == null) {
+			throw new NullPointerException("The vertex 1 cannot be null");
+		}
+		if (target == null) {
+			throw new NullPointerException("The vertex 2 cannot be null");
+		}
+
+		// Initialize adjacency list for vertices if necessary
+		if (!graph.containsKey(source)) {
+			graph.put(source, new HashMap<T, Integer>());
+		}
+		if (!graph.containsKey(target)) {
+			graph.put(target, new HashMap<T, Integer>());
+		}
+
+		// Add the edge to the graph
+		graph.get(source).put(target, distance);
+
+		// Uncomment this to make the graph undirected
+		// graph.get(target).put(source, distance);
+	}
+
+	/**
+	 * Execute an action for all edges of a specific vertex matching
+	 * conditions
+	 * 
+	 * @param source
+	 *            The vertex to test edges for
+	 * @param bp
+	 *            The conditions an edge must match
+	 * @param bc
+	 *            The action to execute for matching edges
+	 */
+	public void forAllEdgesMatchingAt(T source, BiPredicate<T, Integer> bp,
+			BiConsumer<T, Integer> bc) {
+		getEdges(source).forEach((tgt, weight) -> {
+			if (bp.test(tgt, weight)) {
+				bc.accept(tgt, weight);
+			}
+		});
+	}
+
+	/**
+	 * 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 Map<T, Integer> getEdges(T source) {
+		// Can't find edges for a null source
+		if (source == null) {
+			throw new NullPointerException("The source cannot be null.");
+		}
+
+		return Collections.unmodifiableMap(graph.get(source));
+	}
+
+	/**
+	 * Get the initial vertex of the graph
+	 * 
+	 * @return The initial vertex of the graph
+	 */
+	public T getInitial() {
+		return graph.keySet().iterator().next();
+	}
+
+	/**
+	 * Uses Prim's algorothm to calculate a MST for the graph. If the graph
+	 * is non-connected, this will lead to unpredictable results.
+	 * 
+	 * @param graph
+	 *            a connected graph.
+	 * @return a list of edges that constitute the MST
+	 */
+	public List<Edge<T>> getMinSpanTree() {
+		// Set of all of the currently available edges
+		Queue<Edge<T>> availEdges = new PriorityQueue<Edge<T>>(10,
+				(e1, e2) -> e1.getDistance() - e2.getDistance());
+
+		// The MST of the graph
+		List<Edge<T>> minEdges = new ArrayList<Edge<T>>();
+
+		// The set of all of the visited vertices.
+		Set<T> visited = new HashSet<T>();
+
+		// Start at the initial vertex and visit it
+		GenHolder<T> src = new GenHolder<>(getInitial());
+		visited.add(src.held);
+
+		// Make sure we visit all the nodes
+		while (visited.size() != getVertexCount()) {
+			// Grab all edges adjacent to the provided edge
+
+			forAllEdgesMatchingAt(src.held,
+					(tgt, weight) -> !visited.contains(tgt),
+					(tgt, weight) -> availEdges
+							.add(new Edge<T>(src.held, tgt, weight)));
+
+			// Get the edge with the minimum distance
+			Edge<T> minEdge = availEdges.poll();
+
+			// Only consider edges where we haven't visited the target of
+			// the edge
+			while (visited.contains(minEdge.getTarget())) {
+				minEdge = availEdges.poll();
+			}
+
+			// Add it to our MST
+			minEdges.add(minEdge);
+
+			// Advance to the next node
+			src.held = minEdge.getTarget();
+
+			// Visit this node
+			visited.add(src.held);
+		}
+
+		return minEdges;
+	}
+
+	public int getVertexCount() {
+		return graph.size();
+	}
+
+	/**
+	 * Get all of the vertices in this graph.
+	 * 
+	 * @return A unmodifiable set of all the vertices in the graph.
+	 */
+	public Set<T> getVertices() {
+		return Collections.unmodifiableSet(graph.keySet());
+	}
+
+	/**
+	 * Remove the edge starting at the source and ending at the target
+	 * 
+	 * @param source
+	 *            The source vertex for the edge
+	 * @param target
+	 *            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 vertex 1 cannot be null");
+		}
+		if (target == null) {
+			throw new NullPointerException("The vertex 2 cannot be null");
+		}
+
+		// Can't remove if one vertice doesn't exists
+		if (!graph.containsKey(source)) {
+			throw new NoSuchElementException(
+					"vertex " + source + " does not exist.");
+		}
+		if (!graph.containsKey(target)) {
+			throw new NoSuchElementException(
+					"vertex " + target + " does not exist.");
+		}
+
+		graph.get(source).remove(target);
+
+		// Uncomment this to turn the graph undirected
+		// graph.get(target).remove(source);
+	}
+
+	/**
+	 * Convert a graph into a adjacency map/matrix
+	 * 
+	 * @return A adjacency map representing this graph
+	 */
+	public AdjacencyMap<T> toMap() {
+		AdjacencyMap<T> aMap = new AdjacencyMap<>(graph.keySet());
+
+		graph.entrySet().forEach(src -> src.getValue().forEach((tgt,
+				weight) -> aMap.setWeight(src.getKey(), tgt, weight)));
+
+		return aMap;
+	}
+
+	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()));
+
+		return g;
+	}
+}