Due date: Wednesday, November 5, 2020.

In this homework we'll be implementing the Topological Sorting problem discussed in class with MPI.

Download the following files.
graph.cc
graph.h
process_graph.cc
process_graph.h
main.cc
Makefile
graph.txt
graph1.txt
graph2.txt

The program is compiled with the command make and run with "make run" or "mpirun -np ## depends", where ## stands for the number of processes. For now, if you run the program with a single process, it will display the graph and then exit with an error message. If you run it with 10 processes (as the default is for "make run"), then you will notice a deadlock after the graph is displayed. However, you can still verify that the graph was read correctly.

The first two graph files contain the graphs that can be seen in the PowerPoint slides and in the notes. The third one is based on the following image:

In this program, we must find an ordering for the vertices in a directed graph such that for every edge (a --> b), the vertex a is before b in the list. Each vertex in the graph can represent a task to be done, and each edge a dependency between the two tasks.

Solution Description

For this, we will assign a process to each vertex in the graph. The process will be writing out the value of its own id when it is time for it to be executed. The process will first need to receive a message from each vertex that it is dependent on (all the incoming edges). When all of its dependencies are solved, then the process can execute the task by outputting a message. Finally, after its task is done, the process much send a message to all the other vertices that depend on it, to let them know that they can proceed now. In pseudocode, this can be described as

Process(id) {
   for all incoming "in" vertices 
      Receive(dummy, in);
   output id;
   Perform_task(id);
   for all outgoing "out" vertices
      Send(dummy, out);
}

For example, in the graph in the following figure:

a. Implement the function Send_incoming in the Graph class. This function should send each process the number of incoming edges, and if the number is not 0, then it should also send the array of incoming vertices.

b. Implement the function Process_dependency in the file process_graph.cc. This function should implement the outline given in pseudocode above. You can also find it in this notes file and in the PowerPoint slide. In this function, the process with the id given by the first parameter should

• first receive a message from all the processes with ids present in its incoming array,
• output a message containing the id, so that we can track the order in which the processes get to that point,
• then send a message to all the processes with ids in the outgoing dependency array.

What to look for in the result: is the order in which the processes output their id in the middle of the function Process(id) above consistent with the dependency order in the graph?

Upload: to Canvas, Assignments, Homework 9, all the files that you modify, add, create.