summaryrefslogtreecommitdiff
path: root/base/src
diff options
context:
space:
mode:
Diffstat (limited to 'base/src')
-rw-r--r--base/src/main/java/bjc/utils/graph/AdjacencyMap.java46
-rw-r--r--base/src/main/java/bjc/utils/graph/Edge.java83
-rw-r--r--base/src/main/java/bjc/utils/graph/Graph.java103
3 files changed, 76 insertions, 156 deletions
diff --git a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
index 978b21d..04fe4c8 100644
--- a/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
+++ b/base/src/main/java/bjc/utils/graph/AdjacencyMap.java
@@ -22,7 +22,7 @@ import bjc.utils.funcutils.FuncUtils;
* @param <T>
* The type of the nodes in the graph
*/
-public class AdjacencyMap<T> {
+public class AdjacencyMap<T, W> {
/**
* Create an adjacency map from a stream of text
*
@@ -31,11 +31,11 @@ public class AdjacencyMap<T> {
*
* @return An adjacency map defined by the text
*/
- public static AdjacencyMap<Integer> fromStream(final InputStream stream) {
+ public static AdjacencyMap<Integer, Integer> fromStream(final InputStream stream) {
if (stream == null) throw new NullPointerException("Input source must not be null");
/* Create the adjacency map. */
- AdjacencyMap<Integer> adjacency;
+ AdjacencyMap<Integer, Integer> adjacency;
try (Scanner input = new Scanner(stream)) {
input.useDelimiter("\n");
@@ -79,7 +79,7 @@ public class AdjacencyMap<T> {
}
/* Read a row of edges. */
- private static void readRow(final AdjacencyMap<Integer> adjacency,
+ private static void readRow(final AdjacencyMap<Integer, Integer> adjacency,
final int vertexCount, final Holder<Integer> row, final String strang) {
final String[] parts = strang.split(" ");
@@ -106,7 +106,7 @@ public class AdjacencyMap<T> {
throw imex;
}
- adjacency.setWeight(row.getValue(), column, weight);
+ adjacency.setLabel(row.getValue(), column, weight);
column++;
}
@@ -115,7 +115,7 @@ public class AdjacencyMap<T> {
}
/** The backing storage of the map */
- private final MapEx<T, MapEx<T, Integer>> adjacency = new FunctionalMap<>();
+ private final MapEx<T, MapEx<T, W>> adjacency = new FunctionalMap<>();
/**
* Create a new map from a set of vertices
@@ -127,10 +127,10 @@ public class AdjacencyMap<T> {
if (vertices == null) throw new NullPointerException("Vertices must not be null");
vertices.forEach(vertex -> {
- final MapEx<T, Integer> row = new FunctionalMap<>();
+ final MapEx<T, W> row = new FunctionalMap<>();
vertices.forEach(target -> {
- row.put(target, 0);
+ row.put(target, null);
});
adjacency.put(vertex, row);
@@ -147,7 +147,7 @@ public class AdjacencyMap<T> {
adjacency.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
- final int inverseValue = adjacency.get(targetKey).get().get(sourceKey).get();
+ final W inverseValue = adjacency.get(targetKey).get().get(sourceKey).get();
if (targetValue != inverseValue) result.replace(false);
});
@@ -157,16 +157,16 @@ public class AdjacencyMap<T> {
}
/**
- * Set the weight of an edge.
+ * Set the label of an edge.
*
* @param source
* The source node of the edge.
* @param target
* The target node of the edge.
- * @param weight
+ * @param label
* The weight of the edge.
*/
- public void setWeight(final T source, final T target, final int weight) {
+ public void setLabel(final T source, final T target, final W label) {
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");
@@ -180,7 +180,7 @@ public class AdjacencyMap<T> {
throw new IllegalArgumentException(msg);
}
- adjacency.get(source).get().put(target, weight);
+ adjacency.get(source).get().put(target, label);
}
/**
@@ -188,8 +188,8 @@ public class AdjacencyMap<T> {
*
* @return The new representation of this graph.
*/
- public Graph<T> toGraph() {
- final Graph<T> ret = new Graph<>();
+ public Graph<T, W> toGraph() {
+ final Graph<T, W> ret = new Graph<>();
adjacency.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
@@ -209,16 +209,14 @@ public class AdjacencyMap<T> {
public void toStream(final OutputStream sink) {
if (sink == null) throw new NullPointerException("Output source must not be null");
- final PrintStream outputPrinter = new PrintStream(sink);
+ try (PrintStream outputPrinter = new PrintStream(sink)) {
+ adjacency.forEach((sourceKey, sourceValue) -> {
+ sourceValue.forEach((targetKey, targetValue) -> {
+ outputPrinter.printf("%d", targetValue);
+ });
- adjacency.forEach((sourceKey, sourceValue) -> {
- sourceValue.forEach((targetKey, targetValue) -> {
- outputPrinter.printf("%d", targetValue);
+ outputPrinter.println();
});
-
- outputPrinter.println();
- });
-
- outputPrinter.close();
+ }
}
}
diff --git a/base/src/main/java/bjc/utils/graph/Edge.java b/base/src/main/java/bjc/utils/graph/Edge.java
index b48fcd0..5b0eba3 100644
--- a/base/src/main/java/bjc/utils/graph/Edge.java
+++ b/base/src/main/java/bjc/utils/graph/Edge.java
@@ -1,16 +1,17 @@
package bjc.utils.graph;
+import java.util.Objects;
+
/**
* An edge in a weighted graph.
*
* @author ben
*
- * @param <T>
- * The type of the nodes in the graph.
+ * @param <T> The type of the nodes in the graph.
*/
-public class Edge<T> {
+public class Edge<T, W> {
/* The distance from initial to terminal node. */
- private final int distance;
+ private final W distance;
/* The initial and terminal nodes of this edge. */
private final T source, target;
@@ -18,54 +19,29 @@ public class Edge<T> {
/**
* Create a new edge with set parameters.
*
- * @param initial
- * The initial node of the edge.
+ * @param initial The initial node of the edge.
*
- * @param terminal
- * The terminal node of the edge.
+ * @param terminal The terminal node of the edge.
*
- * @param distance
- * The distance between initial and terminal edge.
+ * @param distance The distance between initial and terminal edge.
*/
- public Edge(final T initial, final T terminal, final int distance) {
- 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");
+ public Edge(final T initial, final T terminal, final W distance) {
+ 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");
this.source = initial;
this.target = terminal;
this.distance = distance;
}
- @Override
- public boolean equals(final Object obj) {
- if (this == obj) return true;
- else if (obj == null) return false;
- else if (getClass() != obj.getClass()) return false;
- else {
- final 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)) {
- return false;
- } else if (target == null) {
- if (other.target != null) return false;
- } else if (!target.equals(other.target)) {
- return false;
- }
-
- return true;
- }
- }
-
/**
* Get the distance in this edge.
*
* @return The distance between the initial and terminal nodes of this edge.
*/
- public int getDistance() {
+ public W getDistance() {
return distance;
}
@@ -88,24 +64,27 @@ public class Edge<T> {
}
@Override
- public int hashCode() {
- final int prime = 31;
-
- int result = 1;
-
- result = prime * result + distance;
- result = prime * result + (source == null ? 0 : source.hashCode());
- result = prime * result + (target == null ? 0 : target.hashCode());
+ public String toString() {
+ String msg = String.format("source vertex %s to target vertex %s with distance: %s", source, target, distance);
- return result;
+ return msg;
}
@Override
- public String toString() {
- String msg
- = String.format("source vertex %s to target vertex %s with distance: %s",
- source, target, distance);
+ public int hashCode() {
+ return Objects.hash(distance, source, target);
+ }
- return msg;
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ Edge<?, ?> other = (Edge<?, ?>) obj;
+ return Objects.equals(distance, other.distance) && Objects.equals(source, other.source)
+ && Objects.equals(target, other.target);
}
}
diff --git a/base/src/main/java/bjc/utils/graph/Graph.java b/base/src/main/java/bjc/utils/graph/Graph.java
index f32e07f..81653fc 100644
--- a/base/src/main/java/bjc/utils/graph/Graph.java
+++ b/base/src/main/java/bjc/utils/graph/Graph.java
@@ -21,10 +21,10 @@ import bjc.funcdata.MapEx;
*
* @author ben
*
- * @param <T>
+ * @param <VertexLabel>
* The label for vertices.
*/
-public class Graph<T> {
+public class Graph<VertexLabel, EdgeLabel> {
/**
* Create a graph from a list of edges.
*
@@ -36,8 +36,8 @@ public class Graph<T> {
*
* @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<>();
+ public static <E, L> Graph<E, L> fromEdgeList(final List<Edge<E, L>> edges) {
+ final Graph<E, L> g = new Graph<>();
edges.forEach(edge -> {
g.addEdge(edge.getSource(), edge.getTarget(), edge.getDistance(), true);
@@ -47,7 +47,7 @@ public class Graph<T> {
}
/** The backing representation of the graph. */
- private final MapEx<T, MapEx<T, Integer>> backing;
+ private final MapEx<VertexLabel, MapEx<VertexLabel, EdgeLabel>> backing;
/** Create a new empty graph. */
public Graph() {
@@ -63,31 +63,31 @@ public class Graph<T> {
* @param target
* The target vertex for this edge.
*
- * @param distance
+ * @param label
* The distance from the source vertex to the target vertex.
*
* @param directed
* Whether or not the edge is directed or not.
*/
- public void addEdge(final T source, final T target, final int distance,
+ public void addEdge(final VertexLabel source, final VertexLabel target, final EdgeLabel label,
final boolean directed) {
/* Can't add edges with a null source or target. */
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");
/* Initialize adjacency list for vertices if necessary. */
- if (!backing.containsKey(source)) backing.put(source, new FunctionalMap<T, Integer>());
+ if (!backing.containsKey(source)) backing.put(source, new FunctionalMap<VertexLabel, EdgeLabel>());
/* Add the edge to the graph. */
- backing.get(source).get().put(target, distance);
+ backing.get(source).get().put(target, label);
/* Handle possible directed edges. */
if (!directed) {
if (!backing.containsKey(target)) {
- backing.put(target, new FunctionalMap<T, Integer>());
+ backing.put(target, new FunctionalMap<VertexLabel, EdgeLabel>());
}
- backing.get(target).get().put(source, distance);
+ backing.get(target).get().put(source, label);
}
}
@@ -103,13 +103,13 @@ public class Graph<T> {
* @param action
* The action to execute for matching edges.
*/
- public void forAllEdgesMatchingAt(final T source,
- final BiPredicate<T, Integer> matcher, final BiConsumer<T, Integer> action) {
+ public void forAllEdgesMatchingAt(final VertexLabel source,
+ final BiPredicate<VertexLabel, EdgeLabel> matcher, final BiConsumer<VertexLabel, EdgeLabel> action) {
if (matcher == null) throw new NullPointerException("Matcher 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)) action.accept(target, weight);
+ getEdges(source).forEach((target, label) -> {
+ if (matcher.test(target, label)) action.accept(target, label);
});
}
@@ -120,7 +120,7 @@ public class Graph<T> {
* The vertex to use as a source.
* @return All of the edges with the specified vertex as a source.
*/
- public MapEx<T, Integer> getEdges(final T source) {
+ public MapEx<VertexLabel, EdgeLabel> getEdges(final VertexLabel source) {
/* Can't find edges for a null source. */
if (source == null) {
throw new NullPointerException("The source cannot be null.");
@@ -136,68 +136,11 @@ public class Graph<T> {
*
* @return The initial vertex of the graph.
*/
- public T getInitial() {
+ public VertexLabel getInitial() {
return backing.keyList().first();
}
- /**
- * Uses Prim's algorothm to calculate a MST for the graph.
- *
- * 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() {
- /* Set of all of the currently available edges. */
- final Queue<Edge<T>> available = new PriorityQueue<>(10,
- (left, right) -> left.getDistance() - right.getDistance());
-
- /* The MST of the graph. */
- final List<Edge<T>> minimums = new ArrayList<>();
-
- /* The set of all of the visited vertices. */
- final Set<T> visited = new HashSet<>();
-
- /* Start at the initial vertex and visit it */
- final Holder<T> source = new Identity<>(getInitial());
-
- visited.add(source.getValue());
-
- /* Make sure we visit all the nodes. */
- while (visited.size() != getVertexCount()) {
- /* Grab all edges adjacent to the provided edge. */
-
- forAllEdgesMatchingAt(source.getValue(),
- (target, weight) -> !visited.contains(target),
- (target, weight) -> {
- final T vert = source.unwrap(vertex -> vertex);
-
- available.add(new Edge<>(vert, target, weight));
- }
- );
-
- /* Get the edge with the minimum distance. */
- final Holder<Edge<T>> minimum = new Identity<>(available.poll());
-
- /*
- * Only consider edges where we haven't visited the target of the edge.
- */
- while (visited.contains(minimum.getValue().getTarget())) {
- minimum.transform(edge -> available.poll());
- }
-
- /* Add it to our MST. */
- minimums.add(minimum.getValue());
-
- /* Advance to the next node. */
- source.transform(vertex -> minimum.unwrap(edge -> edge.getTarget()));
-
- /* Visit this node. */
- visited.add(source.getValue());
- }
-
- return minimums;
- }
+
/**
* Get the count of the vertices in this graph.
@@ -213,7 +156,7 @@ public class Graph<T> {
*
* @return A unmodifiable set of all the vertices in the graph.
*/
- public ListEx<T> getVertices() {
+ public ListEx<VertexLabel> getVertices() {
return backing.keyList();
}
@@ -226,7 +169,7 @@ public class Graph<T> {
* @param target
* The target vertex for the edge.
*/
- public void removeEdge(final T source, final T target) {
+ public void removeEdge(final VertexLabel source, final VertexLabel target) {
/* Can't remove things w/ null vertices. */
if (source == null) {
throw new NullPointerException("The source vertex cannot be null");
@@ -261,12 +204,12 @@ public class Graph<T> {
*
* @return A adjacency map representing this graph.
*/
- public AdjacencyMap<T> toAdjacencyMap() {
- final AdjacencyMap<T> adjacency = new AdjacencyMap<>(backing.keyList());
+ public AdjacencyMap<VertexLabel, EdgeLabel> toAdjacencyMap() {
+ final AdjacencyMap<VertexLabel, EdgeLabel> adjacency = new AdjacencyMap<>(backing.keyList());
backing.forEach((sourceKey, sourceValue) -> {
sourceValue.forEach((targetKey, targetValue) -> {
- adjacency.setWeight(sourceKey, targetKey, targetValue);
+ adjacency.setLabel(sourceKey, targetKey, targetValue);
});
});
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 04:16:21 +0000