Algorithme de Ford-Fulkerson

[moujaprim]

Voilà le code de la fonction:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
%WHITE =0;
%GRAY=1;
%BLACK=2

function augmentpath=bfs_augmentpath(start,target,current_flow,capacity,n)
    n=10;
    WHITE =0;
    GRAY=1;
    BLACK=2;
    color(1:n)=WHITE;
    head=1;
    tail=1;
    q=[];
    augmentpath=[ ];
    start=2;
    bInf = 0.5 ;
    bSup = 5 ;
    M    =    10 ;
    N    =    10 ;
    
    capacity = bInf + (bSup-bInf).*rand(M, N);
    
    %ENQUEUE
    
    q=[start q];
    
    color(start)=GRAY;
    
    pred(start) = -1;
    
    pred=zeros(1,n);
    
    while ~isempty (q) 
      %  [u,q]=dequeue(q);
            u=q(end);
            q(end)=[];
            color(u)=BLACK;
    %     dequeue end here
            
            for v=1:n
                if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )
    %enqueue(v,q)
                    q=[v q];
                    color(v)=GRAY;
    % enqueue end here
                    pred(v)=u;                        

                end
            end
    end
    
    if color(target)==BLACK       %if target is accessible
       temp=target;
       while pred(temp)~=start
        augmentpath = [pred(temp) augmentpath];     %augment path doesnt containt the start point AND target point
        temp=pred(temp);
       end
       augmentpath=[start augmentpath target];
    else
        augmentpath=[];         % default resulte is empty
    end

[moujaprim]

Il ne me donne pas encore l'erreur de définition de la fonction parce ce que j'ai renommé le fichier par le nom de la fonction

voila la commande que je saisi sur MATLAB:

Code :

augmentpath = bfs_augmentpath(1,5,12,31,6)

??? Index exceeds matrix dimensions.

Error in ==> C:\MATLAB6p5\toolbox\grtheorie\bfs_augmentpath.m
On line 42  ==>                 if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )

mais ça c'est mon nouveau message d'erreur !

[magelan]

Ouf!! Déjà un problème en moins.

La fonction principale est ff_max_flow (qui fera appel à bfs_augmentpath), pourquoi veux-tu faire appel directement à bfs_augmentpath? Que cherches-tu à faire?

Dans tout les cas, je te suggère de bien relire la description :

Main function is function max_flow=ff_max_flow(source,sink,capacity,nodes_number).
The graph is expressed as N by N adjacency matrix. N is the number of vertices in the graph, i.e., "nodes_number". "source","sink" are identified by the node ID. "capacity" is an N by N matrix express the edge capacity. "max_flow" is output max flow found.

[moujaprim]

SALUT,

mais si je commence par la fonction ff_max_flow voila l'erreur que me donne aussi :

Code :

max_flow=ff_max_flow(1,5,37,6)

Code :

1
2
3
4
5
6
7
??? Index exceeds matrix dimensions.

Error in ==> C:\MATLAB6p5\toolbox\grtheorie\bfs_augmentpath.m
On line 42  ==>                 if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )

Error in ==> C:\MATLAB6p5\toolbox\grtheorie\ff_max_flow.m
On line 9  ==> augmentpath = bfs_augmentpath(source,sink,current_flow,capacity,nodes_number);

ca veut dire que il ya un probleme au niveau de la ligne 42 !!
merci infinment .

[moujaprim]

voila la 1 er fonction :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function max_flow=ff_max_flow(source,sink,capacity,nodes_number)


current_flow=zeros(nodes_number,nodes_number);

max_flow=0;

augmentpath = bfs_augmentpath(source,sink,current_flow,capacity,nodes_number);

     %bfs_augmentpath(2,6,current_flow,capacity,6)

while ~isempty(augmentpath)
    
    % if there exits a augment path, update teh current_flow    
    increment = inf;
    for i=1:length(augmentpath)-1
        increment=min(increment, capacity(augmentpath(i),augmentpath(i+1))-current_flow(augmentpath(i),augmentpath(i+1)));
    end
    
    %now increase the current_flow
    
    for i=1:length(augmentpath)-1
        current_flow(augmentpath(i),augmentpath(i+1))=current_flow(augmentpath(i),augmentpath(i+1))+increment;
        current_flow(augmentpath(i+1),augmentpath(i))=current_flow(augmentpath(i+1),augmentpath(i))-increment;
    end
    max_flow=max_flow+increment;
    augmentpath = bfs_augmentpath(source,sink,current_flow,capacity,nodes_number);% try to find new augment path    

end

voila la 2ème fonction :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
%WHITE =0;
%GRAY=1;
%BLACK=2

function augmentpath=bfs_augmentpath(start,target,current_flow,capacity,n)
    n=10;
    WHITE =0;
    GRAY=1;
    BLACK=2;
    color(1:n)=WHITE;
    head=1;
    tail=1;
    q=[];
    augmentpath=[ ];
    start=2;
    bInf = 0.5 ;
    bSup = 5 ;
    M    =    10 ;
    N    =    10 ;
    
    capacity = bInf + (bSup-bInf).*rand(M, N);
    
    %ENQUEUE
    
    q=[start q];
    
    color(start)=GRAY;
    
    pred(start) = -1;
    
    pred=zeros(1,n);
    
    while ~isempty (q) 
      %  [u,q]=dequeue(q);
            u=q(end);
            q(end)=[];
            color(u)=BLACK;
    %     dequeue end here
            
            for v=1:n
                if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )
    %enqueue(v,q)
                    q=[v q];
                    color(v)=GRAY;
    % enqueue end here
                    pred(v)=u;                        

                end
            end
    end
    
    if color(target)==BLACK       %if target is accessible
       temp=target;
       while pred(temp)~=start
        augmentpath = [pred(temp) augmentpath];     %augment path doesnt containt the start point AND target point
        temp=pred(temp);
       end
       augmentpath=[start augmentpath target];
    else
        augmentpath=[];         % default resulte is empty
    end

moi je suis un peu nul en info donc :
Svp je vous demande de me donner les commandes que je vais taper sur MATLAB en ordre prioritaire. merci

[najibaff]

Moi non plus je n'arrive pas à trouver une solution pour ce code, comment l'empiler ?

??? Index exceeds matrix dimensions.

Error in ==> C:\MATLAB6p5\toolbox\grtheorie\bfs_augmentpath.m
On line 42  ==>                 if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )

il y a un problème au niveau de la ligne 42 ,il y a quelque chose qui ne va pas...

[magelan]

Il faut utiliser correctement la fonction ff_max_flow.

Envoyé par moujaprim

mais si je commence par la fonction ff_max_flow voila l'erreur que me donne aussi :

Code :

max_flow=ff_max_flow(1,5,37,6)

Envoyé par magelan

Dans tout les cas, je te suggère de bien relire la description :
Main function is function max_flow=ff_max_flow(source,sink,capacity,nodes_number).
The graph is expressed as N by N adjacency matrix. N is the number of vertices in the graph, i.e., "nodes_number". "source","sink" are identified by the node ID. "capacity" is an N by N matrix express the edge capacity. "max_flow" is output max flow found.

Dans ton cas tu mets nodes_number=6 donc N=6, donc capacity doit être une matrice de taille 6 lignes par 6 colonnes.

[moujaprim]

voila j'ai crée ma matrice d'adjacence a . et voila ce qu'il me donne encore comme erreur ?

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
a

a =

     0     1     0     1     0     1
     0     0     0     0     0     0
     0     1     0     0     1     0
     0     0     0     0     1     1
     0     0     0     0     0     0
     0     0     1     0     0     0

>> max_flow=ff_max_flow(1,5,a,6)
??? Index exceeds matrix dimensions.

Error in ==> C:\MATLAB6p5\toolbox\grtheorie\bfs_augmentpath.m
On line 43  ==>                 if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )

Error in ==> C:\MATLAB6p5\toolbox\grtheorie\ff_max_flow.m
On line 10  ==> augmentpath = bfs_augmentpath(source,sink,current_flow,capacity,nodes_number);

donc je crois que le problème il est dans la ligne 43 cette boucle for ca marche po ! svp essayez lire un peu avec moi cet algorithme et précisément la ligne 43, peut être que ya qlq chose qui manque

[magelan]

La fonction bfs_augmentpath que tu utilises contient effectivement des erreurs. Télécharge les fichiers d'origines sur le lien suivant :
http://www.mathworks.com/matlabcentr...rson-algorithm
et copie les fichiers dans ton répertoire grtheorie

[moujaprim]

MERCIIIIIIIIIIIIIIIIIIIIIIIIII bcp c tres gentil de ta part ,

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
E=[1 2 4 1;1 3 2 2;2 3 2 1;3 2 1 6;3 4 3 3;2 4 1 5;2 5 2 6;4 5 5 5];
>> a=[0 4 2 0 0 ; 0 0 2 1 2;0 1 0 3 0; 0 0 0 0 5;0 0 0 0 0]

a =

     0     4     2     0     0
     0     0     2     1     2
     0     1     0     3     0
     0     0     0     0     5
     0     0     0     0     0

>> max_flow=ff_max_flow(1,5,a,5)

max_flow =

     6

j'ai reussie à trouver le flow max, maintenant si je veut par exemple qu'il me donne les détails ca veut dire , que chaque arc combien d'amélioration qu'il va avoir et qu'ils sont les changements qu'il va subir ? merciii encore une 2eme fois

[moujaprim]

par ce qu j'ai constaté aussi que cet fonction ne prend pas en consediration les flot declarer, est ce que je vais les declarer aussi comme matrice au bien . merci infiniment

[najibaff]

oui enfin moi aussi ça marche sur mon programme mais il me reste de savoir le flux optimal de chaque arc après l'amélioration .

merci M. moujaprim
mercii M. magelan

[moujaprim]

bonjour,


svp est ce qu'il ya qlq 1 qui a une idée sur l'obtention de chemin optimal dans un graphe, et quel sont les lot quand va ajouté a chaque arc lors d'amélioration merci