Graph algorithms
To read the graph supplied with the assignment,
we simply used the readGraph() function supplied in @Rosendahl2025.16
and stored it as an adjacency list graph.
Since we will loop it many times for part 5,
we construct a matrix list graph based on the vertex count in the
adjacency list graph for efficiency.
We then printed it to confirm it works and is bidirectional.
To confirm the graph is connected,
we pick a random vertex and visit the rest of the graph
with visitDepthFirst() as supplied.
The function assertConnected() finishes with a check that
the amount of visited vertices is equal to the size of the graph.
The time complexity of the visit is O(n^2)
since the function recursively visits every out edge
of every vertex.
Grouping choices
To construct groups of subject module choices as described in
the assignment,
we get an ArrayList of sets of vertices from the disjoint() function.
The disjoint() function called with 1 argument takes any graph --
in our case the matrix list graph from earlier --
and creates a List of vertices based on it,
then shuffles it.
It then calls itself with 2 arguments,
processing the actual algorithm.
This list is then looped through,
on the outer layer continuing until it encounters a
vertex not processed before.
It runs through all vertices in the list again and compare them
to current until it finds a vertex with a weight of 0 between itself
and the compared vertex.
It adds the vertex "current", that is being compared,
to a set of isolated vertices,
then in the outer layer of the loop adds this set to the final list of sets,
and adds every vertex in the isolated set to a "done"
set so they are not processed again.
It formats the result nicely and prints it to the terminal.
These sets of vertices are then fed into the function "moduleGroups"
together with the original matrix list graph.
First, a HashMap is created for mapping each vertex to a label.
This is then done by looping through each set,
sorting the toString representations of each vertex in the set
to avoid differently sorted duplicates,
then formatting the names of these sets and putting them in the HashMap,
mapped to their respective set.
A simple loop then compares the each vertex to each vertex in another,
adding up the sum for the set.
Edges are inserted both ways for bidirectionality in an adjacency list,
and the list is returned.
Though first trying Dijkstra,
we switched to a random approach for part 5,
since the problem is a variant of the travelling salesman,
not a single-source shortest path.
The solution to this part was otherwise surprisingly simple,
we simply take the resulting graph "h",
pass it to goodSolution(), which loops over solution()
to find lower path costs.
The solution() function simply shuffles the list of vertices of the original h
and gets the weight between edges in the list incrementally.
It hits no vertex more than once,
and the shuffling makes it quite likely a new attempt each time.
