diff options
| -rw-r--r-- | portfolio3.md | 68 |
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. |