Project Summary
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 Requirements:
- Modifying Breadth First Search (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.
- 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).
- 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.
- 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.