lab_flow

Assignment Description

In this lab you will learn about:

• Flow in a network (a graph-oriented structure) and how to calculate it
• Residual graphs

Checking Out the Code

All assignments will be distributed via our release repo on github this semester. You will need to have set up your git directory to have our release as a remote repo as described in our git set up.

You can merge the assignments as they are released into your personal repo with

git pull --no-edit --no-rebase release main --allow-unrelated-histories
git push

The first git command will fetch and merge changes from the main branch on your remote repository named release into your personal. The --no-edit flag automatically generates a commit message for you, and the--no-rebase flag will merge the upstream branch into the current branch. Generally, these two flags shouldn’t be used, but are included for ease of merging assignments into your repo.

The second command will push to origin (your personal), which will allow it to track the new changes from release.

You will need to run these commands for every assignment that is released.

All the files for this lab are in the lab_flow directory.

Preparing Your Code

This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the lab_flow directory.

mkdir build
cd build

This first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake ..

This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

The code for this activity resides in the lab_flow/ directory.

Graph Class

In this lab, you will make use of a graph class that we have implemented for you. With this graph class you will need to insert a directional edge, which goes from a source vertex to a destination vertex. The Edge class is defined for you in edge.h and we define the structure Vertex to just be a string.

It is recommended that you read up on the graph class and it’s API, see the Doxygen for this lab (or check out the file graph.h).

Network Flow

The idea behind a network flow is to use graph entities to model a sort of capacity problem along various paths. Basically, flow is bounded by the edge weights in a graph. As we compute the total graph flow, we build a secondary residual graph to keep track of the remaining capacity of the edges in the graph.

When we begin calculating flow through a network, we build a residual graph to aid us. The residual graph keeps track of the remaining capacity each edge currently supports. When we begin our algorithm we set the flow on all edges to 0 and we assign the weights of our edges to the residual graph like show below.

Part 1: Constructing the Network Flow

To calculate the flow of a network using the algorithm discussed in lab, you need to have both a flow and residual graph. The goal of your constructor is to build the residual and flow graphs from the provided graph.

Part 2: Calculating the Overall Capacity of a Path in a Network

Next, we need to calculate the net capacity of a provided path. To do so, simply find the minimum weight among the edges in the path in the residual graph by iterating through the vertices in the path vector.

Part 3: Calculate the Flow in a Network

Now, we will take the function made in Part 2, pathCapacity() and use it to help us calculate the total flow of our graph network. Here is a breakdown of the algorithm in its fundamental steps.

1. Use the provided findAugmentingPath() function to identify a valid augmenting path. When there are no valid paths, the algorithm is complete.
2. In the loop, get the capacity of the path found using pathCapacity()
3. Using that capacity, you will update three paths:
   1. Add the capacity to the edges in the corresponding path in the flow graph. Note that this path may go in the opposite direction of the edge in your graph. In that case, reverse the vertices and subtract the capacity from the edge in the flow graph
   2. Subtract the capacity from the forward edges in the residual graph.
   3. Add the capacity to the reverse edges in the residual graph.

The algorithm is finished when no more paths with nonzero capacity can be found from the source node to the sink node.

NOTE: One conceptual trick you must understand is that ‘forward’ and ‘reverse’ in the above pseudocode is context dependent. If the path uses the edge B->A then that edge is forward and the reverse edge is A->B. Don’t forget to update the flow graph in the appropriate way though – it only has edges in one direction!

Let’s Test Out Network Flow

A main.cpp is provided that lets you simulate a small network flow example:

./flow

After testing with this binary, be sure to use our full set of test cases for this lab.

./test

Grading Information

The following files are used for grading this lab:

• NetworkFlow.h
• NetworkFlow.cpp

All other files including any testing files you have added will not be used for grading. Remember that submissions must be done through Prairielearn!

Good luck!