Edge capacity

As explained in Advanced Algorithms and Data Structures

Edge capacity is the maximum amount of flow that a network edge can carry.

Treat a network as a directed, weighted graph with a source and sink. Edge capacity is the maximum flow an edge can carry; actual edge flow may be lower. section 18.4.1

Use capacity to constrain routing. Each vertex redistributes incoming flow, but total outbound flow must match incoming flow, so upstream capacity can limit downstream flow even when outgoing edges have room. section 18.4.1

Hydraulic network

Model pipes as edges and their maximum liquid volume per unit of time as capacities. A pipe may have unused capacity when limited inbound flow or downstream constraints prevent additional routing. section 18.4.1

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

Inspect the network diagram to compare edge capacities, identify bottlenecks, and see how routing choices affect maximum flow. section 18.4.1

How Advanced Algorithms and Data Structures covers it

How deep it goes

Defines capacity and relates it to actual flow, conservation, routing choices, and bottlenecks.

Examples

Uses hydraulic pipes and a worked directed network with competing routes to illustrate capacity and routing.

What you can do after

Evaluate how edge limits and routing choices constrain the total flow reaching a sink.

How it connects

Connects edge capacity with network flow, directed graphs, source nodes, sink nodes, and maximum flow.

liveBookmanning.com

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

Related concepts

• information flowused by · Information flow is the movement and transmission of information through connected processes, systems, networks, or participants.
• capacitykind of · Capacity is the maximum amount of resources, workload, or contents that a system, structure, or process can accommodate or handle under specified 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.