PROGRAM-5: adding features to a graph class Solution

----------------------------------------------------------------------




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.







The above items total 150 points. In addition, submissions receive up to

50 points for "honest effort" (i.e., there was clear effort put into the

assignment even if the result does not work completely).




Note: "honest effort" and "turned in _something_" are not the same thing!




Total Points Possible: 200




General suggestion: use programs bfs.cpp, dfs.cpp, topo.cpp and epaths.cpp as

models for additional programs to test your additional features.