Discussion :

[camelia136]

bonjour,

j'ai 2 fonctions pour l'algorithme de Ford Fulkerson qui resout le problème des flots maximums

la première fonction qui est la fonction principale qui permet d'augmenter la capacité des segments

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

et la deuxième

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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    =    6 ;
    N    =    6 ;
 
    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

je compile en premier temps la 2em fonction car je l'utilise dans la seconde

et on me sort comme quoi il y'a erreur dans la ligne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )

[duf42]

Bonjour,

Serait-il possible de voir l'erreur que tu obtiens?

Duf

P.S. Qu'entends-tu par "compiler", si c'est pour exécuter dans MATLAB il n'y a pas de compilation puisque c'est un langage interprété.

[camelia136]

Bonjour,

Serait-il possible de voir l'erreur que tu obtiens?

Duf

P.S. Qu'entends-tu par "compiler", si c'est pour exécuter dans MATLAB il n'y a pas de compilation puisque c'est un langage interprété.

oui je veux dire exécuter

??? Attempted to access capacity(2,7); index out of bounds because size(capacity)=[6,6].

Error in ==> bfs_augmentpath at 42
                if (color(v)==WHITE && capacity(u,v)>current_flow(u,v) )

alors que capacité et current_flow sont définie de la même manière

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
    start=2;
    bInf = 0.5 ;
    bSup = 5 ;
    M    =    6 ;
    N    =    6 ;
 
    capacity = bInf + (bSup-bInf).*rand(M, N);
    current_flow= bInf + (bSup-bInf).*rand(M, N);

[duf42]

Oui mais tu essayes d'accéder à la 7ème colonne alors que ta matrice n'en contient que 6...

[camelia136]

Oui mais tu essayes d'accéder à la 7ème colonne alors que ta matrice n'en contient que 6...

je n'ai rien essayé , j'ai juste exécuté le programme

[Pienpien]

Peut être alors qu'il y a seulement une erreur dans le programme.

Maintenant tu peux aller essayer de voir pourquoi il y a cette erreur et essayer de la corriger pour l'application que tu veux en faire

[camelia136]

Peut être alors qu'il y a seulement une erreur dans le programme.

Maintenant tu peux aller essayer de voir pourquoi il y a cette erreur et essayer de la corriger pour l'application que tu veux en faire

l'erreur vient de cette ligne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

capacity(u,v)>current_flow(u,v)

ils disent que l'indice dépasse les dimensions de la matrice.

comment ça se fait alors que les 2 matrices sont de la même dimension

[oodbae_adriano]

tu as défini n=10 et M,N=6.

A la ligne 42, indiquée par le signal d'erreur, il y a une boucle for qui court de 1 à n=10 et qui lit la colonne i de matrices ayant 6 colonnes. Donc , comme l'a dit DUF, ton programme essaie d'accéder à une colonne inexistante. Error, error.

[camelia136]

tu as défini n=10 et M,N=6.

A la ligne 42, indiquée par le signal d'erreur, il y a une boucle for qui court de 1 à n=10 et qui lit la colonne i de matrices ayant 6 colonnes. Donc , comme l'a dit DUF, ton programme essaie d'accéder à une colonne inexistante. Error, error.

ah oui , j'ai pas fait attention à ça

merci bien