path: root/src/dk.biks.bachelorizer/dk/biks/bachelorizer/Combi.java

// 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.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 <https://moodle.ruc.dk/mod/assign/view.php?id=523186>
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);

        // ensure the graph is connected
        assertConnected(g);

        nonOverlapping(g);

//      GraphAlgorithms.printGraph(g);
        GraphAlgorithms.printGraph(moduleGroups(nonOverlapping(g), g));

        System.out.println(
            solution(moduleGroups(nonOverlapping(g), g)));

        // 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<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");
        }
    }

    /// groups of disjoint choices
    ///
    /// @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 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>> 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)) {
                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);
        }

for(Set<Vertex> s: sets) {
System.out.println("set: "+s.size());
for (Vertex v: s) {
System.out.println("  "+v.toString());
}
}

        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<Set<Vertex>> sets, Graph g) {
        Graph 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  groups of non-overlapping selections 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 non-overlapping selections 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));
    }
}