max_flow

Scilab function
Last update : 25/04/2007

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);