Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
net_apps_example.cc File Reference

Network Flow Applications: Real-World Problem Solving. More...

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <cstring>
#include <net_apps.H>
Include dependency graph for net_apps_example.cc:

Go to the source code of this file.

Functions

static bool has_flag (int argc, char *argv[], const char *flag)
 
void demo_project_selection ()
 Demo 1: Project Selection Problem.
 
void demo_image_segmentation ()
 Demo 2: Image Segmentation.
 
void demo_baseball_elimination ()
 Demo 3: Baseball Elimination.
 
void demo_survey_design ()
 Demo 4: Survey Design.
 
int main (int argc, char *argv[])
 

Detailed Description

Network Flow Applications: Real-World Problem Solving.

This example demonstrates how network flow algorithms solve diverse real-world optimization problems. Many seemingly unrelated problems can be reduced to max-flow or min-cut, enabling efficient polynomial-time solutions. This showcases the power of algorithmic reductions.

The Power of Reductions

What is a Reduction?

A reduction transforms problem A into problem B such that:

  • Solution to B gives solution to A
  • If B is polynomial-time, then A is also polynomial-time

Why Network Flow?

Network flow is powerful because:

  • Many problems reduce to it: Diverse applications
  • Polynomial-time algorithms: Efficient solutions exist
  • Min-cut duality: Max-flow = Min-cut (powerful tool)
  • Well-studied: Many efficient algorithms available

Reduction Strategy

To reduce problem P to max-flow:

  1. Model problem as network
  2. Encode constraints as capacities
  3. Encode objective as flow
  4. Solve max-flow
  5. Extract solution from flow

Applications Demonstrated

1. Project Selection (Max Closure Problem)

Problem Statement

Choose projects to maximize profit while respecting dependencies:

  • If project A requires project B, both must be chosen
  • Some projects have profit, others have cost
  • Goal: Maximize net profit

Reduction to Min-Cut

Network construction:

Source → Projects with profit (capacity = profit)
Projects with cost → Sink (capacity = cost)
Dependencies: A requires B → B → A (infinite capacity)

Key insight: Min-cut separates profitable projects from costly ones. Projects on source side are selected.

Applications

  • Portfolio optimization: Choose investments with dependencies
  • Feature selection: Choose features respecting constraints
  • Resource planning: Select projects optimally

2. Image Segmentation (Graph Cuts)

Problem Statement

Label each pixel as foreground or background optimally:

  • Pixels similar to foreground should be foreground
  • Pixels similar to background should be background
  • Neighboring pixels should have same label (smoothness)

Reduction to Min-Cut

Network construction:

Source → Pixels (capacity = foreground affinity)
Pixels → Sink (capacity = background affinity)
Neighboring pixels → edges (capacity = similarity penalty)

Key insight: Min-cut minimizes total penalty:

  • Cut source-pixel edge: pixel is background
  • Cut pixel-sink edge: pixel is foreground
  • Cut pixel-pixel edge: neighbors have different labels

Applications

  • Computer vision: Object segmentation
  • Medical imaging: Organ segmentation
  • Photo editing: Background removal

3. Baseball Elimination

Problem Statement

Determine which teams can still win the league given:

  • Current standings (wins per team)
  • Remaining games (who plays whom)
  • Can a specific team still win?

Reduction to Max-Flow

Network construction:

Source → Games (capacity = 1 game)
Games → Teams (capacity = 1, represents game outcome)
Teams → Sink (capacity = max_wins - current_wins)

Key insight: If max-flow saturates all game edges, team can win by distributing wins appropriately.

Applications

  • Sports analytics: Tournament analysis
  • Tournament scheduling: Determine possible outcomes
  • Game theory: Analyze competition scenarios

4. Survey Design

Problem Statement

Assign respondents to questions ensuring:

  • Coverage: Each question answered by required number of people
  • Constraints: Each person answers exactly k questions
  • Feasibility: Is such assignment possible?

Reduction to Max-Flow

Network construction:

Source → Respondents (capacity = k questions per person)
Respondents → Questions (capacity = 1, person can answer question)
Questions → Sink (capacity = required respondents per question)

Key insight: Max-flow = total assignments. If it equals required coverage, assignment is possible.

Applications

  • Market research: Design surveys efficiently
  • Experimental design: Assign treatments to subjects
  • Resource allocation: Match resources to tasks

General Reduction Pattern

Max-Flow Reductions

Problems reducible to max-flow often involve:

  • Matching: Assigning items to slots
  • Coverage: Ensuring requirements met
  • Flow constraints: Capacity-like limitations

Min-Cut Reductions

Problems reducible to min-cut often involve:

  • Partitioning: Dividing into two groups
  • Selection: Choosing subset optimally
  • Labeling: Assigning binary labels

Complexity

Polynomial-Time Solutions

Since max-flow can be solved in polynomial time:

  • Edmonds-Karp: O(VE²)
  • Dinic: O(V²E)
  • HLPP: O(V²√E)

Any problem reducible to max-flow is also polynomial-time!

Comparison with Alternatives

Problem Direct Approach Max-Flow Reduction
Project Selection Exponential (try all) O(VE²)
Image Segmentation Heuristic O(VE²) optimal
Baseball Elimination Complex logic O(VE²)
Survey Design Constraint solving O(VE²)

Key Insight

Many optimization problems can be reduced to max-flow or min-cut, allowing efficient polynomial-time solutions. The art is recognizing when a problem has this structure!

Look for:

  • Binary choices (select/don't select)
  • Capacity-like constraints
  • Matching/assignment problems
  • Partitioning problems

Usage

# Run all application demos
./net_apps_example
# Run specific application
./net_apps_example --project-selection
./net_apps_example --image-segmentation
./net_apps_example --baseball-elimination
./net_apps_example --survey-design
# Show help
./net_apps_example --help
See also
net_apps.H Application-specific reductions and utilities
tpl_maxflow.H Maximum flow algorithm implementations
network_flow_example.C Basic max-flow introduction
maxflow_advanced_example.cc Advanced max-flow algorithms
Author
Leandro Rabindranath León

Definition in file net_apps_example.cc.

Function Documentation

◆ demo_baseball_elimination()

void demo_baseball_elimination ( )

Demo 3: Baseball Elimination.

Determine if a team is mathematically eliminated from winning. A team is eliminated if no outcome of remaining games allows them to finish first.

Definition at line 414 of file net_apps_example.cc.

References Aleph::check_baseball_elimination(), Aleph::maps(), and Aleph::HTList::size().

Referenced by main().

◆ demo_image_segmentation()

void demo_image_segmentation ( )

Demo 2: Image Segmentation.

Segment an image into foreground and background using graph cuts. Each pixel has costs for being foreground or background. Adjacent pixels prefer having the same label.

Definition at line 333 of file net_apps_example.cc.

References Aleph::maps(), and Aleph::segment_image().

Referenced by main().

◆ demo_project_selection()

void demo_project_selection ( )

Demo 1: Project Selection Problem.

A company must choose which projects to undertake. Some projects have positive profit, others have costs. Some projects depend on others (prerequisites).

Goal: Maximize total profit while respecting dependencies.

Definition at line 275 of file net_apps_example.cc.

References Aleph::maps(), and Aleph::solve_project_selection().

Referenced by main().

◆ demo_survey_design()

void demo_survey_design ( )

Demo 4: Survey Design.

Assign respondents to survey questions respecting constraints:

  • Each question needs min-max responses
  • Each respondent answers min-max questions
  • Respondents can only answer eligible questions

Definition at line 497 of file net_apps_example.cc.

References Aleph::count(), Aleph::design_survey(), Aleph::maps(), and Aleph::HTList::size().

Referenced by main().

◆ has_flag()

static bool has_flag ( int  argc,
char *  argv[],
const char *  flag 
)
static

Definition at line 258 of file net_apps_example.cc.

References Aleph::maps().

Referenced by main().

◆ main()

int main ( int  argc,
char *  argv[] 
)