Description

Assignment no. 7
Objective To implement Depth First Search (DFS) and to use it to do
topological sorting of a directed acyclic graph (DAG)
Total marks 10
Penalty for violating naming convention(s) 5%
Input
Task
Implement DFS and use it to do a topological sorting of the input DAG. The output file should be named as ‘ts.txt’. The output file must contain the vertices – one vertex per line – which represents a topological sorting of the input DAG. Please note that there can be many topological sortings of the same DAG depending on the order in which the DFS is done. You can do DFS in any order that you wish and a valid topological sorting is enough to receive full marks.
Submission
● The program you submit should output ‘ts.txt’ when run.
● The main file of your program should be named as <roll no>.<extension>, where roll no. specifies your roll no. and the extension depends on the language you choose (Usage of C is mandatory for this assignment). Ex: 200010001.c.
● Follow some coding style uniformly. Provide proper comments in your code.
● Submit only through moodle. Submit well in advance. Any hiccups in the moodle/internet at the last minute is never acceptable as an excuse for late submission. Submissions through email or any other means will be ignored.
Evaluation
There are two parts for the evaluation: (i) part 1, you either receive 0 marks or 2 marks. To receive 2 marks you have to make sure that the topological sorting produced by your
algorithms contains exactly the same set of vertices in the DAG;
*****[Note: The given input.graph might also contain Isolated vertices, which means that this type of vertices do not contain any in-coming or out-going edges. These vertices are not present in the input.graph file, but these vertices should be present in the output file ts.txt]
(ii) part2 (max: 8 marks), the marks you obtain will be proportional to the number of edges that is being respected by the sequence of vertices that your program gives as a topological sorting. A sequence of vertices respects a directed edge xy if x comes before y in the sequence.
We will not be using ‘diff’ for the evaluation of this assignment.