tpl_netcapgraph.H File Reference

Network flow graph with capacities. More...

#include <tpl_net.H>
#include <ah-errors.H>

Include dependency graph for tpl_netcapgraph.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Net_Cap_Node< Node_Info, F_Type >
	Node with capacity constraint for flow networks. More...
class	Aleph::Net_Cap_Graph< NodeT, ArcT >
	Capacitated network with node capacity constraints. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Network flow graph with capacities.

Example: Maximum flow problem

using Net = Net_Graph<Net_Node<string>, Net_Arc<Empty_Class>>;
Net network;
 
auto source = network.insert_node("Source");
auto a = network.insert_node("A");
auto b = network.insert_node("B");
auto sink = network.insert_node("Sink");
 
// Insert arcs with capacities
network.insert_arc(source, a, 10);  // capacity 10
network.insert_arc(source, b, 8);
network.insert_arc(a, sink, 12);
network.insert_arc(b, sink, 9);
network.insert_arc(a, b, 5);
 
// Compute max flow
Ford_Fulkerson_Maximum_Flow<Net> ff;
auto max_flow = ff(network, source, sink);
cout << "Maximum flow: " << max_flow << endl;

Example: Minimum cut

// After computing max flow, partition is determined
// By max-flow min-cut theorem: max_flow = min_cut capacity
DynList<Net::Node*> source_side, sink_side;
// Nodes reachable from source in residual graph = source_side

Author

Leandro Rabindranath León

Definition in file tpl_netcapgraph.H.