Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
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;
Flow network implemented with adjacency lists.
Definition tpl_net.H:261
Node * insert_node(const Node_Type &node_info)
Insert a new node by copying node_info.
Definition tpl_net.H:559
Arc * insert_arc(Node *src_node, Node *tgt_node, const Flow_Type &cap, const Flow_Type &flow, const typename Arc::Arc_Type &arc_info=Arc_Type())
Insert a capacitated arc with an initial flow.
Definition tpl_net.H:607
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.