Description

Programming Assignment 1

Your input is:

A directed graph with non-negative integral capacities on every edge, and need n(i) on every vertex i. The graph will be given in a file in a specific format that your program will first read into an adjacency list. You can assume that the n(i) values will be positive or negative integers or 0.

Your program should output:

An assignment of flow f on every edge subject to the above conditions if possible, or say that it is not possible. For example, as a trivial case, if all n(i) are positive, no flow assignment is possible satisfying the above conditions (as there are no producers for the consumers).

Your program should contain the following types/functions etc. Please adhere strictly to the type/function names, function prototypes etc. so that your program runs properly when TAs test it. Do not use the structure field names for any other variable names in your program.

2. Define a C type called VERTEX to represent one vertex of the flow network. The structure that you typedef should contain 3 fields, an integer x storing the id of the vertex, an integer n storing the need value of the vertex, and a pointer p storing a pointer to an EDGE node (basically p will point to the first node in the adjacency list of the vertex).
3. Define a C type called GRAPH that stores the directed graph. The graph will be stored as an adjacency list. The C structure that you typedef should store 3 things: an integer V storing the number of vertices, an integer E storing the number of edge, and a pointer H storing a pointer to an array of VERTEX nodes (basically H stores a pointer to an array containing the vertices of the adjacency list, with each vertex pointing to its edge list).
4. Define a function GRAPH *ReadGraph(char *fname) that reads the graph from a file whose name is given in the null-terminated string fname. It should also initialize the fields appropriately. The function should return a pointer to the graph formed. The format of the input file is described at the end.
5. Define a function void PrintGraph(GRAPH G) that prints the graph G. A sample format for printing the graph is described at the end.
8. Design a main function that does the following exactly in this order:
a. Read in the file name from the keyboard into a string S (you can assume that the maximum size of the file name is 20 characters)
b. Call the function ReadGraph() to read and initialize the graph
c. Call the function PrintGraph() to print the graph
d. Read in the identifiers of the source and the sink (in that order)
e. Call the function ComputeMaxFlow() to compute and print the maxflow in the graph, taking the ids read in as source and sink
f. Call the function PrintGraph() to print the graph
g. Call the function ReadGraph() again to read and initialize the graph (as the original graph has been changed by the ComputeMaxFlow() call)
h. Call the function NeedBasedFlow() to compute the need-based flow in the graph
i. Call the function PrintGraph() to print the graph

Input File Format
If the graph has N vertices, the vertices will be identified by the integers 1, 2, ….,N.
The first line of the file contains 2 integers, N followed by M (separated by spaces), where N is the number of vertices and M is the number of edges
The second line contains N integers, with integer i representing the need value of vertex i.
This is followed by M lines, with each line containing three integers x, y, c separated by spaces where x and y represent the vertex identifiers of the edge from x to y, and c represents the capacity of the edge.
For example, consider the following graph with 3 vertices and 3 edges. The identifiers for each vertex are shown inside the circle representing the vertex, and the need of the vertex is shown against it just outside the circle.

Then the graph will be represented in the file by the following lines:
3 3
-5 5 0
1 2 7
3 1 12
2 3 10

Output Print Format
Print the graph as a normal adjacency list in the following format, with one line for the edge list of each vertex 1, 2, 3,….,N 1 -> (x, c, f) -> (x, c, f)->….
2 -> (x, c, f) -> (x, c, f)->….
.
N -> (x, c, f) -> (x, c, f)->….

For example, if you want to find a need-based flow, the example graph will be printed as
1 -> (2, 7, 5)
2-> (3, 10, 0)
3-> (1, 12, 0)
You can verify that the flow assignments satisfy the constraints of a need-based flow for the example graph shown.