From e54d71230df7f53bb1fa71e356a6c7dcca958b00 Mon Sep 17 00:00:00 2001 From: Jonas Smedegaard Date: Mon, 28 Apr 2025 23:23:58 +0200 Subject: rename class Combi -> Graph --- Makefile | 2 +- .../dk/biks/bachelorizer/Combi.java | 250 --------------------- .../dk/biks/bachelorizer/Graph.java | 250 +++++++++++++++++++++ 3 files changed, 251 insertions(+), 251 deletions(-) delete mode 100644 src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java create mode 100644 src/dk.biks.bachelorizer/dk/biks/bachelorizer/Graph.java diff --git a/Makefile b/Makefile index 17d5676..e29aeb4 100644 --- a/Makefile +++ b/Makefile @@ -13,7 +13,7 @@ JAVA_EXTRACLASSES_portfolio3 = AbstractGraph AdjListGraph AdjMapGraph \ Edge EdgeGraph GraphAlgorithms Graph Graphs MatrixGraph Vertex JAVA_MODULEPATHS_bachelorizer = /usr/share/openjfx/lib JAVA_ROOT_bachelorizer = src/dk.biks.bachelorizer -JAVA_MAINCLASSES_bachelorizer = Main Combi Window +JAVA_MAINCLASSES_bachelorizer = Main Graph Window JAVA_EXTRACLASSES_bachelorizer = Control GUI Person JAVA_MODULES_bachelorizer = $(addprefix javafx.,base controls graphics) diff --git a/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java b/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java deleted file mode 100644 index 6cde168..0000000 --- a/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java +++ /dev/null @@ -1,250 +0,0 @@ -// SPDX-FileCopyrightText: 2025 Jonas Smedegaard -// 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.Graph; -import com.example.portfolio3.GraphAlgorithms; -import com.example.portfolio3.MatrixGraph; -import com.example.portfolio3.Vertex; - -/// Combi - static sample dataset of course combinations -/// -/// Slurps and parses data from upstream-provided comma-separated file. -/// -/// @version 0.0.1 -/// @see -public final class Combi { - - /// data about combinations as a Graph - private Graph g; - - /// Default constructor - /// - /// @param path path to data file - private Combi(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) - Graph _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 - Graph 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> s = disjoint(g); - System.out.printf( - "\n\n%d disjoint choice sets collected:\n", - s.size()); - for(Set 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 - Graph 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"; - - Combi combi = new Combi(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(Graph g) { - - // collect all vertices in the graph - Collection c = g.vertices(); - - // pick a random vertice in the graph - Vertex v = g.vertices().iterator().next(); - - // collect the set of visitable vertices - Set 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> disjoint(Graph g) { - - // get all subject modules - // - // TODO: optionally seed this, to enable ranking control - List 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> disjoint(Graph g, List vip) { - ArrayList> sets = new ArrayList<>(); - - // track done subject modules as extendable set - // - // HashList used for efficient addition and lookup - Set done = new HashSet<>(); - - // convert module list to a set - // - // defined once outside loop as a slight optimization - Set 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 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 Graph moduleGroups(ArrayList> sets, Graph g) { - Graph h = new AdjListGraph(); - for (Set s: sets) { - for (Set 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(Graph 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(Graph g, Vertex v) { - return GraphAlgorithms.pathLength( - GraphAlgorithms.dijkstra(g, v)); - } -} 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 +// 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 +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> s = disjoint(g); + System.out.printf( + "\n\n%d disjoint choice sets collected:\n", + s.size()); + for(Set 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 c = g.vertices(); + + // pick a random vertice in the graph + Vertex v = g.vertices().iterator().next(); + + // collect the set of visitable vertices + Set 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> disjoint(AbstractGraph g) { + + // get all subject modules + // + // TODO: optionally seed this, to enable ranking control + List 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> disjoint(AbstractGraph g, List vip) { + ArrayList> sets = new ArrayList<>(); + + // track done subject modules as extendable set + // + // HashList used for efficient addition and lookup + Set done = new HashSet<>(); + + // convert module list to a set + // + // defined once outside loop as a slight optimization + Set 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 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> sets, AbstractGraph g) { + AbstractGraph h = new AdjListGraph(); + for (Set s: sets) { + for (Set 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)); + } +} -- cgit v1.2.3