Description
Problem: Cycle Breaking
Cycle breaking serves as a fundamental technique for many applications, e.g., resolving resource deadlock or
simplifying a problem instance. In graph theory, a cycle is a path where the first and the last vertices are
the same. A graph without cycles is called an acyclic graph. Given a graph G = (V, E) which may contain
cycles, we want to remove some edges to make the graph acyclic with minimum total cost (weight). Such a
problem is so-called the cycle breaking or cycle removal problem. For example, Figure 1 (a) is a weighted
undirected graph Gu with cycles. We can remove e01 and e34 to make it acyclic with total cost = 3 + 5 = 8.
For the weighted directed graph Gd in Figure 1 (b), there is only one cycle C143. So we only need to remove
e43 with total cost = 5. Cycle breaking for an (unweighted or weighted) undirected graph can be solved in
polynomial time. The problem for a weighted directed graph, however, is also known as a minimum feedback
arc set problem, which is a NP-hard problem. In this assignment, test cases contain three types of graph
instances: 1) unweighted undirected graph, 2) weighted undirected graph, and 3) weighted directed graph.
(a) weighted undirected graph (b) weighted directed graph
Figure 1: Graph with cycles.
Input
The input will be a graph with only one connected component which may contain cycles or not. The first line
of the input is a character “u” or a character “d”, which indicates the input graph is an undirected graph or
a directed graph, respectively. The second line is an integer n, denoting the total number of vertices. The
indices of these nodes will be continuous from 0 to n − 1. The third line is an integer m, denoting the total
number of edges. In the following m lines, each contains three integers i, j and w, denoting an edge from
vertex i to vertex j with weight w, −100 ≤ w ≤ 100. For test cases of unweighted undirected graph, the
weight of all edges will equal to 1. Please note that the order of vertex i and j implies the direction of the
edge in a directed graph, while it does not matter in an undirected graph. A single “0” (zero) in the input
line signifies the end of input. For undirected graph instances, 1 ≤ n ≤ 10000 and 1 ≤ m ≤ 50000000. For
directed graph instances, 1 ≤ n ≤ 5000 and 1 ≤ m ≤ 10000.
Output
The output file should report the total weight of removed edges to make the input graph acyclic, followed
by a list of these removed edges and their weights. The graph must remain connected (one connected
component) after the edges are removed. The output edges can be in arbitrary order. If the input graph
has no cycles, you should output a line with single “0” (zero) in your output file.
Here are some input/output examples:
Sample Input 1 Sample Output 1 Sample Input 2 Sample Output 2
u 8 d 5
8 0 1 3 8 4 3 5
9 3 4 5 9
0 1 3 0 1 3
0 2 5 0 2 5
1 3 10 1 4 8
1 4 8 2 5 9
2 5 9 3 1 10
3 4 5 3 5 11
3 5 11 4 3 5
3 6 12 4 7 6
4 7 6 6 3 12
0 0
Command-line Parameter:
The executable binary must be named as ‘cb” and use the following command format.
./cb
For example, if you would like to run your binary for the input file 1.in and generate a solution named
1.out, the command is as follows:
./cb 1.in 1.out
Required Files:
You need to create a directory named pa3/ (e.g. b06901000 pa3/) which must contain the
following materials:
• A directory named src/ containing your source codes (e.g. cycleBreaking.cpp): only *.h, *.hpp, *.c,
*.cpp are allowed in src/, and no directories are allowed in src/;
• An executable binary named cb;
• A makefile named makefile or Makefile that produces an executable binary from your source codes
by simply typing “make”: the binary should be generated under the directory pa3/;
• A text readme file named readme.txt describing how to compile and run your program.
Then please use the following command to compress your directory into a .tgz file:
tar zcvf .tgz
The submission file should be named as pa3.tgz (e.g. b06901000 pa3.tgz). For example,
if your student ID is b06901000, then you should use the command below.
2
tar zcvf b06901000 pa3.tgz b06901000 pa3/
Please submit your .tgz file to the NTU COOL system before 1pm, December 29, 2019 (Sunday).
To make sure that your submission satisfies all the requirements, we provide a script checkSubmitPA3.sh to
check your .tgz file by the command below:
bash checkSubmitPA3.sh
For example,
bash checkSubmitPA3.sh b06901000 pa3.tgz
Language/Platform:
1. Language: C or C++.
2. Platform: Linux.
Evaluation:
An individual score per test case is determined by the correctness of the output result as well as the file format
for undirected graph instances. The score is determined by not only correctness but also quality (total weight)
for directed graph instances. The runtime limit for each case is 60 seconds. For fair evaluation, please apply
the -O3 optimization for the compilation. Three input test cases are provided and more hidden test cases will
be used for the final test.
References:
Breadth-first search, depth-first search, minimum spanning trees.
For any questions, please email Shang-Chien Lin at r07943106@ntu.edu.tw or Yi-Ting Lin at r07943102@ntu.edu.tw.
Thank you so much for your cooperation. Have fun with this programming assignment!
3
