|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Network Flow Applications: Real-World Problem Solving. More...
#include <iostream>#include <iomanip>#include <vector>#include <string>#include <map>#include <cstring>#include <net_apps.H>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[]) |
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.
A reduction transforms problem A into problem B such that:
Network flow is powerful because:
To reduce problem P to max-flow:
Choose projects to maximize profit while respecting dependencies:
Network construction:
Key insight: Min-cut separates profitable projects from costly ones. Projects on source side are selected.
Label each pixel as foreground or background optimally:
Network construction:
Key insight: Min-cut minimizes total penalty:
Determine which teams can still win the league given:
Network construction:
Key insight: If max-flow saturates all game edges, team can win by distributing wins appropriately.
Assign respondents to questions ensuring:
Network construction:
Key insight: Max-flow = total assignments. If it equals required coverage, assignment is possible.
Problems reducible to max-flow often involve:
Problems reducible to min-cut often involve:
Since max-flow can be solved in polynomial time:
Any problem reducible to max-flow is also polynomial-time!
| 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²) |
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:
Definition in file net_apps_example.cc.
| 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().
| 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().
| 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().
| void demo_survey_design | ( | ) |
Demo 4: Survey Design.
Assign respondents to survey questions respecting constraints:
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().
|
static |
| int main | ( | int | argc, |
| char * | argv[] | ||
| ) |
Definition at line 570 of file net_apps_example.cc.
References demo_baseball_elimination(), demo_image_segmentation(), demo_project_selection(), demo_survey_design(), has_flag(), and Aleph::maps().