<< Flots Flots min_lcost_cflow >>

metanet >> metanet > Flots > max_flow

max_flow

flot maximum entre deux sommets

Séquence d'appel

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

Paramètres

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 les flots sont données par les éléments g.edges.data.min_cap et g.edges.data.max_cap du graphe.

Les valeurs des capacités maximum et minimum doivent être non négatives . La valeur de la capacité maximum doit être supérieure ou égale à la valeur de la capacité minimum. Si la valeur de min_cap ou de max_cap n'est pas donnée elle est supposé nulle sur chaque arête.

Si les champs de donnée min_cap ou max_cap ne sont pas présents dans la structure du graphe, ils peuvent être ajoutés et affectés en utilisant la fonction add_edge_data.

Exemples

ta=[1 1 2 2 3 3 4 4 5 5 5 5 6 6 6 7 7 15 15 15 15 15 15 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 5 6 7 16 16 16 16 16 16 16];
g=make_graph('foo',1,16,ta,he);
g.nodes.graphics.x=[53,430,202,374,116,250,325,176,373,34,330,233,114,429,208,206];
g.nodes.graphics.y=[86,114,115,129,118,122,133,222,222,221,214,219,218,246,40,301];
ma=edge_number(g);
g=add_edge_data(g,'max_cap',[2,4,3,3,3,2,3,3,5,2,3,1,2,1,4,1,2,2,2,2,4,1,5,3,2,1,5,4,3,4,2]);
g=add_edge_data(g,'min_cap',ones(1,ma))
source=15;g.nodes.graphics.type(source)=2; //source node
sink=16;g.nodes.graphics.type(sink)=1; //sink node
show_graph(g);

[v,phi,ierr]=max_flow(source,sink,g);
g.edges.graphics.foreground(phi<>0)=11;
g=add_edge_data(g,'flow',phi)
g.edges.graphics.display='flow';
show_graph(g);

Report an issue
<< Flots Flots min_lcost_cflow >>