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...

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.="" 1.="" define="" a="" c="" type="" called="" edge="" that="" represents="" one="" edge="" of="" a="" flow="" network.="" the="" structure="" that="" you="" typedef="" should="" store="" 4="" fields:="" an="" integer="" y="" storing="" the="" endpoint="" vertex="" y="" of="" an="" edge="" (x,="" y)="" (edge="" from="" x="" to="" y),="" an="" integer="" c="" storing="" the="" capacity="" of="" the="" edge,="" an="" integer="" f="" storing="" the="" flow="" value="" to="" be="" assigned="" on="" the="" edge,="" and="" a="" next="" field="" pointing="" to="" an="" edge="" type="" node="" (for="" creating="" a="" linked="" list="" of="" edges).="" 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.="" 6.="" define="" a="" function="" void="" computemaxflow(graph="" *g,="" int="" s,="" int="" t)="" that="" takes="" as="" parameter="" a="" pointer="" to="" a="" graph="" g,="" the="" id="" of="" the="" source="" vertex="" s="" and="" the="" id="" of="" the="" sink="" vertex="" t,="" and="" computes="" the="" maximum="" flow="" on="" it.="" the="" function="" should="" fill="" up="" the="" f="" field="" in="" every="" edge="" in="" the="" graph="" with="" final="" flow="" value="" assigned="" on="" that="" edge="" when="" the="" maximum="" flow="" is="" found.="" in="" addition,="" it="" should="" print="" the="" value="" of="" the="" maximum="" flow="" with="" a="" nice="" message.="" you="" should="" use="" the="" ford-fulkerson="" method,="" with="" the="" constraint="" that="" at="" every="" step,="" you="" should="" choose="" the="" augmenting="" path="" with="" the="" maximum="" residual="" capacity="" among="" all="" shortest="" augmenting="" paths="" (i.e.,="" find="" the="" set="" of="" all="" augmenting="" paths="" with="" smallest="" number="" of="" edges,="" and="" among="" them="" choose="" the="" one="" with="" the="" maximum="" residual="" capacity).="" 7.="" define="" a="" function="" void="" needbasedflow(graph="" *g)="" that="" takes="" as="" parameter="" a="" pointer="" to="" a="" graph="" g="" and="" computes="" the="" flow="" values="" on="" every="" edge="" for="" the="" need-based="" flow.="" the="" function="" should="" fill="" up="" the="" f="" field="" in="" every="" edge="" in="" the="" graph="" with="" the="" flow="" assigned="" on="" that="" edge.="" this="" function="" must="" call="" the="" computemaxflow="" function()="" (so="" you="" should="" see="" how="" you="" can="" use="" the="" max="" flow="" problem="" to="" solve="" this,="" do="" not="" design="" a="" totally="" different="" algorithm="" of="" your="" own="" for="" this="" assignment,="" that="" will="" not="" be="" graded).="" 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.
Oct 17, 2021
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here