Description

Lecturer: Prof. Jaesik Park
Teaching Assistants: ByeongHoon So, Hyunmin Lee, Junha Lee

1. Graph Traversal (4 pts)

b. Input & output
Input: Pairs of node labels that indicate edges.
– (‘1’, ‘2’ ): an edge between node 1 and node 2.
Output:
– Result of DFS traverse separated with a white space
– Multiple traverses separated with a newline, in the ascending order.

c. Example Input & Output
Input Output
[(‘0′,’2’), (‘0′,’1’), (‘0′,’3’), (‘1′,’2’),
(‘1′,’3’), (‘1′,’4’), (‘1′,’5’), (‘2′,’5’), (‘2′,’4’)] 0 1 2 4 5 3
[(‘0′,’2’), (‘0′,’1’), (‘0′,’3’), (‘1′,’2’),
(‘1′,’3’), (‘1′,’4’), (‘1′,’5’), (‘2′,’5’),
(‘2′,’4’), (‘8′,’9’)] 0 1 2 4 5 3
8 9
[(‘0′,’1’), (‘0′,’2’), (‘0′,’3’), (‘0′,’4’),
(‘1′,’5’), (‘2′,’5’), (‘3′,’6’), (‘4′,’6’),
(‘8′,’7’), (‘9′,’10’), (’10’,’11’)] 0 1 5 2 3 6 4
7 8
9 10 11

d. Example execution
>> ./pa6.exe 1 “[(‘0′,’2’), (‘0′,’1’), (‘0′,’3’), (‘1′,’2’),
(‘1′,’3’), (‘1′,’4’), (‘1′,’5’), (‘2′,’5’), (‘2′,’4’)]”
[Task 1]
0 1 2 4 5 3

2. Topological Sort (4 pts)

a. Implement a function that performs a topological sort using the given directed graph. If there exists more than one result, print the topological sort that comes first in the ascending order. To take an example below, acceptable topological sorts are ‘0 1 2 3 5 4’, ‘0 2 1 5 4 3’, ‘0 2 3 1 5 4’, etc. Among these, the desirable output is ‘0 1 2 3 5 4’ . Also, print ‘error’ if the topological sort could not be performed. You can modify graph.cpp and graph.h files for this problem.

b. Input & output
Input: Pairs of node labels that indicate edges.
– (‘1’, ‘2’ ): an edge from node 1 to node 2.
– If the input edge already exists in the graph, ignore the input.
Output:
– Result of topological sort or ‘error’ message

c. Example Input & Output
Input Output
[(‘0′,’1’), (‘0′,’2’), (‘1,’5’), (‘5′,’4’),
(‘2′,’4’), (‘2,’3’)] 0 1 2 3 5 4
[(‘0′,’1’), (‘0′,’3’), (‘1′,’2’), (‘2,’4’),
(‘3′,’4’), (‘4′,’5’)] 0 1 2 3 4 5
[(‘1′,’2’), (‘2′,’3’), (‘3,’1’)] error

d. Example execution
>> ./pa6.exe 2 “[(‘0′,’1’), (‘0′,’2’), (‘1,’5’), (‘5′,’4’),
(‘2′,’4’), (‘2,’3’)]”
[Task 2]
0 1 2 3 5 4

3. Single Source Shortest Path (4 pts)

a. Implement a function that finds the shortest path from the source node to the destination node in the given graph. We assume that the given graph is a directed, weighted, and weakly-connected graph. All weights of edges are positive (i.e. larger than 0). This function should return the sequence of node labels along the path and also the length (sum of the weights of the edges) of the path. If there exists multiple shortest path, print out all of them with ascending lexicographic order. (e.g. if both of A->B->E and A->C->E are shortest paths with cost 5, prints out ‘A B E 5’ then ‘A C E 5’ ) . If the path from the source node to the destination node doesn’t exist, return ‘error’ . You can modify the graph.cpp and graph.h files for this problem.

b. Input & output
Input: A sequence of commands
– (‘A-B’, integer): an edge from node A to node B with a weight value {integer }.
– (‘A’, ‘B’ ): a pair of node labels that indicates the source and the destination node. The first element indicates the source node and the second one indicates the destination node.
Output:
– A sequence of the node labels of the shortest path(s) followed by length of the path. If there exists multiple paths, you should print out all of them sorted by ascending lexicographic order, separated with newline( ).
– error if the shortest path could not be determined

c. Example Input & Output
Input Output
[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2),
(‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,’E’)] A C E 18
[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2),
(‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,’D’)] A C B D 10
[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2),
(‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘D’,’A’)] error

d. Example execution
>> ./pa6.exe 3 “[(‘A-B’,10), (‘A-C’,3), (‘B-D’,5), (‘C-B’,2),
(‘C-E’,15), (‘A-D’,20), (‘D-E’,11), (‘A’,’E’)]” [Task 3]
A C E 18

4. All Pairs Shortest Path of Graph (4 pts)

a. Implement a function that finds the shortest paths of all pairs of nodes. Unlike problem 3, there will be an edge(s) with negative weight value(s). There will be no negative cycle in the given graph. This function should return the distances of all paths in the given graph like the above image. You can modify the graph.cpp and graph.h files for this problem.

b. Input & Output
Input: A sequence of commands
– (‘A-B’, integer): an edge from node A to node B with weight value {integer }. Output:
– A distance matrix in a string format. The nodes in the row and column of the matrix are sorted in lexicographic order. If the source and the destination node are the same, the distance should be 0. If the path doesn’t exist, the distance is INF .

c. Example Input & Output
Input Output
[(‘A-B’,4),(‘B-C’,9),(‘B-D’,1),
(‘C-D’,10),(‘D-C’,8),(‘D-A’,-2)] 0 4 13 5
-1 0 9 1
8 12 0 10
-2 2 8 0
[(‘A-B’,4),(‘A-F’,3),(‘B-F’,6),
(‘B-C’,9),(‘F-E’,-2),(‘E-F’,5),
(‘C-E’,-3),(‘E-C’,8),(‘E-D’,6)] 0 4 9 7 1 3
INF 0 9 10 4 6
INF INF 0 3 -3 2
INF INF INF 0 INF INF
INF INF 8 6 0 5
INF INF 6 4 -2 0
[(‘A-B’,4),(‘B-C’,9),(‘C-E’,-2),
(‘E-C’,8),(‘B-H’,1),(‘A-H’,4),
(‘H-C’,3),(‘B-F’,6),(‘A-G’,7),
(‘G-B’,-4),(‘B-G’,8),(‘G-F’,7),
(‘F-E’,6),(‘E-F’,5),(‘E-D’,6)] 0 3 7 11 5 9 7 4
INF 0 4 8 2 6 8 1
INF INF 0 4 -2 3 INF INF
INF INF INF 0 INF INF INF INF
INF INF 8 6 0 5 INF INF
INF INF 14 12 6 0 INF INF
INF -4 0 4 -2 2 0 -3
INF INF 3 7 1 6 INF 0

d. Example execution
>> ./pa6.exe 4 “[(‘A-B’,4), (‘A-F’,3), (‘B-F’,6), (‘B-C’,9),
(‘F-E’,-2), (‘E-F’,5), (‘C-E’,-3), (‘E-C’,8), (‘E-D’,6)]”
[Task 4]
0 4 9 7 1 3
INF 0 9 10 4 6
INF INF 0 3 -3 2
INF INF INF 0 INF INF
INF INF 8 6 0 5
INF INF 6 4 -2 0

5. Prim’s Algorithm (4 pts)

a. Implement a function that finds the Minimum-cost Spanning Tree (MST) of the given weighted undirected graph using Prim’s algorithm . Given a start node, this function starts with the single-vertex tree of the given node. Then, the function prints the added edge and the weight of the edge each time the tree grows. When printing an edge, you first have to print the label of the node that already exists in the tree, then print the label of the node that was recently inserted into the tree. If there are multiple edges with the same weight, this function checks the label of the added node ( i.e. the node which is not included in the tree) and selects the node with the first label in lexicographical order . Finally, the function returns the cost of the MST (i.e. the sum of edge weights). You can assume that the given graph is a connected graph. You can modify graph.cpp and graph.h files for this problem.

b. Input & Output
Input: A sequence of commands
– (‘A-B’, integer): an edge between node A and node B with weight value {integer }.
– (‘MST’, ‘A’ ): find MST using the Prim’s algorithm which starts with node A.
Output:
– For each time the tree grows, print the labels of the nodes indicating the added edges and the weight of the edge as a string separated with a white space.
– Print the cost of MST.

c. Example Input & Output
Input Output
[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4),
(‘B-D’, 1), (‘C-D’, 2), (‘D-E’, 5),
(‘MST’, ‘A’)] A C 1
C D 2
D B 1
D E 5
9
[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4),
(‘B-D’, 1), (‘C-D’, 2), (‘D-E’, 5),
(‘MST’, ‘E’)] E D 5
D B 1
D C 2
C A 1
9
[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 1),
(‘B-D’, 4), (‘C-D’, 2), (‘D-E’, 5),
(‘MST’, ‘E’)] E D 5
D C 2
C A 1
C B 1
9

d. Example execution
>> ./pa6.exe 5 “[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4), (‘B-D’,
1), (‘C-D’, 2), (‘D-E’, 5), (‘MST’, ‘A’)]” [Task 5] A C 1
C D 2
D B 1
D E 5
9

6. Kruskal’s Algorithm (5 pts)

a. Implement a function that finds the Minimum-cost Spanning Tree (MST) of the given weighted undirected graph using Kruskal’s algorithm . The function prints the added edge and the weight of the edge each time the tree grows. When printing an edge, you have to print the label in lexicographical order. If there are multiple edges with the same weight, this function also selects the edge in lexicographical order. That means it compares the first node of edges, and if the first node is the same, it compares the second node of edges. The function returns the cost of the MST (i.e. the sum of edge weights). You can assume that the given graph is a connected graph. You can modify graph.cpp and graph.h files for this problem.

b. Input & Output
Input: A sequence of commands
– (‘A-B’, integer): an edge between node A and node B with weight value {integer }.
– (‘MST’, NULL ): find MST using Kruskal’s algorithm.
Output:
– For each time the tree grows, print the labels of the nodes indicating the added edges in lexicographical order and the weight of the edge as a string separated with a white space.
– Print the cost of MST.

c. Example Input & Output
Input Output
[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4),
(‘B-D’, 1), (‘C-D’, 2), (‘D-E’, 5),
(‘MST’, NULL)] A C 1
B D 1
C D 2
D E 5
9
[(‘D-B’, 1), (‘D-C’, 2), (‘E-D’, 5),
(‘B-A’, 3), (‘C-A’, 1), (‘C-B’, 4),
(‘MST’, NULL)] A C 1
B D 1
C D 2
D E 5
9
[(‘A-B’, 1), (‘B-C’, 1), (‘C-D’, 1),
(‘D-A’, 1), (‘A-C’, 1), (‘B-D’, 1),
(‘MST’, NULL)] A B 1
A C 1
A D 1
3

d. Example execution
>> ./pa6.exe 6 “[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4), (‘B-D’,
1), (‘C-D’, 2), (‘D-E’, 5), (‘MST’, NULL)]” [Task 6] A C 1
B D 1
C D 2
D E 5
9

This is the last page of the programming assignments.
We hope you have enjoyed the course.

We do appreciate your participation to make this class better.

Warm wishes,

Jaesik Park ByeongHoon So Hyunmin Lee Junha Lee