1 files changed, 68 insertions, 0 deletions
diff --git a/portfolio3.md b/portfolio3.md
index e69de29..6ea4e97 100644
--- a/portfolio3.md
+++ b/portfolio3.md
@@ -0,0 +1,68 @@
+# Graph algorithms
+
+To read the graph supplied with the assignment,
+we simply used the readGraph() function also supplied
+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 a new attempt each time.