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