CSCI 429 Fall 2023: Lab Network Flow



Due: midnight, Thursday Nov 9 2023

  1. Create your own fork of it on the central repository using the command:
    ssh csci fork csci429/networkflow csci429/$USER/networkflow
    *If you find you are getting warnings about x11 when you run the ssh command, you can include the option -x to prevent them.
    Once you have your central version set up, it is time to create a working copy in your own account. This is done as follows:
    cd ~/csci429
    git clone csci:csci429/$USER/networkflow
    cd networkflow
    Eventually, when all is ready, remember to git push. See csci.viu.ca/~wesselsd/guides/gitstudent.html

  2. (10 marks) You have been provided with a file called networkflow.cpp. It computes the max flow for a graph that is hardcoded into "main". Alter it so that it reads a graph into the program from an external file that is named on the command line. To execute, you should be able to enter "./networkflow graph1" and the result returned will be the value of the maximum flow of the graph encoded in the file graph1. graph1 should look like this:
    5
    0 1 50
    0 2 65
    2 1 80
    2 3 14
    1 3 44
    2 4 16
    3 4 19
    Note that the first entry in the file is the number of nodes. Vertices are assumed to be named 0, 1, ..., n-1, where n is the first entry in the file.
    Your program should output the value of the flow across each edge, as well as the value of the total flow:
    ./networkflow graph2
    0-1: 4 out of 19
    0-2: 16 out of 36
    ...
    Total flow: 148



  3. (10 marks) Copy networkflow.cpp to networkflow2.cpp. This program will attempt to solve multicommodity flows. The graph input will be of the following type:
    5 1.3
    0 1 14 4 18
    0 2 60 60 60
    etc.

    The number of nodes is 5; the value of the second commodity is 1.3 times that of the first commodity. The edge from 0 to 1 has a capacity of 14 of commodity 1, 4 of commodity 2, and a joint capacity (of commodity 1 plus commodity 2) of 18.

    Take a stab at devising a network flow algorithm that will maximize the value of the flow of the two commodities from 0 to node n-1, the sink. You solution may not be optimal, but it must preserve conservation of flow for both commodities: at every node except the source and sink, the flow in of commodity 1 should equal the flow out of commodity 1, and similarly for commodity 2. Also, capacity limits should be adhered to. Can you find an algorithm that is optimal when the value factor is 1 (i.e, the commodities have equal value)? Can you prove it? Does it work when the value factor is not 1?

  4. (10 marks) Edit the README to make your claim about the effectiveness of networkflow2. Does it give a correct flow? Does it give the optimal flow? What are your claims about its running time?


Submit your networkflow.cpp and networkflow2.cpp to git. You should submit a makefile that makes both programs. One mark will be deducted from your grade if the marker has to guess how to make.