#Copyright (c) 2005 EPFL/Switzernet/Intarnet by Emin Gabrielyan

reset;

commands config.txt;

option randseed (randseed);

option presolve 1;


set NODES = 1..N;
param source_node in NODES, =1;
param sink_node in NODES, != source_node, =int(N/2)+1;

param flow_out{1..T,NODES} default 0;
param flow_out_incr{1..T,NODES} default 0;
param flow_out_bottl{1..T,NODES} default 0;

set LINKS{1..T} dimen 2 within NODES cross NODES;
set INITLINKS{1..T} dimen 2;


set FRAMES within 1..T default 1..T;
set FRAMES_quit;
set FRAMES_true;

var F{1..T}>=0;

set Core{1..T} dimen 2;
set Core_clean{1..T} dimen 2;
param eps = 1e-10;

minimize Cost;

node Node{t in FRAMES, i in NODES}: net_out = F[t]*flow_out[t,i];

arc Link{t in FRAMES, (i,j) in LINKS[t]} >=0, <=1,
  from Node[t,i], to Node[t,j],
  obj Cost if (i,j) in Core[t] then 1;


maximize Flow:
  sum{t in FRAMES} F[t];

param xxx;
param yyy;
param xx{NODES};
param yy{NODES};
param x{1..T,NODES};
param y{1..T,NODES};
param a{NODES} default Uniform(0,2*PI);

commands randomwalk.txt;

for{t in 1..T} let INITLINKS[t] := LINKS[t];

param layers{1..T} default 0;
param flow_outs{t in 1..T,0..layers[t],NODES} default 0;
param pump{t in 1..T, 1..layers[t]};

set PATH_mincost{1..T} dimen 2;
param load_mincost{t in 1..T, (i,j) in INITLINKS[t]} >=0;
set BOTTLENECKS{t in 1..T, 1..layers[t]} dimen 2;
set PATH{t in 1..T, 1..layers[t]} dimen 2;
param load{t in 1..T, l in 1..layers[t], (i,j) in PATH[t,l]} >=0;
param maxload;
param counter;

for{t in 1..T, i in NODES: (if i==source_node then 1)+(if i==sink_node then -1) != 0}
{
  let flow_out[t,i] := (if i==source_node then 1) + (if i==sink_node then -1);
  let flow_outs[t,0,i] := flow_out[t,i];
}

printf "\nlayering:\n" > (log);
for{l in 1..200}
{
  printf "\n  layer %d:\n",l > (log);
  printf "    %-8s %d\n","frames",card(FRAMES) > (log);

  for{t in FRAMES} unfix F[t];
  for{t in FRAMES} let Core[t] := {};
  objective Flow;
  commands solve.txt;
  printf "    %-8s %f\n","max-flow",Flow > (log);
  
  for{t in FRAMES} fix F[t];

  for{t in FRAMES} let layers[t]:=layers[t]+1;

  display setof {t in FRAMES} (t,round(F[t],5));

  for{t in FRAMES} let pump[t,layers[t]] := F[t];

  let FRAMES_quit := {t in FRAMES: not F[t]};

  # Emptying all parameters for frames with no flow
  if FRAMES_quit not within {}
    then
    {
      print "Frames with no flow:";
      display FRAMES_quit;
      printf "Emptying all parameters for these frames ... ";
      for{t in FRAMES_quit}
      {
        let PATH[t,layers[t]] := {};
        let BOTTLENECKS[t,layers[t]] := {};
        for{i in NODES: flow_out[t,i]!=0}
        {
          let flow_out[t,i] := 0;
          let flow_outs[t,layers[t],i] := flow_out[t,i];
        }
      }
      printf "Ok\n";
    }

  let FRAMES := FRAMES diff FRAMES_quit;

  if FRAMES within {}
    then
    {
      print "no frame has flow";
      break;
    }

  printf "Setting the cost objective for all links ... ";
  for{t in FRAMES} let Core[t] := LINKS[t];
  objective Cost;
  printf "Ok\n\n";

  printf "    hunting bottlenecks:\n" > (log);
  let FRAMES_true := FRAMES;
  for{hunt in 1..1000}
  {
    printf "      hunt %d:\n",hunt > (log);
    printf "        %-8s %d\n","frames",card(FRAMES) > (log);
    printf "        %-8s %d\n","core",sum{t in FRAMES} card(Core[t]) > (log);
    commands solve.txt;
    printf "        %-8s %f\n","min-cost",Cost > (log);
    if hunt==1 then
    {
      # min-cost solution for all FRAMES of the present layer
      for{t in FRAMES} let PATH_mincost[t] := {(i,j) in LINKS[t]: Link[t,i,j]>eps};
      for{t in FRAMES} for{(i,j) in PATH_mincost[t]} let load_mincost[t,i,j] := Link[t,i,j];

      for{t in FRAMES} let PATH[t,layers[t]] := PATH_mincost[t];
      for{t in FRAMES} for{(i,j) in PATH_mincost[t]} let load[t,layers[t],i,j] := load_mincost[t,i,j];
    }
    let FRAMES_quit := {}; #will be computed in cleancore
    commands cleancore.txt;
    display setof{t in FRAMES} (t,card(Core[t]));

    let FRAMES := FRAMES diff FRAMES_quit;
    display FRAMES_quit,FRAMES;
    if FRAMES within {}
      then
        break;
  };
  let FRAMES := FRAMES_true;
  
  let benchmark_start := _ampl_time;
  printf "    preparing the next layer:\n" > (log);
  printf "Preparing the next layer (5 steps):\n";

  printf "  (1) Increase of non-zero flow outs ... ";
  reset data flow_out_incr;
  for{t in FRAMES, i in NODES: abs(flow_out[t,i])>0}
  {
    let flow_out_incr[t,i] := if abs(flow_out[t,i]) <= eps then 0 else
      flow_out[t,i]*F[t];
  }
  printf "Ok\n";
  printf "      increased flow outs  %d\n",
    card({t in FRAMES, i in NODES: abs(flow_out_incr[t,i])>0}) > (log);
  
  printf "  (2) Removal of bottleneck links ... ";
  reset data flow_out_bottl;
  for{t in FRAMES}
  {
    for{(i,j) in Core[t]}
    {
      let LINKS[t] := LINKS[t] diff {(i,j)};
    }
    for{i in NODES}
    {
      let flow_out_bottl[t,i] :=
        sum{(j,i) in Core[t]} 1 - sum{(i,j) in Core[t]} 1;
    }
  }
  reset data flow_out;
  for{t in FRAMES, i in NODES} let flow_out[t,i] :=
    flow_out_incr[t,i] + flow_out_bottl[t,i];
  printf "Ok\n";
  printf "      removed bottlenecks  %d\n",
    card({t in FRAMES, Core[t]}) > (log);

  printf "  (3) Zeroing negligible flow: ";
  let counter:=0;
  for{t in FRAMES, i in NODES: 0<abs(flow_out[t,i])<=eps}
  {
    let flow_out[t,i] := 0;
    printf ".";
    let counter:=counter+1;
  }
  printf " Ok\n";
  printf "      zeroed flow outs     %d\n",counter > (log);

  # Calibration
  printf "  (4) Calibration ... ";
  for{t in FRAMES} let PATH_mincost[t] := PATH_mincost[t] diff Core[t];
  reset data flow_out_incr;
  let counter:=0;
  for{t in FRAMES, i in NODES: abs(flow_out[t,i])>0}
  {
    let flow_out_incr[t,i] :=
      sum{(i,j) in PATH_mincost[t]} load_mincost[t,i,j] -
      sum{(j,i) in PATH_mincost[t]} load_mincost[t,j,i];
    let counter:=counter+1;
  }
  reset data flow_out;
  for{t in FRAMES, i in NODES: abs(flow_out_incr[t,i])>0}
    let flow_out[t,i] := flow_out_incr[t,i];
  printf "Ok\n";
  printf "      calibrated flow outs %d\n",counter > (log);

  printf "  (5) Zeroing negligible flow: ";
  let counter:=0;
  for{t in FRAMES, i in NODES: 0<abs(flow_out[t,i])<=eps}
  {
    let flow_out[t,i] := 0;
    printf ".";
    let counter:=counter+1;
  }
  printf " Ok\n";
  printf "      zeroed flow outs     %d\n",counter > (log);

  for{t in FRAMES, i in NODES: flow_out[t,i] != 0}
    let flow_outs[t,layers[t],i] := flow_out[t,i];

  for{t in FRAMES} let BOTTLENECKS[t,layers[t]] := Core[t];

  let benchmark_stop := _ampl_time;
  printf "Done in %f seconds\n\n",benchmark_stop - benchmark_start;
  printf "      all done in (sec)    %f\n",benchmark_stop - benchmark_start > (log);

  display setof{t in FRAMES} (t,card(BOTTLENECKS[t,layers[t]]));

  let FRAMES_quit := {t in FRAMES: {i in NODES: abs(flow_out[t,i])>eps} within {}};

  for{t in FRAMES_quit}
  {
    fix F[t] := 0;
    let Core[t] := {};
  }

  let FRAMES := FRAMES diff FRAMES_quit;
  
  if FRAMES within {}
    then
    {
      print "all explored";
      break;
    }

}
printf "\nlayering completed.\n" > (log);
close (log);


set All_solve_results := setof{i in 1..solve_n} solve_results[i];
display _ampl_time, _total_solve_time;
display solve_n;
display All_solve_results;
display N,T;
display max{t in 1..T} layers[t];

let file := "speedup.csv";
if num(sub(ctime(),"^.* [0-9]+:[0-9]+:([0-9]+) .*$","\1")) mod 5 == 0 then
  print "time,ampl_time,total_solve_time," &
         "solve_n,solved,N,T,max layers,randseed" >> (file);
printf "%s,%.5f,%.5f,%d,%s,%d,%d,%d,%d\n", sub(ctime(),"^[^ ]* ",""),
  _ampl_time, _total_solve_time,
  solve_n,if All_solve_results symdiff {"solved"} within {} then "ok" else "error",
  N, T, max{t in 1..T} layers[t], randseed >> (file);
close (file);


shell "rmdir /s /q dump";
shell "mkdir dump";
shell "del /q dump\*";
shell "copy config.txt dump";
shell "copy solvelog.csv dump";
shell "copy model.log dump";

let file := "dump/flow.txt";
display layers > (file);
display pump > (file);
display BOTTLENECKS > (file);
display flow_outs > (file);
close (file);

let file := "dump/path.txt";
printf "param T = %d;\n\n",T > (file);
printf "param N = %d;\n\n",N > (file);

print "param" > (file);
display layers > (file);

print "param" > (file);
display pump > (file);

display BOTTLENECKS > (file);

display PATH > (file);

display INITLINKS > (file);

print "param" > (file);
display load > (file);
close (file);


#end;

print "Drawing...";

param ps symbolic = "diagram/out.ps";
param layer;
param diagram_pos;

commands linkviews_load.txt;
commands diagram.txt;
commands slideshow.txt;