tpl_netcapgraph_example.cc File Reference

Educational examples for capacity-constrained flow networks. More...

#include <iostream>
#include <tpl_netcapgraph.H>
#include <tpl_net.H>

Include dependency graph for tpl_netcapgraph_example.cc:

Go to the source code of this file.

Functions
int	main ()

Detailed Description

Educational examples for capacity-constrained flow networks.

WHAT IS A CAPACITY NETWORK?

Network where arcs have capacity limits (max flow through arc) Foundation for maximum flow and minimum cut problems Core structure for many optimization algorithms

MAXIMUM FLOW PROBLEM:

Given: Source node, sink node, arc capacities Find: Maximum amount of "flow" from source to sink Subject to:

1. Flow conservation (in = out at each node)
2. Capacity constraints (flow ≤ capacity)

KEY ALGORITHMS:

• Ford-Fulkerson: Augmenting paths, O(E * max_flow)
• Edmonds-Karp: BFS for paths, O(V * E^2)
• Dinic: Level graphs, O(V^2 * E)
• Push-Relabel: O(V^3) or O(V^2 * sqrt(E))

COMPILE & RUN:

g++ -std=c++20 -I.. -o tpl_netcapgraph_example tpl_netcapgraph_example.cc ./tpl_netcapgraph_example

Definition in file tpl_netcapgraph_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 39 of file tpl_netcapgraph_example.cc.

References Aleph::maps().