HW7 First Impressions by Yiran “Lawrence” Luo Since HW7 is an unprecedented project with no golden solution at hand, I will be giving away some of my personal takes on how to approach this. I will be using very crass pseudocode wherever necessary. The observed The project involves 4 intertwined procedures around a graph. A graph is represented using an adjacency matrix or a set of adjacency lists. A graph G consists of two critical sets V and E. V means vertices/nodes, and E means edges. An edge always connects two vertices (while the vertices can be the same one) The input graph is unweighted, so we assume the length of all edges in E is 1. If a graph is weighted, then its edges may carry any real values. The ‘degree’ of a vertex is equal to the number of edges it connects to. E.g. The degree of Vertex_0 is 2 while the degree of Vertex_1 is 4. A ‘path’ is a sequence that connects multiple vertices via existing edges. E.g. Path 2-1-0 has a length of 2. The top-down design of the entire project Input: G(E, V) Part 1 – Finding odd-degree nodes O <- Part1( G(E, V) ) // O is a set of vertices print O Part 2 - Applying FW algorithm wrt O G' <- Part2( G(E, O) ) // E is the same E from the input G; // G' is an adjacency matrix of the shortest path lengths // between the vertices in O via edges in E. print G' Part 3 - Find the minimum perfect matchings from G' M <- Part3(G') // M is a collection of weighted edges print M Part 4 - Find the Euler Circuit in G along with the minimum perfect matching edges M C <- Part4(G (E ∪ M, V)) // C is the set of edges that are part of the Euler Circuit print C A modularized code design as reference These are my own personal designs in pseudocode and they are NOT complete source code. You should design your own however you see fit. main.cpp: int main() { E, V = load_edges_and_vertices(input_file) G = build_graph(E, V) O = Part1(G) G' = Part2( build_graph(G.E, O)) M = Part3(G') G_new = build_weighted_graph(G.E + M, G.V) C = Part4(G_new) } // the end graph.cpp & graph.h: struct Vertices { … }; struct Edges { … }; class Graph { … }; util.cpp & util.h: load_edges_and_vertices() build_graph() build_weighted_graph() … part1.cpp & part1.h Vertices Part1(Graph G); … // And likewise for part2 part3 and part4 Makefile: g++ -o int main.cpp graph.cpp util.cpp part1.cpp part2.cpp part3.cpp part4.cpp
