Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 36 ยท Projects and Practice

Project: Volunteer Shift Planner with Max Flow

Build a shift planner with maximum flow: model volunteers and shifts as a network, find assignments, diagnose shortages with a minimum cut and verify the result with SciPy.

A community festival needs volunteers to staff shifts. Every shift needs a certain number of people, every volunteer can only work some shifts, and nobody wants more than a few shifts. Can all shifts be covered? If not, which shifts are short, and who would you have to recruit? This is a classic flow problem, and in this project you will build the planner, diagnose its failures with a minimum cut, and check it against a library.

The model

Build a network with four layers:

flowchart LR
    S((source)) -->|"max shifts"| V1["volunteer"]
    S -->|"max shifts"| V2["volunteer"]
    V1 -->|"1 if available"| H1["shift"]
    V1 --> H2["shift"]
    V2 --> H2
    H1 -->|"demand"| T((sink))
    H2 -->|"demand"| T

Source to volunteers (capacity = shifts they will do), volunteers to shifts (capacity 1 = one person fills a shift at most once), shifts to sink (capacity = people needed).

An integer flow of value F corresponds to F filled positions. If F equals the total demand, every shift is fully staffed.

Step 1: build the network and solve it

We keep the data in plain dictionaries and reuse an Edmonds-Karp implementation. The assignment is read back from the flow on the volunteer-to-shift edges.

Python Step 1: assign volunteers to shifts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every position is filled in this instance (9 of 9). Run it and inspect the roster: no volunteer appears more times than their limit, and no one is scheduled for a shift they cannot do, because the flow respects the capacities.

Step 2: diagnose a shortage with the minimum cut

Now suppose Dara and Fay cancel. The planner must say why it cannot fill the shifts, ideally with a certificate. The minimum cut provides one, and its edges come in three kinds that each tell a different story:

  • Source-to-volunteer edges in the cut: those volunteers are fully booked. The shortage is a lack of people.
  • Volunteer-to-shift edges in the cut: availability is the problem; the shifts cannot reach enough volunteers (a Hall-type violator).
  • Shift-to-sink edges in the cut: those shifts are completely staffed and are not a problem.

We compute the set S reachable from the source in the final residual graph and classify the edges that leave it.

Python Step 2: shortage report from the min cut

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here every source edge is in the cut: all four volunteers are fully booked, and their combined capacity (6) is below the demand (9). The remedy is to recruit three more people (or raise limits), and the per-shift lines show where they are needed most. Had the cut contained availability edges instead, the advice would be to find volunteers available for the starved shifts. Because several minimum cuts can exist, the reachable-set cut is the one closest to the source.

Step 3: verify against SciPy and test sensitivity

Two more checks make the planner trustworthy. First compare the flow value with scipy.sparse.csgraph.maximum_flow. Second, a what-if analysis: for each volunteer, ask "if this person could also work one more shift, would the filled count rise?" Run the solver again with a hypothetical extra availability and report the best recruiting target.

Python Step 3: SciPy cross-check and what-if analysis

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Since the solver is fast, the what-if loop can try every volunteer and shift pair. This pattern, recompute the optimum under a small change, is the basis of sensitivity analysis for all flow-based planners.

Extensions

  • Costs and preferences: minimum-cost flow (successive shortest paths) lets you prefer volunteers' favorite shifts. SciPy's linear_sum_assignment covers the one-to-one case.
  • Skills: split the network per skill, or give each position a type and add a layer.
  • Lower bounds: require every volunteer to work at least one shift (flow with lower bounds, solved by a standard circulation transformation).
  • Fairness: run several rounds, each time giving a unit of priority to the volunteers with the fewest shifts so far.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the shift-planner network, what is the capacity of the edge from the source to a volunteer?

    The source edge limits how many shifts a volunteer can take on, so the flow through that volunteer cannot exceed it.
  2. 2. How does the planner know that all shifts are fully staffed?

    Each unit of flow fills one position, so a flow equal to the total demand saturates every shift-to-sink edge.
  3. 3. What does the source side of the minimum cut reveal when demand cannot be met?

    Vertices reachable in the residual graph delimit a subproblem whose total supply is smaller than its demand, which is exactly the shortage.
  4. 4. Why compare your own max-flow code with SciPy?

    Max-flow values are unique, so a mismatch between two implementations means one of them has a bug.

Summary

  • Staffing problems become flows: source to volunteers (limits), volunteers to shifts (availability), shifts to sink (demand).
  • A flow equal to total demand certifies a complete roster; the residual-reachable set of a smaller flow is a shortage certificate.
  • What-if reruns identify the most valuable new availability.
  • Cross-check against a trusted library, and extend to costs with min-cost flow.

Next: Graph Theory Practice Problems