project/FordFulk/FordFulk/FordFulk.data

   1 do
   2   for Eij as all the edges
   3     mark Eij as candidate (green) if
   4       t(Eij)<c(E), or
   5       Eji exists and t(Eji)>0
   6   mark 'Source' as active
   7   while ('s'=first active node) and
   8         if this 's' is not 'Target' do
   9     for 't' as all the unmarked nodes
  10       if exists edge 'Est' and its a candidate one
  11         add 't' end of active nodes
  12         record 's' to 't' for backtrace
  13     mark node 's' as passed
  14   if 's' is empty (no 'Target' reachable)
  15     finish the algorithm
  16   clean the backtraces not on 't'->'s' path
  17   'd'=+infinity
  18   start at 's' and...
  19     while still backtracable for 'j' backwards to 'i' do
  20       if 'Eij' is a candidate
  21         'd'=min('d',c('Eij')-t('Eij'))
  22       if 'Eji' is a candidate
  23         'd'=min('d',t('Eji'))
  24   start at 's' and...
  25     while still backtracable for 'j' backwards to 'i' do
  26       if 'Eij' is a candidate
  27         t('Eij')+='d'
  28       if 'Eji' is a candidate
  29         t('Eji')-='d'
  30   network and variable cleanup (only 't()' remains)
  31   forever (until line 15 finishes)
  32 -
  33 0
  34 Algorithm is currently stopped. You may use the control buttons to clear the
  35 state and restart whole simulation.
  36 -
  37 1 31
  38 The cycle will run as long as there are some paths to improve.
  39 Exit check is done on the line 15.
  40 -
  41 2-3
  42 In this cycle we're marking the directions and edges which would
  43 be eventually usable during next processing...
  44 -
  45 4
  46 In forward direction such path must have some capacity left [t(E)<c(e)].
  47 -
  48 5
  49 In backward direction there must exist appropriate inverse edge and this one
  50 must have t(E)>0.
  51 -
  52 6-13
  53 We're searching any existing path from source 's' to the target 't'
  54 which uses only marked (green) edges in correctly marked directions.
  55 In fact it is a wide-search with recording of back-path into each node.
  56 After reaching the target we can track the recorded path back to the
  57 source 's'.
  58 -
  59 14-15
  60 If no target 't' was found that means that:
  61 |1) Target is separated completely from the source or
  62 |2) There's no (other) paths which can be
  63 improved and which are connecting the source and target nodes.
  64 -
  65 16
  66 A little tidy up to clear the diagram.
  67 -
  68 17-23
  69 We're trying to find maximum 'd' which is improvable on ALL the edges
  70 used in the path found. Such 'd' must be >0 as otherwise one of such
  71 edges wouldn't be marked on the algorithm lines 1-5.
  72 -
  73 24-29
  74 We have the final value of 'd' so we can now on all the same edges
  75 contained in the path found apply appropriate improvements.
  76 -
  77 30
  78 All the temporary variables and data structures are no longer needed and
  79 may be freed now. The only result from this one pass of algorithm is
  80 the improvement in values of function 't()'
  81 -
  82 -
  83 0 0 0 1 0 2 0 3
  84 1 0 1 1 1 2
  85             2 3
  86 -
  87 1 5 2
  88 5 4 3
  89 2 3 1
  90 4 7 5
  91 7 4 7
  92 7 2 1
  93 5 6 2
  94 5 0 4
  95 0 6 9
  96 -
  97 5 3
  98 -