c++代写-HW07|学霸联盟

c++代写-HW07

时间：2021-11-24

HW07 Technical Tips
Remastered
Yiran “Lawrence” Luo, Yezhou Yang
Setup
● Language of choice: C++ (highly recommended) or C
○ C++ has classes / is Object-oriented, while C is not
● Everything must work on general.asu.edu
○ A unified testing ground
○ Here is a tutorial https://fpsluozi.github.io/Linux-Setup/
○ g++ there supports up to C++17
○ Coding remotely saves a lot for compiler inconsistency
● How we are going to test it?
○ ./int < test_graph.txt > test_out.txt
○ diff test_out.txt test_answer.txt
○ We will run with hidden inputs in batches
Deliverables
● *The code files in Code/
○ *.cpp and *.h
○ Better not put implementations inside header files
○ Be well documented, comment what part does what job
● *The makefile in Code/
○ If your program fails to compile or execute, you would end up with a 0!
○ Use --std=C++17 to enforce C++ all the time (recommended)
● *The state description state.pdf in State/
○ Basically how you finish this project. Difficulties, references taken, design choices, etc.
● ZIP them, and submit
● DO NOT turn in your executable in the package (cuz they'd be
overwritten)
The Banned & The Allowed
NO. PRE-MADE. CONTAINER. LIBRARIES. This is the bottomline.
● No #include ; #include ; #include ; and likes
● Will result in heavy penalty (at least 80%) if you ever use them in your code.
Struct, class, array, pointer, linked list are allowed, and they are enough.
, , stdio, stdlib, string, char, int, float, double are all okay. You
can't escape them after all.
Graph Theory Recap Time
Graph - Cities and routes, abstracted
A Graph G is dictated by two sets:
● E (Edges) and
● V (Vertices/nodes)
If edges are one-way / directional, the graph is directed.
Otherwise, undirected.
If edges carry values / distances, the graph is weighted.
Otherwise, unweighted.
We use an adjacency matrix to describe the connectivity of
the graph. A[0][1] = 1 means node 0 and node 1 are
connected. A[0][2] = 0 means node 0 and node 2 are not.
What is this project all about?
Finding an Eulerian Circuit in a graph. AKA
Can you go over all the edges exactly once in a single stroke and be
back to the start? If not, at least how many edges have to go over twice?
The Seven Bridges of Konigsberg
For an Eulerian Circuit to exist in a graph
Degree: The # of edges a
node/vertex is connected to.
For an Eulerian Circuit to exist, the #
of odd-degree nodes must be 0.
A practical fix is to allow some
edges between odd-degree nodes
be used twice.
The revised circuit is actually no
longer an Eulerian Circuit but a
solution for Postman problem.
How to Code This Project -
A Personal Take
The intertwined four parts
Input graph G
P1: Find
odd-degree
nodes
P2: Find shortest
paths in between
odd-degree
nodes w/ FW
P3: Find best
additional edges in
between odd-degree
nodes w/ greedy
P4: Produce the
Eulerian Circuit of G
with the additional
edges
P0: Observing the input, and check its integrity
● First line: # of total nodes; # of total edges
● Following lines: end nodes of each edge
The easiest way is to convert this into an adjacency matrix (2D
array of int)
4 5
1 2
1 3
1 4
2 3
3 4
std::cin >> num_nodes >> num_edges;
int G[num_nodes+1][num_nodes+1];
zeroes(G); // Initialize the matrix with 0's
for (int i = 1; i<=num_edges; i++) {
std::cin >> x >> y;
G[x][y] = 1;
G[y][x] = 1;
}
0 0 0 0 0
0 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
P1: The odd-degree nodes O
Just scan each row, because the adjacency matrix of the undirected G is symmetric.
Print & store the indices with odd 1's into a new array O (whose size is always
smaller than # of total nodes)
0 0 0 0 0
0 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
G
O: {1, 3}
P2: The map S of shortest paths (of odd-degree nodes)
For convenience, just copy the original adjacency matrix and run Floyd-Warshall
on the whole G to produce S. Output those rows and columns dictated by O.
0 0 0 0 0
0 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
0 0 0 0 0
0 0 1 1 1
0 1 0 1 2
0 1 1 0 1
0 1 2 1 0
S
P2*: While doing FW
You could also record all actual sequence of each shortest path, and store them
somewhere.
Each path can be represented by an array, whose length never exceeds # of total
nodes.
0 0 0 0 0
0 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
P
Path #0: [1, 2], [1, 2, -1, -1], len=2
Path #1: [1, 3], [1, 3, -1, -1], len=2
Path #2: [1, 4], [1, 4, -1, -1], len=2
Path #3: [2, 3], [2, 3, -1, -1], len=2
Path #4: [2, 4], [2, 1, 4, -1], len=3
Path #5: [3, 4], [3, 4, -1, -1], len=2
P3: Perfect matchings of odd-degree nodes w/ greedy M
Sort all paths whose ends are with in O by length. And use greedy to pick the
non-intersected paths into M as the virtual edges.
(You don't even have to implement sorting. You can just scan through all possible
path lengths.)
O: {1, 3} +
P M
Path #0: [1, 3], [1, 3, -1, -1], len=2
Path #0: [1, 2], [1, 2, -1, -1], len=2
Path #1: [1, 3], [1, 3, -1, -1], len=2
Path #2: [1, 4], [1, 4, -1, -1], len=2
Path #3: [2, 3], [2, 3, -1, -1], len=2
Path #4: [2, 4], [2, 1, 4, -1], len=3
Path #5: [3, 4], [3, 4, -1, -1], len=2
P4: Find the Eulerian Circuit in G with M
● Technically Depth First Search.
● Advised to create a copy of the adjacency matrix G first.
● To remove an edge whose end nodes are x and y, simply do
○ G_copy[x][y] = 0; G_copy[y][x] = 0;
● Use the edges in G first, then consider the virtual edges in M.
● The stack shall be implemented as a custom struct/class
○ With an array of Edges and an integer to indicate the stacks size and the header position.
○ The size of the stack shall never exceed # of total edges
● Please refer to the instructions for the actual steps
The utility classes/structs/functions needed (as ref.)
A few you could think of:
● Struct of Edge (int as start, int as end)
● Struct of Path (an Edge, an array of int as Sequence, an int as Length)
● Struct of Stack (an array of Edge as Storage, an int as Header/Size)
● Function to zero a 2D array of int
● Function to load a graph from iostream
● Function to create a copy of a 2D array
● Function to implement Floyd-Warshall upon a 2D array
● … Or up to your design
The modularized code (an example)
● main.cpp:
○ Just a main(), but include all custom .h
○ Load graph from file; Run P1; Run P2; Run P3; Run P4;
● util.cpp, util.h:
○ Custom structs/classes;
○ Functions such as copy 2D array, load graph file into an 2D array, etc.
● p1.cpp, p1.h, p2.cpp, p2.h, ....:
○ Tackle each part.
● Makefile: g++ and compile everything together
Marginal cases and error handling
What if the input has errors?
What if the graph has no odd-degree nodes to start with?
What if ...
Question Time
Our Discord is your friend too!
And remember, no pre-made containers