max_flow - flot maximum entre deux sommets

Calling Sequence

[v,phi,flag] = max_flow(i,j,g)

Parameters

• i : entier, numéro du sommet de départ
• j : entier, numéro du sommet d'arrivée
• g : graphe (liste)
• v : valeur du flot maximum, si elle existe
• phi : vecteur ligne des valeurs des flots sur les arcs
• flag : problème soluble ou non (0 ou 1)

Description

max_flow renvoie la valeur du flot maximum v du sommet i au sommet j si elle existe, et la valeur des flots sur chaque arc sous forme d'un vecteur ligne phi . Les calculs sont faits en nombres entiers. Le graphe doit être orienté. Si le problème n'est pas soluble, flag est égal à 0, sinon il est égal à 1.

Les bornes sur le flot sont données par les éléments edge_min_cap et edge_max_cap du graphe. La valeur de la capacité maximum doit être supérieure ou égale à la capacité minimum. Si la valeur de edge_min_cap ou edge_max_cap n'est pas donnée (vecteur ligne vide [] ), elle est supposée égale à 0 sur chaque arête.

Examples

ta=[1 1 2 2 3 3 4 4 5 5 5 5 6 6 6 7 7 15 15 15 15 15 15];
ta=[ta, 15 8 9 10 11 12 13 14];
he=[10 13 9 14 8 11 9 11 8 10 12 13 8 9 12 8 11 1 2 3 4];
he=[he, 5 6 7 16 16 16 16 16 16 16];
n=16;
g=make_graph('foo',1,n,ta,he);
g('node_x')=[42 615 231 505 145 312 403 233 506 34 400 312 142 614 260 257];
g('node_y')=[143 145 154 154 147 152 157 270 273 279 269 273 273 274 50 376];
ma=edge_number(g);
g('edge_max_cap')=ones(1,ma);
g('edge_min_cap')=zeros(1,ma);
source=15; sink=16;
nodetype=0*ones(1,n); nodetype(source)=2; nodetype(sink)=1;
g('node_type')=nodetype;
nodecolor=0*ones(1,n); nodecolor(source)=11; nodecolor(sink)=11;
g('node_color')=nodecolor;
show_graph(g);
[v,phi,ierr]=max_flow(source,sink,g);
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
g('edge_font_size')=edgefontsize;
g('edge_label')=string(phi);
show_graph(g);