C/C++/java program

1. Implement a graph parser for the following graph file format v <id> <label> d *or* u <source> <target> <label> % <comments> For example, a ‘triangle’-shaped graph could be defined as v 1 a v 2 b v 3 c d 1 2 t d 2 3 t u 3 1 t Implement Breadth-First Search Implement Depth-First Search Implement Topological Sort Your program should execute as follows ## Deliverables 1. Implement a graph parser for the following graph file format v <id> <label> d *or* u <source> <target> <label> % <comments> For example, a ‘triangle’-shaped graph could be defined as v 1 a v 2 b v 3 c d 1 2 t d 2 3 t u 3 1 t 1. A vertex must be defined before using its ID in an edge definition. 2. Both vertex and edge labels can be alphanumeric. 3. Edges are considered ‘directed’ when defined using ‘d’. 4. Edges are considered ‘undirected’ when defined using ‘u’. Quite simply, insert an edge in both directions when parsing a ‘u’. 5. Any line starting with the character ‘%’ should be ignored (and can be used to add comments). 6. Define your own graph data structure and populate it using data read from the input file. i. Your program must accept the input-file’s name as its input. 1. If your program is named “Program5?? it could be started using > Program5 [login to view URL] 1. Implement Breadth-First Search 1. In addition to following the BFS pseudocode in the textbook, extend your algorithm so that it prints the *discovery* and *visit* events for each node. 2. Implement Depth-First Search 1. In addition to following the DFS pseudocode in the textbook, extend your algorithm so that it prints the *discovery*, *visit* and *finish* events for each node. 3. Implement Topological Sort 1. Based on your DFS implementation, create a new algorithm that implements TS. When your algorithm is finished with a node, insert the satellite data of that node onto the front of a linked list. 2. Once your TS algorithm is finished, print the contents of your linked list. 4. Your program should execute as follows 1. Invoke BFS with vertex ID = 1 as the starting point. 2. Invoke DFS (it should visit all vertices). 3. Invoke TS (it should also visit all vertices). <!-- --> 1. Invoke BFS with vertex ID = 1 as the starting point. 2. Invoke DFS (it should visit all vertices). 3. Invoke TS (it should also visit all vertices).