Flow, capacity, and bottlenecks

Flow through a network is a polynomial problem. Image segmentation, project selection, sports elimination, ad allocation — all secretly the same problem.

1. 01
   Project-selection-under-budget reduces to max-flow: a source feeds each project's revenue, each project feeds its required resources, resources feed a sink with capacity equal to the budget. Run ford_fulkerson once; the max flow is the optimal portfolio value.

   use petgraph::algo::ford_fulkerson;
   use petgraph::graph::{DiGraph, NodeIndex};
   
   fn max_throughput(network: &DiGraph<&str, u32>, source: NodeIndex, sink: NodeIndex) -> u32 {
       let (flow, _flows) = ford_fulkerson(network, source, sink);
       flow
   }

2. 02
   Three things happen on that let line. First, ford_fulkerson returns a tuple — two values bundled together in one return, no struct required. Tuples are Rust's anonymous "this thing and that thing" type, written with parentheses: the return type here is (u32, Vec<EdgeFlow>). The first slot is the maximum flow (the bottleneck capacity, the answer to "how much can move"); the second is the per-edge flow table you would need if you wanted to actually route the flow. Second, the let (flow, _flows) = … syntax is destructuring: the parentheses on the left of = mirror the tuple's shape, and each name binds to one slot. Third, the underscore prefix on _flows is the convention for "I am intentionally not using this — do not warn me about an unused variable." A bare _ discards entirely; _flows keeps the binding (mostly for documentation, so the reader knows what lives in slot two) without consuming the compiler's attention.

   // A tuple is N values bundled with parentheses.
   let point: (i32, i32)        = (3, 4);
   let pair:  (String, bool)    = (String::from("hi"), true);
   
   // Functions can return tuples — bundle several results without
   // inventing a struct for them.
   fn dimensions() -> (u32, u32) {
       (1920, 1080)
   }
   
   // Destructuring: the parentheses on the left mirror the tuple
   // shape on the right; each name binds to one position.
   let (width, height) = dimensions();
   // width = 1920, height = 1080
   
   // Underscore prefix on a name — "I'm not using this, don't warn."
   let (width, _height) = dimensions();
   //          └─────── compiler stays quiet; binding still exists
   
   // Bare underscore — discard entirely, no binding created.
   let (width, _) = dimensions();
   
   // Why _flows instead of bare _ on page 12?  Documentation.
   // The name tells the reader what would have lived in slot two.
   let (flow, _flows) = ford_fulkerson(network, source, sink);
   //   ─────  ──────
   //    │       └── per-edge flow table — held alive, unused
   //    └────────── the answer: bottleneck capacity, the max flow
   
   // To actually route the flow, drop the underscore and use it:
   let (flow, flows) = ford_fulkerson(network, source, sink);
   for edge_flow in &flows { /* ... */ }