network_flow_example.C File Reference

Maximum flow in Aleph-w networks (Ford-Fulkerson) + max-flow reductions (matching). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tpl_net.H>
#include <tclap/CmdLine.h>

Include dependency graph for network_flow_example.C:

Go to the source code of this file.

Typedefs
using	NodeInfo = string
using	ArcInfo = Empty_Class
using	FlowType = int
using	FlowNet = Net_Graph< Net_Node< NodeInfo >, Net_Arc< ArcInfo, FlowType > >

Functions
FlowNet	build_water_network ()
	Build a sample flow network.
FlowNet	build_datacenter_network ()
	Build a more complex network.
void	print_network (FlowNet &net, const string &title)
	Print network structure and flow.
void	demonstrate_min_cut (FlowNet &net)
	Demonstrate min-cut (dual of max-flow)
void	demonstrate_bipartite_matching ()
	Demonstrate bipartite matching as max-flow.
int	main (int argc, char *argv[])

Detailed Description

Maximum flow in Aleph-w networks (Ford-Fulkerson) + max-flow reductions (matching).

Overview

This example demonstrates the maximum flow problem on Aleph-w's Net_Graph data structure. It uses the classic Ford-Fulkerson method (DFS augmenting paths) to compute a max flow from a single source to a single sink.

It includes three demos:

• A small water distribution network.
• A more complex datacenter-style network.
• A bipartite matching reduction (max-flow = max matching).

Data model used by this example

• Network type:
  • FlowNet = Net_Graph<Net_Node<string>, Net_Arc<Empty_Class, int>>
• Node info: label/name (string)
• Arc capacity/flow:
  • capacity and flow are stored in Net_Arc<..., FlowType> (here FlowType = int).

Notes:

• Net_Graph tracks sources/sinks incrementally: nodes with no incoming arcs are sources, nodes with no outgoing arcs are sinks.
• The max-flow routine used here requires exactly one source and one sink.

Usage / CLI

# Run all demos (default if no specific demo flags are given)
./network_flow_example
 
# Run a single demo
./network_flow_example --simple
./network_flow_example --complex
./network_flow_example --matching
 
# Explicitly run all demos
./network_flow_example --all
 
# Verbose output (flag exists; this example currently ignores the value)
./network_flow_example --verbose
 
# Show help
./network_flow_example --help

Algorithms

Ford-Fulkerson (DFS augmenting paths)

The program calls ford_fulkerson_maximum_flow(net). Conceptually:

1. Start with zero flow.
2. While there exists an augmenting path from source to sink in the residual network:
   • Find the path (here, via DFS)
   • Push the bottleneck capacity along it
3. The final total outflow of the source is the maximum flow.

Reductions: bipartite matching

The matching demo uses unit-capacity edges and interprets flow == 1 on worker→task arcs as selected matches.

Complexity

Let V be the number of nodes and E the number of arcs.

• Ford-Fulkerson (DFS): O(E * F) where F is the value of the max flow (pseudo-polynomial; can be very slow on some inputs).
• Edmonds-Karp (BFS augmenting paths): O(V * E^2) (not used in this file).

In practice, prefer the advanced max-flow examples for faster algorithms.

Pitfalls and edge cases

• Multiple sources/sinks: if your network has multiple sources/sinks you typically need to add a super-source/super-sink (see tpl_net.H).
• Integral capacities: with integral capacities Ford-Fulkerson terminates, but performance can still be poor; algorithm choice matters.
• Interpreting results: the final flow is stored on arcs (arc->flow), and the residual network is implicit in the implementation.

References / see also

• tpl_net.H (network structure)
• maxflow_advanced_example.cc (Dinic / HLPP / scaling, etc.)
• mincost_flow_example.cc (min-cost flow)
• bipartite_example.C (matching concepts)

Author

Leandro Rabindranath León

Definition in file network_flow_example.C.

Typedef Documentation

ArcInfo

using ArcInfo = Empty_Class

Definition at line 146 of file network_flow_example.C.

FlowNet

using FlowNet = Net_Graph<Net_Node<NodeInfo>, Net_Arc<ArcInfo, FlowType> >

Definition at line 152 of file network_flow_example.C.

FlowType

using FlowType = int

Definition at line 149 of file network_flow_example.C.

NodeInfo

using NodeInfo = string

Definition at line 143 of file network_flow_example.C.

Function Documentation

build_datacenter_network()

FlowNet build_datacenter_network

(

)

Build a more complex network.

Definition at line 206 of file network_flow_example.C.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), and Aleph::maps().

Referenced by main().

build_water_network()

FlowNet build_water_network

(

)

Build a sample flow network.

Water distribution network:

               [B]
              / | \
            10  4   8
           /    |    \
[Source]--     [D]    --[Sink]
          \    /|\   /
           8  5 2  6
            \ | | /
              [C]

The topology ensures Source has no incoming arcs and Sink has no outgoing arcs.

Definition at line 171 of file network_flow_example.C.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

Referenced by main().

demonstrate_bipartite_matching()

void demonstrate_bipartite_matching

(

)

Demonstrate bipartite matching as max-flow.

Definition at line 317 of file network_flow_example.C.

References Aleph::ford_fulkerson_maximum_flow(), GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::Net_Graph< NodeT, ArcT >::is_sink(), Aleph::Net_Graph< NodeT, ArcT >::is_source(), and Aleph::maps().

Referenced by main().

demonstrate_min_cut()

void demonstrate_min_cut

(

FlowNet &

net

)

Demonstrate min-cut (dual of max-flow)

Definition at line 290 of file network_flow_example.C.

References GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), and Aleph::maps().

Referenced by main().

main()

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

Definition at line 387 of file network_flow_example.C.

References build_datacenter_network(), build_water_network(), demonstrate_bipartite_matching(), demonstrate_min_cut(), Aleph::ford_fulkerson_maximum_flow(), Aleph::maps(), and print_network().

print_network()

void print_network	(	FlowNet &	net,
		const string &	title
	)

Print network structure and flow.

Definition at line 241 of file network_flow_example.C.

References GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Net_Graph< NodeT, ArcT >::get_sink(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Net_Graph< NodeT, ArcT >::is_sink(), Aleph::Net_Graph< NodeT, ArcT >::is_source(), and Aleph::maps().

Referenced by main().