%%%%%%%%%%%%%%%%%%%%%%%
%maxflow_pref
%%%%%%%%%%%%%%%%%%%%%%%
%Preflow algorithm with highest distance label

%global variables:
%ACTIVE{d}---Active node LIST with distance d
%act_found----=1, find an active node;
%act_found----=0, if there is no active node, algorithm stops.

%dist_i --- d(i), where i is the current active node
%d(i)---- distance label
%e(i)---- exess flow 
%level---current position in ACTIVE
%ADMIS{i}----LIST of admissible arc from node i

clear;

data=[1  1 2 20
    2  1 3 15
    3  1 4 10
    4  2 4 4
    5  2 5 5
    6  2 6 9
    7  3 2 5
    8  3 6 6
    9  4 5 8
    10 5 6 25
    11 5 7 10
    12 6 5 5
    13 6 7 30];  % Forward-Star Representation of Fig. 7.22

T=data(:,2); 
H=data(:,3); 
UB=data(:,4); 

data=load('SpokaneFStarRep.txt');
T=data(:,1); 
H=data(:,2); 
UB=data(:,3); 



M=length(T); 
N=max(max(T), max(H)); 

s = input('give the source node  ');
t = input('give the sink node  ');  

netdata;

maxflow_pref_ini;

%d
%posT
%posH
%celldisp(ADMIS)


maxflow_pref_find_active;

iter=0;
while act_found==1 
   %i
   maxflow_pref_push_relab;
   iter=iter+1;
   %d
   %X
   %celldisp(ADMIS)
   
   maxflow_pref_find_active;
end %while
iter
disp('X = ');
disp([T(find(X > 0)) H(find(X>0)) X(find(X>0))]);
value=sum(X(A{s}))