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

// SPDX-FileCopyrightText: 2025 <Ian Valentin Christensen stud-ianc@ruc.dk>
// 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.HashMap;
import java.util.Map;
import java.util.List;
import java.util.Random;
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 extends Storage {

    /// amount of iterations in demo
    private static final int DEMO_ITERATIONS = 1000000;

    /// path to source file for graph
    private String path = "combi.txt";

    /// data about combinations as a Graph
    private AbstractGraph g;

    /// Default constructor
    // to silence javadoc
    private Graph() {}

    /// constructor with custom file source
    ///
    /// @param path  path to source file for graph
    private Graph(String path) {
        this.path = path;
    }

    /// JVM entry point
    ///
    /// @param args  command-line arguments
    public static void main(final String[] args) {
        Graph g;

        // first argument, if provided, is the data file path;
        // else use upstream named file in current directory.
        g = (args.length > 0)
            ? new Graph(args[0])
            : new Graph();

        g.initialize();
        g.demo();
    }

    /// load graph from file
    void initialize() {

        // 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
        g = new MatrixGraph(_vertice_count);
        GraphAlgorithms.readGraph(g, path);
    }

    /// 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.
    ///
    /// @throws   IllegalArgumentException
    /// https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html
    public void assertConnected() {

        // 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
    ///
    /// @return   list of disjoint sets
    public ArrayList<Set<Vertex>> disjoint() {

        // get all subject modules
        //
        // TODO: optionally seed this, to enable ranking control
        List<Vertex> modules = new ArrayList<>(g.vertices());
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);
        System.out.println(
            "Seed used for shuffling modules: " + seed);
        Collections.shuffle(modules, random);

        return disjoint(modules);
    }

    /// groups of disjoint choices seeded by priority list of choices
    ///
    /// @param vip  Ordered list of subject modules to prioritize
    /// @return     List of sets of disjoint choices
    public ArrayList<Set<Vertex>> disjoint(final 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
            Set<Vertex> isolated = new HashSet<>();
            isolated.add(current);
            for (Vertex compared: vip) {

                // skip if already done
                if (compared.equals(current)
                    || done.contains(compared)) {
                    continue;
                }

                if (isolated.stream().allMatch(u ->
                    g.getWeight(u,compared) == null)
                ) {
                    isolated.add(compared);
                }
            }

            // 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
    /// @return      groups of disjoint choices as a graph
    private AbstractGraph moduleGroups(
        final ArrayList<Set<Vertex>> sets
    ) {
        AbstractGraph h = new AdjListGraph();
        Map<Set<Vertex>, String> groupLabel = new HashMap<>();
        for (Set<Vertex> groupSet : sets) {

            // stringify each group of module selections
            String name = groupSet.stream()
                .map(Vertex::toString)

                // avoid differently sorted duplicates
                .sorted()

                // formatting of groups as vertices
                .collect(Collectors.joining(
                    ", ", "{", "}"));

            // map group to name of group
            groupLabel.put(groupSet, name);
        }

        for (Set<Vertex> s: sets) {
            for (Set<Vertex> t: sets) {
                if (t == s) {
                    continue;
                }

                // process each pair only once
                if (s.hashCode() > t.hashCode()) {
                    continue;
                }

                // accumulate student count across set
                int sum = 0;
                for (Vertex v: s) {
                    // students with this choice
                    for (Vertex w: t) {
                        Integer weight =
                          g.getWeight(v, w);
                        if (weight != null) {
                            sum += weight;
                        }
                    }
                }
                // ensure h is treated as undirected
                h.insertEdge(
                    groupLabel.get(s),
                    groupLabel.get(t),
                    sum);
                h.insertEdge(
                    groupLabel.get(t),
                    groupLabel.get(s),
                    sum);
            }
        }
        return h;
    }

    /// loop through random combinations of sets of modules
    ///
    /// @param g  sets of disjoint choices as a graph
    /// @return   best path among many random ones
    private static long[] solveManyTimes(final AbstractGraph g) {
        // number higher than total students
        long[] bestSolution = solve(g);
        for (int i = 1; i < DEMO_ITERATIONS; i++) {
            long[] solution = solve(g);
            if (solution[0] < bestSolution[0]) {
                // store shortest path
                bestSolution = solution;
            }
        }
        return bestSolution;
    }

    /// find total weight of random path through disjoint choice sets
    ///
    /// @param g  sets of disjoint choices as a graph
    /// @return   total weight of random path and its seed as array
    private static long[] solve(final AbstractGraph g) {

        /// parameters for solution
        long[] solution = new long[] {0, 0};

        List<Vertex> path = new ArrayList<>(g.vertices());
        solution[1] = System.currentTimeMillis();
        Random random = new Random(solution[1]);

        // order of list contents becomes path order
        Collections.shuffle(path, random);

        for (int i = 0; i < path.size() - 1; i++) {
            solution[0] += g.getWeight(
                path.get(i), path.get(i + 1));
        }
        return solution;
    }

    /// Demo function to solve assignment
    private void demo() {

        System.out.println("\n\nGraph of choices constructed:");
        GraphAlgorithms.printGraph(g);

        // ensure the graph is connected
        assertConnected();
        System.out.println(
            "\n\nGraph is connected"
              + " (otherwise an exception was thrown)");

        // collect disjoint choice sets
        ArrayList<Set<Vertex>> s = disjoint();
        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);
        System.out.println(
            "\n\nGraph of disjoint choices constructed:");
        GraphAlgorithms.printGraph(h);

        // find path through disjoint choice graph
        long[] solution = solveManyTimes(h);
        System.out.printf(
            "\n\nSolution with disjoint choices found: "
            + "%d (disjoint shuffle seed: %d)%n",
            solution[0], solution[1]);
    }
}