title: Is this Sedgewick code correct?
body: <p>I am solving an optimization problem in which, among other things, I must maximize flow networks. I implemented a c++ code based flow-maximization algorithm based in the following <strong>java code</strong> that appears in the book of Sedgewick "Algorithms in Java, Third Edition, Part 5: Graph Algorithms", which maximizes a network flow using a vertex-based PREFLOW-push algorithm:</p>
  
  <pre><code>class NetworkMaxFlow
  { private Network G; private int s, t;
    private int[] h, wt;
    private void initheights()
    NetworkMaxFlow(Network G, int s, int t)
    { this.G = G; this.s = s; this.t = t;
      wt = new int[G.V()]; h = new int[G.V()];
      initheights();
      intGQ gQ = new intGQ(G.V());
      gQ.put(s); wt[t] = -(wt[s] = Edge.M*G.V());
      while (!gQ.empty())
      { int v = gQ.get();
        AdjList A = G.getAdjList(v);
        for (Edge e = A.beg(); !A.end(); e = A.nxt())
          { int w = e.other(v), cap = e.capRto(w);
            int P = cap &lt; wt[v] ? cap : wt[v];
            if (P &gt; 0 &amp;&amp; v == s || h[v] == h[w]+1) // first observation (see below)
              { e.addflowRto(w, P);
                wt[v] -= P; wt[w] += P;
                if ((w != s) &amp;&amp; (w != t)) gQ.put(w); // enqueue w if it is not source or sink
              }
          }
        if (v != s &amp;&amp; v != t &amp;&amp; wt[v] &gt; 0) // why check v != t if t never enter the queue?
          { h[v]++; gQ.put(v); }
      }
    }
  }
  </code></pre>
  
  <p>My implementation, based on that code, fails to maximize the following network
  <img src="https://i.stack.imgur.com/KkDF5.png" alt="Capacitated network; all flows are in zero">
  After execution, the the resulting flow is as follows
  <img src="https://i.stack.imgur.com/75tuA.png" alt="Final state for the previous net">
  With this flow, the flow value is 8, but the maximum is 9, as indicated by the flow of the figure below
  <img src="https://i.stack.imgur.com/TgZn6.png" alt="A maximum flow">
  According to my understanding, the algorithm is consistent with the explanation of the book. However, I see two strange things</p>
  
  <ol>
  <li>There is no explicit preflow phase from source. It is included in the <code>while</code> and executed first and only once when the predicate <code>P &gt; 0 &amp;&amp; v == s</code> is true. Maybe this was done to shorten the code</li>
  <li>According to my understanding, and discourse of the book, the sink never enters the queue. However, when the height is increased, the code checks that v != t. Any reason for this?</li>
  </ol>
  
  <p>This is an excerpt from my implementation of this algorithm in C++</p>
  
  <pre><code>template &lt;class Net, class Q_Type&gt; typename Net::Flow_Type
  generic_preflow_vertex_push_maximum_flow(Net &amp; net)
  {
    init_height_in_nodes(net); // breadth first traverse from sink to
                   // source. Nodes are labeled with their
                   // minimal distance (in nodes) to sink
    auto source = net.get_source();
    auto sink   = net.get_sink();
  
    using Itor = __Net_Iterator&lt;Net&gt;;
    Q_Type q; // generic queue (can be fifo, heap or random) of active nodes
  
    // preflow: floods all nodes connected to the source 
    for (Itor it(source); it.has_curr(); it.next()) 
      {
        auto arc  = it.get_curr();  
        arc-&gt;flow = arc-&gt;cap; // saturate arc to its maximum 
        auto tgt = net.get_tgt_node(arc);
        put_in_active_queue(q, tgt);
        assert(node_height&lt;Net&gt;(source) == node_height&lt;Net&gt;(tgt) + 1);
        assert(not is_residual&lt;Net&gt;(source, arc));
      }
  
    while (not q.is_empty()) // while there are active nodes
      {
        auto src = get_from_active_queue(q);
        auto excess = net.get_in_flow(src) - net.get_out_flow(src);
  
        for (Itor it(src); it.has_curr(); it.next()) 
          {
            auto arc = it.get_curr();
            auto tgt = net.get_connected_node(arc, src);
  
            if (node_height&lt;Net&gt;(src) != node_height&lt;Net&gt;(tgt) + 1)
              continue; // this arc is not eligible
  
            typename Net::Flow_Type flow_to_push;
            if (is_residual&lt;Net&gt;(src, arc))
              {
                flow_to_push = std::min(arc-&gt;flow, excess);
                arc-&gt;flow -= flow_to_push;
              }
            else
              {
                flow_to_push = std::min(arc-&gt;cap - arc-&gt;flow, excess);
                arc-&gt;flow += flow_to_push;
              }
  
            excess -= flow_to_push;
            if (tgt != sink and tgt != source)
              put_in_active_queue(q, tgt);
          }
  
      if (excess &gt; 0) // src still active?
        { 
          node_height&lt;Net&gt;(src)++;
          put_in_active_queue(q, src);
        }
    }
  
    return net.flow_value(); // sum of all outing flow from source
  }
  </code></pre>
  
  <p>¿Someone find any logical inconsistency between my code and the code of Sedgewick? I have the impression that my code (and perhaps also the Sedgewick) is not properly handling the increases in heights. But I do not manage to understand why</p>
  
  <p>I show a detailed execution trace with the network that fails to maximize (the trace start from the first q.get() of while. The values in parentheses are the values of the heights. IN is the incoming flow to the node. OUT the outcoming one.</p>
  
  <p>As example, the line</p>
  
  <pre><code>    4104 (2) --&gt; 0 (1) pushing 1 from 4104 toward 0
  </code></pre>
  
  <p>refers the eligible arc 4104-->0. The node 4104 has height 2 and the node 0 has height 1. The expression "pushing 1" means that 1 unity of flow is pushed toward the target node (0). The line <code>================</code> separates each queue extraction. The queue is FIFO and its state is printed at the end of each processing.</p>
  
  <p>Note that many times zero flow units are pushed or reduceed, but the destination node becomes active.</p>
  
  <p>This is the execution trace</p>
  
  <pre><code>Initial Queue = 4104 4105 4106 4107 4108
  
  Active node 4104 Height = 2 IN = 1 OUT = 0
      4104 (2) --&gt; source (3) not eligible
      4104 (2) --&gt; 0 (1) pushing 1 from 4104 toward 0
      4104 (2) --&gt; 1 (1) pushing 0 from 4104 toward 1
      4104 (2) --&gt; 2 (1) pushing 0 from 4104 toward 2
      4104 (2) --&gt; 4 (1) pushing 0 from 4104 toward 4
      Excess = 0
      Queue = 4105 4106 4107 4108 0 1 2 4
  ================
  Active node 4105 Height = 2 IN = 3 OUT = 0
      4105 (2) --&gt; source (3) not eligible
      4105 (2) --&gt; 1 (1) pushing 1 from 4105 toward 1
      4105 (2) --&gt; 4 (1) pushing 1 from 4105 toward 4
      4105 (2) --&gt; 6 (1) pushing 1 from 4105 toward 6
      Excess = 0
      Queue = 4106 4107 4108 0 1 2 4 6
  ================
  Active node 4106 Height = 2 IN = 1 OUT = 0
      4106 (2) --&gt; source (3) not eligible
      4106 (2) --&gt; 1 (1) pushing 1 from 4106 toward 1
      4106 (2) --&gt; 5 (1) pushing 0 from 4106 toward 5
      Excess = 0
      Queue = 4107 4108 0 1 2 4 6 5
  ================
  Active node 4107 Height = 2 IN = 1 OUT = 0
      4107 (2) --&gt; source (3) not eligible
      4107 (2) --&gt; 1 (1) pushing 1 from 4107 toward 1
      4107 (2) --&gt; 2 (1) pushing 0 from 4107 toward 2
      4107 (2) --&gt; 3 (1) pushing 0 from 4107 toward 3
      4107 (2) --&gt; 4 (1) pushing 0 from 4107 toward 4
      4107 (2) --&gt; 6 (1) pushing 0 from 4107 toward 6
      Excess = 0
      Queue = 4108 0 1 2 4 6 5 3
  ================
  Active node 4108 Height = 2 IN = 3 OUT = 0
      4108 (2) --&gt; source (3) not eligible
      4108 (2) --&gt; 1 (1) pushing 1 from 4108 toward 1
      4108 (2) --&gt; 2 (1) pushing 1 from 4108 toward 2
      4108 (2) --&gt; 4 (1) pushing 1 from 4108 toward 4
      4108 (2) --&gt; 5 (1) pushing 0 from 4108 toward 5
      4108 (2) --&gt; 6 (1) pushing 0 from 4108 toward 6
      Excess = 0
      Queue = 0 1 2 4 6 5 3
  ================
  Active node 0 Height = 1 IN = 1 OUT = 0
      0 (1) --&gt; sink (0) pushing 1 from 0 toward sink
      0 (1) --&gt; 4104 (2) not eligible
      Excess = 0
      Queue = 1 2 4 6 5 3
  ================
  Active node 1 Height = 1 IN = 4 OUT = 0
      1 (1) --&gt; sink (0) pushing 2 from 1 toward sink
      1 (1) --&gt; 4105 (2) not eligible
      1 (1) --&gt; 4106 (2) not eligible
      1 (1) --&gt; 4107 (2) not eligible
      1 (1) --&gt; 4108 (2) not eligible
      Excess = 2    1 goes back onto queue with label 2
      Queue = 2 4 6 5 3 1
  ================
  Active node 2 Height = 1 IN = 1 OUT = 0
      2 (1) --&gt; sink (0) pushing 1 from 2 toward sink
      2 (1) --&gt; 4108 (2) not eligible
      Excess = 0
      Queue = 4 6 5 3 1
  ================
  Active node 4 Height = 1 IN = 2 OUT = 0
      4 (1) --&gt; sink (0) pushing 2 from 4 toward sink
      4 (1) --&gt; 4105 (2) not eligible
      4 (1) --&gt; 4108 (2) not eligible
      Excess = 0
      Queue = 6 5 3 1
  ================
  Active node 6 Height = 1 IN = 1 OUT = 0
      6 (1) --&gt; sink (0) pushing 1 from 6 toward sink
      6 (1) --&gt; 4105 (2) not eligible
      Excess = 0
      Queue = 5 3 1
  ================
  Active node 5 Height = 1 IN = 0 OUT = 0
      5 (1) --&gt; sink (0) pushing 0 from 5 toward sink
      Excess = 0
      Queue = 3 1
  ================
  Active node 3 Height = 1 IN = 0 OUT = 0
      3 (1) --&gt; sink (0) pushing 0 from 3 toward sink
      Excess = 0
      Queue = 1
  ================
  Active node 1 Height = 2 IN = 4 OUT = 2
      1 (2) --&gt; 4105 (2) not eligible
      1 (2) --&gt; 4106 (2) not eligible
      1 (2) --&gt; 4107 (2) not eligible
      1 (2) --&gt; 4108 (2) not eligible
      Excess = 2    1 goes back onto queue with label 3
      Queue = 1
  ================
  Active node 1 Height = 3 IN = 4 OUT = 2
      1 (3) --&gt; 4105 (2) Reducing 1 from 1 toward 4105
      1 (3) --&gt; 4106 (2) Reducing 1 from 1 toward 4106
      1 (3) --&gt; 4107 (2) Reducing 0 from 1 toward 4107
      1 (3) --&gt; 4108 (2) Reducing 0 from 1 toward 4108
      Excess = 0
      Queue = 4105 4106 4107 4108
  ================
  Active node 4105 Height = 2 IN = 3 OUT = 2
      4105 (2) --&gt; source (3) not eligible
      4105 (2) --&gt; 1 (3) not eligible
      Excess = 1    4105 goes back onto queue with label 3
      Queue = 4106 4107 4108 4105
  ================
  Active node 4106 Height = 2 IN = 1 OUT = 0
      4106 (2) --&gt; source (3) not eligible
      4106 (2) --&gt; 1 (3) not eligible
      4106 (2) --&gt; 5 (1) pushing 1 from 4106 toward 5
      Excess = 0
      Queue = 4107 4108 4105 5
  ================
  Active node 4107 Height = 2 IN = 1 OUT = 1
      4107 (2) --&gt; source (3) not eligible
      4107 (2) --&gt; 2 (1) pushing 0 from 4107 toward 2
      4107 (2) --&gt; 3 (1) pushing 0 from 4107 toward 3
      4107 (2) --&gt; 4 (1) pushing 0 from 4107 toward 4
      4107 (2) --&gt; 6 (1) pushing 0 from 4107 toward 6
      Excess = 0
      Queue = 4108 4105 5 2 3 4 6
  ================
  Active node 4108 Height = 2 IN = 3 OUT = 3
      4108 (2) --&gt; source (3) not eligible
      4108 (2) --&gt; 5 (1) pushing 0 from 4108 toward 5
      4108 (2) --&gt; 6 (1) pushing 0 from 4108 toward 6
      Excess = 0
      Queue = 4105 5 2 3 4 6
  ================
  Active node 4105 Height = 3 IN = 3 OUT = 2
      4105 (3) --&gt; source (3) not eligible
      4105 (3) --&gt; 1 (3) not eligible
      Excess = 1    4105 goes back onto queue with label 4
      Queue = 5 2 3 4 6 4105
  ================
  Active node 5 Height = 1 IN = 1 OUT = 0
      5 (1) --&gt; sink (0) pushing 1 from 5 toward sink
      5 (1) --&gt; 4106 (2) not eligible
      Excess = 0
      Queue = 2 3 4 6 4105
  ================
  Active node 2 Height = 1 IN = 1 OUT = 1
      2 (1) --&gt; sink (0) pushing 0 from 2 toward sink
      2 (1) --&gt; 4108 (2) not eligible
      Excess = 0
      Queue = 3 4 6 4105
  ================
  Active node 3 Height = 1 IN = 0 OUT = 0
      3 (1) --&gt; sink (0) pushing 0 from 3 toward sink
      Excess = 0
      Queue = 4 6 4105
  ================
  Active node 4 Height = 1 IN = 2 OUT = 2
      4 (1) --&gt; 4105 (4) not eligible
      4 (1) --&gt; 4108 (2) not eligible
      Excess = 0
      Queue = 6 4105
  ================
  Active node 6 Height = 1 IN = 1 OUT = 1
      6 (1) --&gt; sink (0) pushing 0 from 6 toward sink
      6 (1) --&gt; 4105 (4) not eligible
      Excess = 0
      Queue = 4105
  ================
  Active node 4105 Height = 4 IN = 3 OUT = 2
      4105 (4) --&gt; source (3) Reducing 1 from 4105 toward source
      4105 (4) --&gt; 1 (3) pushing 0 from 4105 toward 1
      Excess = 0
      Queue = 1
  ================
  Active node 1 Height = 3 IN = 2 OUT = 2
      1 (3) --&gt; 4107 (2) Reducing 0 from 1 toward 4107
      1 (3) --&gt; 4108 (2) Reducing 0 from 1 toward 4108
      Excess = 0
      Queue = 4107 4108
  ================
  Active node 4107 Height = 2 IN = 1 OUT = 1
      4107 (2) --&gt; source (3) not eligible
      4107 (2) --&gt; 2 (1) pushing 0 from 4107 toward 2
      4107 (2) --&gt; 3 (1) pushing 0 from 4107 toward 3
      4107 (2) --&gt; 4 (1) pushing 0 from 4107 toward 4
      4107 (2) --&gt; 6 (1) pushing 0 from 4107 toward 6
      Excess = 0
      Queue = 4108 2 3 4 6
  ================
  Active node 4108 Height = 2 IN = 3 OUT = 3
      4108 (2) --&gt; source (3) not eligible
      4108 (2) --&gt; 5 (1) pushing 0 from 4108 toward 5
      4108 (2) --&gt; 6 (1) pushing 0 from 4108 toward 6
      Excess = 0
      Queue = 2 3 4 6 5
  ================
  Active node 2 Height = 1 IN = 1 OUT = 1
      2 (1) --&gt; sink (0) pushing 0 from 2 toward sink
      2 (1) --&gt; 4108 (2) not eligible
      Excess = 0
      Queue = 3 4 6 5
  ================
  Active node 3 Height = 1 IN = 0 OUT = 0
      3 (1) --&gt; sink (0) pushing 0 from 3 toward sink
      Excess = 0
      Queue = 4 6 5
  ================
  Active node 4 Height = 1 IN = 2 OUT = 2
      4 (1) --&gt; 4105 (4) not eligible
      4 (1) --&gt; 4108 (2) not eligible
      Excess = 0
      Queue = 6 5
  ================
  Active node 6 Height = 1 IN = 1 OUT = 1
      6 (1) --&gt; sink (0) pushing 0 from 6 toward sink
      6 (1) --&gt; 4105 (4) not eligible
      Excess = 0
      Queue = 5
  ================
  Active node 5 Height = 1 IN = 1 OUT = 1
      5 (1) --&gt; sink (0) pushing 0 from 5 toward sink
      5 (1) --&gt; 4106 (2) not eligible
      Excess = 0
      Queue =
  </code></pre>