Consider a flow problem where, unlike the maximum-flow problem you have seen so far, there are no special vertices s (source) and t (sink).
computer science
Description
Consider a flow problem where, unlike the maximum-flow problem you have seen so far, there are no special vertices s (source) and t (sink). However, each vertex may produce some amount of an item or consume some amount of the item. In addition, the vertices allow items to flow through them for distribution to other vertices. Let n(i) denote the amount that a vertex i produces or consumes. Thus, if n(i) = 0, the vertex is neither a producer nor a consumer, the vertex is a consumer if n(i) > 0, and the vertex is a producer if n(i) < 0. The items produced are shipped along the edges to satisfy the needs of the consumers. The flow assignments along the edges should be such that in addition to the standard capacity constraints, if vertex i is a producer then its total outflow must be greater than its total inflow by |n(i)| at any time, if vertex i is a consumer then its total inflow must be greater than its total outflow by |n(i)| at any time, and the total inflow must be equal to the total outflow for all other vertices.
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.
