A Friendly Warning This lab has been designed to heavily depend upon the material taught in lab. Unless you feel pretty confident with network flow, it is highly advised not to start this lab without first attending your lab section.
Assignment Description
In this lab you will learn about:
- Flow in a network (a graph-oriented structure) and how to calculate it
- Residual graphs
Lab Insight
Flow algorithms are very powerful and used for many things in the field of Computer Science. It is helpful many times to represent a system as a graph and the flow throughout that graph could very important. For example, flow algorithms are used all the time in networking to try to determine how much throughput a system is getting and whether there is a bottle neck. If you would like to learn more about some the applications for flow with respect to Networking, Distributed Systems, or Algorithms, look into CS 438, CS 425, and CS 473 respectively
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
git push
if you are using multiple machines you may need to use the following to allow them to work correcly.
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.
- Keep looping until no more valid augmenting paths can be found.
- In the loop, get the capacity of the path found using
pathCapacity()
- Using that capacity, you will update three paths:
- 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 capcity from the edge in the flow graph
- Subtract the capacity from the forward edges in the residual graph.
- 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.
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!