diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/graph')
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; + } +} |