Is there an something wrong with the value being returned to this function in MATLAB resulting in an incorrect answer?

Question

My code below should return a max_flow value of 7 for the given network but it returns 2. I am certain my error is confined to generating the paths from s to t as I have re-wriiten the program in c++ which I have more experience in. I have also printed out my residual graph to see whats going on which is obviously also incorrect. There shouldn't be negative integers within it for one thing.

 0     0     0     0     0     0
 0     0     0     0     0     0
 0     0     0     0     0     0
 0     0     0     0    -2     2
 0     0     0     2     0     6
 0     0     0    -2    -6     0

I have also verified its 7 by hand. Inside my main function in c++ I have used while (int sent = dfs(s, t, INF)) as the condition for my while loop but in MATLAB I figured the equivalent was while sent == dfs(s,t,INF). I think that this could be the problem but I cant find an alternative and don't know where the hole in my logic is. I know that MATLAB has a built in maxlow function but I wanted to build my own as a learning experience. I am using a depth first search to find paths from source to sink in my residual graph Flow. I would appreciate any pointers to mending this and also anything else you think should/could be improved

    function ff
    clear;

%adjacency matrix representing capacities


    Cap =  [0, 4, 5, 0, 0, 0;
            0, 0, 2, 1, 4, 0;
            0, 0, 0, 0, 3, 0;
            0, 0, 0, 0, 0, 2;
            0, 0, 0, 2, 0, 6;
            0, 0, 0, 0, 0, 0;
                            ];




    len = length(Cap)

    Flow =zeros([len,len])
     
   
    
% source and sink
 INF=99999;
 s = 1; 
 t = 6; 
 max_flow=0;
 
 sent = 0;
 
 visited=boolean(zeros(1,len));
 
   sent = dfs(s,t,INF);

   while  sent == dfs(s,t,INF)
       
       max_flow =+ sent;

       visited=boolean(zeros(1,len));
      
   end
  
  disp('Residual graph:');
  disp(Flow);
  disp(['Max flow is ' num2str(max_flow)]);


%%dfs


    function F= dfs(Source,Sink,minimum)
      
       
      
     visited(Source) = true;
     
      
       if Source==Sink
          F = minimum;
        end 
 
       for  i = drange (2:length(visited))
            flow_cap = Cap(Source,i) - Flow(Source,i);
            
           

            if visited(i)==false && flow_cap > 0
                 visited(i) = true
             
            

                  if sent == dfs(i,Sink,min(minimum,flow_cap))
                     Flow(Source,i) =  Flow(Source,i)+sent;
                     Flow(i,Source) = Flow(i,Source)-sent ;
                     F=sent;
                  
                  end

          
           end

         F=sent;
         
        end
       
   end
  
end


 

Answer 1

As Ander Biguri said in a comment, sent == … doesn’t update sent like you do in C++. You cannot update a variable inside an expression (AFAIK). In MATLAB you’d update sent inside the loop.

Also, max_flow =+ sent is not the equivalent of max_flow += sent in C++. You are applying the unwary + to sent, which does nothing, then assigning the result to max_flow. That is, you are doing max_flow = +sent.

This would be a correct loop in MATLAB:

sent = dfs(s,t,INF);
while sent
   max_flow += sent;
   visited = zeros(1,len,'logical');
   sent = dfs(s,t,INF);
end

Finally, sharing visited with the dfs function is bad practice. You should try to use only local variables everywhere. You can pass the array into the function and then return it again, for example [sent,visited] = dfs(s,t,INF,visited).

Answer 2

I haven't checked your code, but why not simply use MATLAB's own maxflow function?

>> Cap =  [0, 4, 5, 0, 0, 0;
           0, 0, 2, 1, 4, 0;
           0, 0, 0, 0, 3, 0;
           0, 0, 0, 0, 0, 2;
           0, 0, 0, 2, 0, 6;
           0, 0, 0, 0, 0, 0;
                           ];
>> g = digraph(Cap)
g =
  digraph with properties:

    Edges: [9x2 table]
    Nodes: [6x0 table]
>> maxflow(g,1,6)
ans =
     7

This gives the answer 7 as you expected.