Maximum flow

As explained in Advanced Algorithms and Data Structures

Maximum flow is the problem of sending the greatest possible amount through a capacitated network from a source to a sink while respecting edge capacities and flow conservation.

Maximum flow asks how much can travel through a capacitated directed network from a source s to a sink t. Edge capacities limit flow, and every intermediate vertex must redistribute exactly the amount it receives. The objective is to route flow so that the sink receives as much as possible. section 18.4.1

Model the problem with these ingredients:

• Represent the network as a directed, weighted graph; treat edge weights as capacities. section 18.4.1
• Assign each edge a flow that cannot exceed its capacity. section 18.4.1
• Conserve flow at intermediate vertices: total outbound flow equals total inbound flow. section 18.4.1
• Choose competing routes carefully when downstream capacity makes some outgoing edges more valuable than others. section 18.4.1
• Treat candidate assignments as optimization solutions; genetic algorithms can search for near-optimal flows. section 18.4 section 18.4.1

Routing through a bottleneck

In a hydraulic network, edges represent pipes and capacities represent maximum liquid volumes. If vertex D can receive at most 5 units but can send 6, its outbound flow is still limited by its inbound flow. When F can send only 1 unit to the sink, routing D’s flow toward G may increase the total reaching t. section 18.4.1

Figure 18.22 An example of a network, whose maximum flow is 6.

Use the network diagram to inspect the vertices, capacities, source, sink, and a maximum flow of 6. section 18.4.1

How Advanced Algorithms and Data Structures covers it

How deep it goes

Defines networks, capacities, conservation, and routing choices, then stops short of a complete solving algorithm.

Examples

Uses hydraulic pipes, a D-F-G routing scenario, and chromosome assignments illustrated on a network.

What it assumes

Introduces network terminology from directed weighted graphs rather than assuming prior maximum-flow knowledge.

What you can do after

Evaluate/understand whether candidate edge assignments satisfy flow constraints and maximize delivery to the sink.

How it connects

Connects directed graphs, network flow, optimization, and genetic algorithms.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

• genetic algorithmaddressed by · A genetic algorithm is an evolutionary optimization method that improves a population of candidate solutions through fitness-based selection and variation, often including recombination and mutation.
• optimizationkind of · Optimization is the systematic selection or adjustment of values, actions, or system designs to improve a specified objective, often subject to constraints.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.