Description
Problem statement – single target shortest path:
Given a graph and a node “t”, find the shortest distances of all nodes to “t”
together with the paths. For example, the shortest distance from node 1 to t
is 7 with path 1->3->4->t. Please note that this is different from the singlesource shortest path problem!! However, you can make minor modifications
to the algorithm for that problem to solve this one.
Input files:
In the input file, each line is in format of:
“EdgeId FromNodeId ToNodeId Distance”.
In the above example, the input contains (assume t has node id 0):
0 0 1 10.0
1 1 2 3.0
2 1 3 1.0
3 2 1 3.0
4 2 0 5.0
5 2 3 9.0
6 2 4 2.0
7 3 4 4.0
8 4 0 2.0
9 4 3 6.0
This sample file “tiny-graph.txt” can be downloaded at:
https://webcms3.cse.unsw.edu.au/COMP9313/18s1/resources/15990
Output:
Set the number of reducers to 1. The single output file contains the shortest
distances and paths of all nodes to the given node. Each line is in format of
“SourceNodeID\tDistance\tPath”. The shortest distances are of double
precision, and each path is a sequence of nodes on the shortest path. Remove
the nodes that cannot reach the query node and sort the output by
SourceNodeID according to its numeric value. Given the example graph,
the output file is like:
0\t0.0\t0
1\t7.0\t1->3->4->0
2\t4.0\t2->4->0
3\t6.0\t3->4->0
4\t2.0\t4->0
Code format:
Name your java file as “SingleTargetSP.java” and put it in the package
“comp9313.ass2”. Your program should take three parameters: the input
folder containing the graph file, the output folder storing the result file, and
the query target node ID.
Hints:
1. One difficulty of this problem is how to do the iterative MapReduce
jobs. You can download the code template at:
https://webcms3.cse.unsw.edu.au/COMP9313/18s1/resources/15991
which may help you solve this problem.
2. Another difficulty is how to check the termination criterion, and you
are required to utilize the counter to do this job.
3. After the iterations are finished (i.e., all shortest distances are found),
the output format is not as required. Thus, you need to use another
round map/reduce to convert the output to the desired format. Please
use the output folder given in the parameter to store the result.
Documentation and code readability
Your source code will be inspected and marked based on readability and
ease of understanding. The documentation (comments of the codes) in your
source code is also important. Below is an indicative marking scheme:
Result correctness: 80%
Code structure, Readability, and
Documentation: 20%
Submission:
Deadline: Sunday 22nd April 09:59:59 PM
Log in any CSE server (williams or wagner), and use the give command
below to submit your solutions:
$ give cs9313 assignment2 SingleTargetSP.java
Or you can submit through:
https://cgi.cse.unsw.edu.au/~give/Student/give.php
If you submit your assignment more than once, the last submission will
replace the previous one. To prove successful submission, please take a
screenshot as assignment submission instructions show and keep it by
yourself.
Late submission penalty
10% reduction of your marks for the 1st day, 30% reduction/day for the
following days.
Plagiarism:
The work you submit must be your own work. Submission of work partially
or completely derived from any other person or jointly written with any
other person is not permitted. The penalties for such an offence may include
negative marks, automatic failure of the course and possibly other academic
discipline. Assignment submissions will be examined manually.
Relevant scholarship authorities will be informed if students holding
scholarships are involved in an incident of plagiarism or other misconduct.
Do not provide or show your assignment work to any other person – apart
from the teaching staff of this subject. If you knowingly provide or show
your assignment work to another person for any reason, and work derived
from it is submitted you may be penalized, even if the work was submitted
without your knowledge or consent.
