draft...

1 files changed, 95 insertions, 1 deletions

diff --git a/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java b/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java
index 78a1ee0..b27fe3c 100644
--- a/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java
+++ b/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java
@@ -3,8 +3,15 @@
 
 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.Graph;
@@ -51,7 +58,9 @@ public final class Combi {
 		// ensure the graph is connected
 		isConnected(g);
 
-		GraphAlgorithms.printGraph(g);
+		nonOverlapping(g);
+
+//		GraphAlgorithms.printGraph(g);
 
 		// release temporary variables for garbage collection
 		_g = null;
@@ -102,4 +111,89 @@ public final class Combi {
 				"graph is not connected");
 		}
 	}
+
+	/// groups of subject modules with no overlapping students
+	///
+	/// @param g  Graph to inspect
+	/// @return   list of non-overlapping sets
+	public static ArrayList<Set<Vertex>> nonOverlapping(Graph g) {
+
+		// get all subject modules
+		//
+		// TODO: optionally seed this, to enable ranking control
+		List<Vertex> modules = new ArrayList<>(g.vertices());
+		Collections.shuffle(modules);
+
+		return nonOverlapping(g, modules);
+	}
+
+	/// groups of subject modules with no overlapping students
+	///
+	/// @param g    Graph to inspect
+	/// @param vip  Ordered list of subject modules to prioritize
+	/// @return     list of non-overlapping sets
+	public static ArrayList<Set<Vertex>> nonOverlapping(Graph 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)) {
+System.out.println("skipped: "+current.toString());
+				continue;
+			}
+
+			// add set of current and any unconnected modules
+			Set<Vertex> isolated = all_set.stream().filter(x -> {
+				if (x == current)
+					return false;
+				Integer weight = g.getWeight(current, x);
+System.out.printf("weight from %s to %s: %d%n", current, x, weight);
+				return weight != null && weight > 0;
+			}).collect(Collectors.toSet());
+
+/*
+			// add set of current and any unconnected modules
+			Set<Vertex> isolated = all_set;
+			isolated.removeIf(x -> {
+				if (x == current)
+					return false;
+				Integer weight = g.getWeight(current, x);
+System.out.printf("weight from %s to %s: %d%n", current, x, weight);
+				return weight != null && weight > 0;
+			});
+*/
+
+			// add as set and omit from future iterations
+			sets.add(isolated);
+			done.addAll(isolated);
+System.out.println("isolated:");
+for (Vertex v: isolated) {
+System.out.println("\t"+v.toString());
+}
+
+//for (Vertex v: done) {
+//System.out.println("done: "+v.toString());
+//}
+		}
+
+for(Set<Vertex> s: sets) {
+System.out.println("set: "+s.size());
+for (Vertex v: s) {
+System.out.println("  "+v.toString());
+}
+}
+
+		return sets;
+	}
 }