rename class Combi -> Graph

1 files changed, 250 insertions, 0 deletions

diff --git a/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Graph.java b/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Graph.java
new file mode 100644
index 0000000..ed38f1d
--- /dev/null
+++ b/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Graph.java
@@ -0,0 +1,250 @@
+// SPDX-FileCopyrightText: 2025 Jonas Smedegaard <dr@jones.dk>
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package dk.biks.bachelorizer;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import com.example.portfolio3.AdjListGraph;
+import com.example.portfolio3.AbstractGraph;
+import com.example.portfolio3.GraphAlgorithms;
+import com.example.portfolio3.MatrixGraph;
+import com.example.portfolio3.Vertex;
+
+/// Bachelorizer - database model
+///
+/// Slurps and parses data from upstream-provided comma-separated file.
+///
+/// @version 0.0.1
+/// @see <https://moodle.ruc.dk/mod/assign/view.php?id=523186>
+public final class Graph {
+
+	/// data about combinations as a Graph
+	private AbstractGraph g;
+
+	/// Default constructor
+	///
+	/// @param path  path to data file
+	private Graph(final String path) {
+
+		// read into temporary graph to resolve vertice count
+		//
+		// use Adjacency List Representation:
+		//  * cheap to bootstrap (done once)
+		//  * simple to count vertices (done once): O(1)
+		AbstractGraph _g = new AdjListGraph();
+		GraphAlgorithms.readGraph(_g, path);
+		Integer _vertice_count = _g.vertices().size();
+
+		// read into final graph
+		//
+		// use Adjacency Matrix Representation:
+		//  * expensive to bootstrap (done once)
+		//    * simple to add edges but needs vertice count
+		//  * simple to get edges (done repeatedly): O(1)
+		//
+		// TODO: avoid reading and parsing file twice
+		AbstractGraph g = new MatrixGraph(_vertice_count);
+		GraphAlgorithms.readGraph(g, path);
+
+		System.out.println("\n\nGraph of choices constructed:");
+		GraphAlgorithms.printGraph(g);
+
+		// ensure the graph is connected
+		assertConnected(g);
+		System.out.println(
+			"\n\nGraph is connected"
+			+" (otherwise an exception was thrown)");
+
+		// collect disjoint choice sets
+		ArrayList<Set<Vertex>> s = disjoint(g);
+		System.out.printf(
+			"\n\n%d disjoint choice sets collected:\n",
+			s.size());
+		for(Set<Vertex> verticeSet: s) {
+			System.out.print("set("+verticeSet.size()+"):");
+			for (Vertex v: GraphAlgorithms.sortVertex(verticeSet)) {
+				System.out.print(" "+v.toString());
+			}
+			System.out.println();
+		}
+
+		// construct graph of disjoint choices
+		AbstractGraph h = moduleGroups(s, g);
+		System.out.println(
+			"\n\nGraph of disjoint choices constructed:");
+		GraphAlgorithms.printGraph(h);
+
+		// find path through disjoint choice graph
+		System.out.println(
+			"\n\nSolution with disjoint choices found:");
+		System.out.println(
+			solution(h));
+
+		// release temporary variables for garbage collection
+		_g = null;
+		_vertice_count = null;
+	}
+
+	/// JVM entry point
+	///
+	/// @param args  command-line arguments
+	public static void main(final String[] args) {
+
+		// first argument, if provided, is the data file path;
+		// else use upstream named file in current directory.
+		String path = (args.length > 0)
+			? args[0]
+			: "combi.txt";
+
+		Graph combi = new Graph(path);
+	}
+
+	/// utility function to check that a graph is connected
+	///
+	/// If check fails, throw an unchecked exception,
+	/// since it occurs at runtime and is unrecoverable.
+	///
+	/// Time complexity of the operation is O(n²)
+	/// where n is the amount of vertices,
+	/// since visitDepthFirst() recurses out-edges of all vertices.
+	///
+	/// @param g  Graph to inspect
+	/// @throws IllegalArgumentException
+	/// https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html
+	public static void assertConnected(AbstractGraph g) {
+
+		// collect all vertices in the graph
+		Collection<Vertex> c = g.vertices();
+
+		// pick a random vertice in the graph
+		Vertex v = g.vertices().iterator().next();
+
+		// collect the set of visitable vertices
+		Set<Vertex> visited = GraphAlgorithms.visitDepthFirst(
+			g, v);
+
+		// throw exception if not all vertices were visited
+		if (visited.size() != c.size()) {
+			throw new IllegalArgumentException(
+				"graph is not connected");
+		}
+	}
+
+	/// sets of disjoint choices
+	///
+	/// @param g  Graph to inspect
+	/// @return   list of disjoint sets
+	public static ArrayList<Set<Vertex>> disjoint(AbstractGraph g) {
+
+		// get all subject modules
+		//
+		// TODO: optionally seed this, to enable ranking control
+		List<Vertex> modules = new ArrayList<>(g.vertices());
+		Collections.shuffle(modules);
+
+		return disjoint(g, modules);
+	}
+
+	/// groups of disjoint choices seeded by priority list of choices
+	///
+	/// @param g    Graph to inspect
+	/// @param vip  Ordered list of subject modules to prioritize
+	/// @return     List of sets of disjoint choices
+	public static ArrayList<Set<Vertex>> disjoint(AbstractGraph g, List<Vertex> vip) {
+		ArrayList<Set<Vertex>> sets = new ArrayList<>();
+
+		// track done subject modules as extendable set
+		//
+		// HashList used for efficient addition and lookup
+		Set<Vertex> done = new HashSet<>();
+
+		// convert module list to a set
+		//
+		// defined once outside loop as a slight optimization
+		Set<Vertex> all_set = new HashSet<>(vip);
+
+		// iterate over subject modules
+		for (Vertex current : vip) {
+
+			if (done.contains(current)) {
+				continue;
+			}
+
+			// add set of current and any unconnected modules
+			// TODO: try tighten to include current in loop
+			Set<Vertex> isolated = all_set.stream()
+				.filter(x ->
+			{
+				if (x == current)
+					return false;
+				Integer weight = g.getWeight(current, x);
+				return weight == null
+					&& !done.contains(x);
+			}).collect(Collectors.toSet());
+			isolated.add(current);
+
+			// add as set and omit from future iterations
+			sets.add(isolated);
+			done.addAll(isolated);
+		}
+
+		return sets;
+	}
+
+	/// sum of students' selections as a graph
+	///
+	/// @param sets  list of disjoint choices
+	/// @param g     choices as weights in graph
+	/// @return      groups of disjoint choices as a graph
+	public static AbstractGraph moduleGroups(ArrayList<Set<Vertex>> sets, AbstractGraph g) {
+		AbstractGraph h = new AdjListGraph();
+		for (Set<Vertex> s: sets) {
+			for (Set<Vertex> t: sets) {
+				if (t == s) continue;
+				int sum = 0;
+				for (Vertex v: s) {
+					// get num of students with this combination of modules.
+					for (Vertex w: t) {
+						Integer weight = g.getWeight(v, w);
+						if (weight != null) {
+							sum += weight;
+						}
+					}
+				}
+				h.insertEdge(s.toString(), t.toString(), sum);
+			}
+		}
+		return h;
+	}
+
+	/// groups of disjoint module choices
+	///
+	/// @param g  sets of disjoint choices as a graph
+	/// @return   amount of students in consecutive slots
+	public static int solution(AbstractGraph g) {
+
+		// pick a random vertice in the graph
+		Vertex v = g.vertices().iterator().next();
+
+		return solution(g, v);
+	}
+
+	/// groups of disjoint module choices seeded by start vertex
+	///
+	/// @param g  groups of disjoint choices as a graph
+	/// @param v  seed vertex within graph
+	/// @return   amount of students in consecutive slots
+	public static int solution(AbstractGraph g, Vertex v) {
+		return GraphAlgorithms.pathLength(
+			GraphAlgorithms.dijkstra(g, v));
+	}
+}