4 files changed, 380 insertions, 0 deletions
diff --git a/base/src/main/java/bjc/utils/graph/ASGraph.java b/base/src/main/java/bjc/utils/graph/ASGraph.java
new file mode 100644
index 0000000..777598f
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/ASGraph.java
@@ -0,0 +1,179 @@
+package bjc.utils.graph;
+
+import java.util.*;
+import java.util.function.Function;
+
+import bjc.data.Pair;
+import bjc.esodata.*;
+import bjc.funcdata.Freezable;
+import bjc.funcdata.ObjectFrozen;
+import bjc.functypes.Unit;
+
+public class ASGraph<Node, Value, Label> implements Freezable<ASGraph<Node, Value, Label>> {
+	private Set<Node> nodes;
+	private Function<Node, Value> nodeValuer;
+	private PairMap<Node, Node, Label> arcMap;
+
+	// Used for implementation efficiency
+	private Multimap<Node, Value> nodeToValue;
+	private Multimap<Value, Node> valueToNode;
+
+	private boolean frozen;
+	private boolean deepFrozen;
+
+	public ASGraph(Function<Node, Value> valuer) {
+		this.nodes = new HashSet<>();
+		this.nodeValuer = valuer;
+		this.arcMap = new PairMap<>();
+
+		this.nodeToValue = new TSetMultimap<>();
+		this.valueToNode = new TSetMultimap<>();
+	}
+
+	/**
+	 * Retrieve a read-only view of the nodes
+	 * 
+	 * @return A read-only set of the nodes.
+	 */
+	public Set<Node> getNodes() {
+		return Collections.unmodifiableSet(nodes);
+	}
+
+	/**
+	 * Get the value for a node in the graph.
+	 * 
+	 * @param nd The node to check.
+	 * 
+	 * @return The value for that node.
+	 */
+	public Value getValue(Node nd) {
+		return nodeValuer.apply(nd);
+	}
+
+	/**
+	 * Add a node to the graph.
+	 * 
+	 * @param nd The node to add.
+	 */
+	public void addNode(Node nd) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+
+		this.nodes.add(nd);
+
+		Value v = nodeValuer.apply(nd);
+		this.nodeToValue.add(nd, v);
+		this.valueToNode.add(v, nd);
+	}
+
+	/**
+	 * Remove a node from the graph.
+	 * 
+	 * @param nd The node to remove
+	 */
+	public void removeNode(Node nd) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+		this.nodes.remove(nd);
+
+		Value v = nodeValuer.apply(nd);
+		this.nodeToValue.remove(nd);
+		this.valueToNode.remove(v, nd);
+	}
+
+	/**
+	 * Add an arc to the graph.
+	 * 
+	 * Note that badness can happen if you add a arc that refers to nodes not in the
+	 * graph.
+	 * 
+	 * @param nd1 The source node for the arc.
+	 * @param nd2 The destination node for the arc.
+	 * @param lab The label for the arc.
+	 */
+	public void addArc(Node nd1, Node nd2, Label lab) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+		arcMap.put(Pair.pair(nd1, nd2), lab);
+	}
+
+	/**
+	 * Remove an arc from the graph.
+	 * 
+	 * @param nd1 The source node for the arc.
+	 * @param nd2 The destination node for the arc.
+	 * @param lab The label for the arc.
+	 */
+	public void removeArc(Node nd1, Node nd2, Label lab) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+		arcMap.remove(Pair.pair(nd1, nd2), lab);
+	}
+
+	/**
+	 * Check if this graph is partitioned by the given graphs.
+	 * 
+	 * <ol>
+	 * <li>Every node in nodes is contained in exactly one partition</li>
+	 * <li>For every node in nodes, the value the partition assigns it is equal to
+	 * the value from nodeValuer</li>
+	 * <li>Every arc in a partition is also in arcMap</li>
+	 * </ol>
+	 * 
+	 * @param partitions The graphs to check partitioning for.
+	 * 
+	 * @return Whether this graph is partitioned by the given nodes.
+	 */
+	public boolean partitionedBy(@SuppressWarnings("unchecked") ASGraph<Node, Value, Label>... partitions) {
+		// TODO: Implement me
+		return false;
+	}
+
+	/**
+	 * Create a graph representing a given string
+	 * 
+	 * Note that because of the way the value function is implemented, modifying the
+	 * graph will not work well.
+	 * 
+	 * @param strang The string to represent.
+	 * 
+	 * @return The graph representing the string.
+	 */
+	public static ASGraph<Integer, Character, Unit> fromString(String strang) {
+		ASGraph<Integer, Character, Unit> ret = new ASGraph<>(strang::charAt);
+
+		for (int i = 0; i < strang.length(); i++) {
+			ret.addNode(i);
+			if (i != 0)
+				ret.addArc(i - 1, i, Unit.UNIT);
+		}
+
+		return ret;
+	}
+
+	@Override
+	public boolean freeze() {
+		frozen = true;
+		return true;
+	}
+
+	@Override
+	public boolean thaw() {
+		if (deepFrozen)
+			return false;
+
+		return false;
+	}
+
+	@Override
+	public boolean deepFreeze() {
+		deepFrozen = true;
+		frozen = true;
+		return true;
+	}
+
+	@Override
+	public boolean isFrozen() {
+		return frozen;
+	}
+}
diff --git a/base/src/main/java/bjc/utils/graph/ASGraphGrammar.java b/base/src/main/java/bjc/utils/graph/ASGraphGrammar.java
new file mode 100644
index 0000000..847107d
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/ASGraphGrammar.java
@@ -0,0 +1,30 @@
+package bjc.utils.graph;
+
+import java.util.Set;
+
+import bjc.data.Either;
+
+// See https://web.archive.org/web/20190414072011/https://core.ac.uk/download/pdf/82129679.pdf
+public class ASGraphGrammar<NonTerminal, Terminal, Label> {
+	public class Rule<Node> {
+		private ASGraph<Node, NonTerminal, ?> starting;
+		
+		// Must contain at least one node
+		private ASGraph<Node, Either<NonTerminal, Terminal>, Label> production;
+		
+		// Start node and end node must be in production
+		private Either<NonTerminal, Terminal> startNode;
+		private Either<NonTerminal, Terminal> endNode;
+		
+		public void derive(ASGraph<Node, Either<NonTerminal, Terminal>, Label> graph) {
+			// The derivation of H from G according to the rule A -> K(I/O) consists simply of replacing
+			// a node N' in G whose value is A by the graph K. Arcs leading into N' are replaced by
+			// arcs leading to I, arcs exiting from B' are replaced by arcs exiting from O, and any
+			// loop arcs on N' are replaced by arcs from O to I. 
+
+		}
+	}
+
+	// int is perhaps not the best node type, but it works
+	private Set<Rule<Integer>> rules;
+}
diff --git a/base/src/main/java/bjc/utils/graph/AlgGraph.java b/base/src/main/java/bjc/utils/graph/AlgGraph.java
new file mode 100644
index 0000000..7c9d38d
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/AlgGraph.java
@@ -0,0 +1,88 @@
+package bjc.utils.graph;
+
+import bjc.functypes.Container;
+
+/**
+ * A directed algebraic graph
+ * 
+ * (ref. Algebraic Graphs with Class, Andrey Mokhov}
+ * 
+ * @author bjcul
+ *
+ * @param <Vertex> The type of the vertexes
+ * @param <PGraph> Containing type parameter
+ */
+public interface AlgGraph<Vertex, PGraph extends AlgGraph<?, PGraph>> extends Container<Vertex, AlgGraph<?, PGraph>> {
+	/**
+	 * Create a empty algebraic graph.
+	 * 
+	 * @param <B> The type of the vertices
+	 * 
+	 * @return A new empty graph.
+	 */
+	<B> AlgGraph<B, PGraph> empty();
+	
+	/**
+	 * Create a algebraic graph with a single vertex
+	 * 
+	 * @param val The value for the vertex
+	 * 
+	 * @return A new graph with the given vertex
+	 */
+	<B> AlgGraph<B, PGraph> vertex(B val);
+	
+	/**
+	 * Overlay a graph onto this one, adding its vertices and edges.
+	 * 
+	 * @param other The graph to overlay
+	 */
+	void overlay(AlgGraph<Vertex, PGraph> other);
+
+	/**
+	 * Connect a graph to this one, adding its vertices and edges; as well as
+	 * establishing an edge from each node in this graph, to each node in the other
+	 * graph.
+	 * 
+	 * @param other The graph to connect
+	 */
+	void connect(AlgGraph<Vertex, PGraph> other);
+	
+	/**
+	 * Overlay two graphs into a new graph.
+	 * 
+	 * @param <Vertex> The type of the vertices.
+	 * 
+	 * @param left     The graph to overlay onto
+	 * @param right    The graph being overlaid
+	 * 
+	 * @return The overlaid graph.
+	 */
+	public static <Vertex, G extends AlgGraph<Vertex, G>> G overlay(G left, G right) {
+		@SuppressWarnings("unchecked")
+		// We know this cast is good, java just can't tell
+		G result = (G) left.empty();
+		result.overlay(left);
+		result.overlay(right);
+
+		return result;
+	}
+
+	/**
+	 * Connect two graphs into a new graph.
+	 * 
+	 * @param <Vertex> The type of the vertices.
+	 * 
+	 * @param left     The graph to connect to
+	 * @param right    The graph being connected
+	 * 
+	 * @return The connected graph.
+	 */
+	public static <Vertex, G extends AlgGraph<Vertex, G>> G connect(G left, G right) {
+		@SuppressWarnings("unchecked")
+		// We know this cast is good, java just can't tell
+		G result = (G) left.empty();
+		result.overlay(left);
+		result.connect(right);
+		return result;
+	}
+}
+\ No newline at end of file
diff --git a/base/src/main/java/bjc/utils/graph/SimpleAlgGraph.java b/base/src/main/java/bjc/utils/graph/SimpleAlgGraph.java
new file mode 100644
index 0000000..2c7ba08
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/SimpleAlgGraph.java
@@ -0,0 +1,83 @@
+package bjc.utils.graph;
+
+import java.util.*;
+
+/**
+ * A basic implementation of a directed algebraic graph.
+ * 
+ * @author bjcul
+ *
+ * @param <Vertex> The type of the vertices
+ */
+public class SimpleAlgGraph<Vertex> implements AlgGraph<Vertex, SimpleAlgGraph<?>> {
+	// TODO: consider if some function for labeling edges would make sense
+	private Set<Vertex> vertices;
+	private Map<Vertex, Vertex> edges;
+
+	/**
+	 * Create a new empty graph.
+	 */
+	public SimpleAlgGraph() {
+		vertices = new HashSet<>();
+		edges = new HashMap<>();
+	}
+
+	/**
+	 * Create a new graph with the given vertices, but no edges.
+	 * 
+	 * @param vertexes The vertices for the graph.
+	 */
+	@SafeVarargs
+	public SimpleAlgGraph(Vertex... vertexes) {
+		this();
+
+		for (Vertex vertex : vertexes)
+			vertices.add(vertex);
+	}
+
+	@Override
+	public <B> SimpleAlgGraph<B> empty() {
+		return new SimpleAlgGraph<>();
+	}
+	
+	@Override
+	public <B> SimpleAlgGraph<B> vertex(B val) {
+		return new SimpleAlgGraph<>();
+	}
+	
+	/**
+	 * Overlay a graph onto this one, adding its vertices and edges.
+	 * 
+	 * @param other The graph to overlay
+	 */
+	@Override
+	public void overlay(AlgGraph<Vertex, SimpleAlgGraph<?>> other) {
+		SimpleAlgGraph<Vertex> graph = (SimpleAlgGraph<Vertex>) other;
+		
+		vertices.addAll(graph.vertices);
+		edges.putAll(graph.edges);
+	}
+
+	/**
+	 * Connect a graph to this one, adding its vertices and edges; as well as
+	 * establishing an edge from each node in this graph, to each node in the other
+	 * graph.
+	 * 
+	 * @param other The graph to connect
+	 */
+	@Override
+	public void connect(AlgGraph<Vertex, SimpleAlgGraph<?>> other) {
+		SimpleAlgGraph<Vertex> graph = (SimpleAlgGraph<Vertex>) other;
+	
+		// note: this could be inefficent for large graphs
+		for (Vertex left : vertices) {
+			for (Vertex right : graph.vertices) {
+				edges.put(left, right);
+			}
+		}
+
+		overlay(other);
+	}
+
+
+}
+\ No newline at end of file