DELIVERABLE: just modified source file Graph.h ---------------------------------------------------------------------- BACKGROUND: You are given a graph class (in the file Graph.h). Many graph operations in the graph class express their results via "labels" assigned to the vertices. There is a vertex_label struct specified in Graph.h which includes the various labels that can be assigned to a vertex (e.g., distance, predecessors, etc.) A particular algorithm like bfs may populate a vector of such labels. The vector is indexed by vertex ID. We sometimes call such a vector a "report." From such reports we can do things like extract paths, etc. All of the operations except bfs (and dfs which you do not need to touch) operate on DAGs. Some Vocabulary: In a DAG G: inputs: subset of vertices with INDEGREE ZERO outputs: subset of vertices with OUTDEGREE ZERO input-path: a path in G STARTING AT AN INPUT VERTEX (and ending at any vertex). output-path: a path in G starting at any vertex and ENDING AT AN OUTPUT VERTEX. input-output-path (or io-path): a path STARTING AT AN INPUT VERTEX _AND_ ENDING AT AN OUTPUT VERTEX. ---------------------------------------------------------------------- INSTRUCTIONS In the source file src/Graph.h you will find a graph class with a bunch of functions already implemented (building the graph, dfs, bfs, topo-sort...) and also a number of "stubs" for functions which you are to complete. GETTING FAMILILAR WITH THE CODE: Browse the Graph.h file to gain an understanding of how a graph instance is organized. Start with the comments starting around line 40. Draw some diagrams so you understand how a graph instance represents a particular graph. WARMUP "LAB": follow the instructions in src/WARMUP-LAB.txt to help get more familiar with some fundamental algorithms and interpreting their results. YOUR JOB FOR THIS ASSIGNMENT: Now that you are warmed up, your task for this assignment is to implement each new feature/function marked with "TODO" in Graph.h Each TODO item has a banner comment explaining the requirements. Below is a short summary of the TODO items (see Graph.h for details). TODO 1 (10 points): Modifying BFS so that the NUMBER OF SHORTEST PATHS to each vertex is recorded. Recall that in BFS path length is simply measured by number of edges. TODO 2 (20 points): Path extraction (function: extract_path). When an algorithm like BFS or DFS (or the critical paths function below) is run, the actual paths explored/discovered are encoded using "predecessor" information. Given the predecessor info, you will reconstruct paths (see comments for details). Advice: you might attempt extract_path first. TODO 3 (30 points): implement function dag_critical_paths. This function takes a DAG and labels each vertex with the length of the LONGEST input path ("critical-paths" measured by sum of edge weights) ending at that vertex. It also encodes the paths themselves using the predecessor values (and the paths can be extracted using TODO 2 above.) TODO 4 (30 points): Implement function dag_num_paths. This function labels each vertex with the number of input-to-output paths which include that vertex. This function does not encode any particular paths. It simply records the number of such paths. See source code for details. TODO 5 (30 points): Implement function valid_topo_order. This function takes a vertex ordering and determines if it is indeed a valid topological ordering of the given graph. (If graph is not even a DAG, the function will return false). See source code for details. TODO 6 (30 points): Implement function enum_paths. This function takes a vertex and constructs ALL input-paths ending at that vertex. The paths are represented as strings; a vector of strings is populated with the paths.

Graph.h will be in comments. please comment so that i could reply the graph.h