RhodeCode

              _level->initAddItem(u);

              nqueue.push_back(u);

            }

          }

          for (OutArcIt e(_graph, n); e != INVALID; ++e) {

            Node v = _graph.target(e);

            if (!reached[v] && _tolerance.positive((*_flow)[e])) {

              reached[v] = true;

              _level->initAddItem(v);

              nqueue.push_back(v);

            }

          }

        }

        queue.swap(nqueue);

      }

      _level->initFinish();

      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {

        Value rem = (*_capacity)[e] - (*_flow)[e];

        if (_tolerance.positive(rem)) {

          Node u = _graph.target(e);

          if ((*_level)[u] == _level->maxLevel()) continue;

          _flow->set(e, (*_capacity)[e]);

          (*_excess)[u] += rem;

        }

      }

      for (InArcIt e(_graph, _source); e != INVALID; ++e) {

        Value rem = (*_flow)[e];

        if (_tolerance.positive(rem)) {

          Node v = _graph.source(e);

          if ((*_level)[v] == _level->maxLevel()) continue;

          _flow->set(e, 0);

          (*_excess)[v] += rem;

        }

      }

      return true;

    }

    /// \brief Starts the first phase of the preflow algorithm.

    ///

    /// The preflow algorithm consists of two phases, this method runs

    /// the first phase. After the first phase the maximum flow value

    /// and a minimum value cut can already be computed, although a

    /// maximum flow is not yet obtained. So after calling this method

    /// \ref flowValue() returns the value of a maximum flow and \ref

    /// minCut() returns a minimum cut.

    /// \pre One of the \ref init() functions must be called before

    /// using this function.

    void startFirstPhase() {

      _phase = true;

      while (true) {

        int num = _node_num;

        Node n = INVALID;

        int level = -1;

        while (num > 0) {

          n = _level->highestActive();

bool checkFlow(const SmartDigraph& g,

               const SmartDigraph::ArcMap<int>& flow,

               const SmartDigraph::ArcMap<int>& cap,

               SmartDigraph::Node s, SmartDigraph::Node t) {

  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {

    if (flow[e] < 0 || flow[e] > cap[e]) return false;

  }

  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {

    if (n == s || n == t) continue;

    int sum = 0;

    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {

      sum += flow[e];

    }

    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {

      sum -= flow[e];

    }

    if (sum != 0) return false;

  }

  return true;

}

int main() {

  typedef SmartDigraph Digraph;

  typedef Digraph::Node Node;

  typedef Digraph::NodeIt NodeIt;

  typedef Digraph::ArcIt ArcIt;

  typedef Digraph::ArcMap<int> CapMap;

  typedef Digraph::ArcMap<int> FlowMap;

  typedef Digraph::NodeMap<bool> CutMap;

  typedef Preflow<Digraph, CapMap> PType;

  Digraph g;

  Node s, t;

  CapMap cap(g);

  std::istringstream input(test_lgf);

  DigraphReader<Digraph>(g,input).

    arcMap("capacity", cap).

    node("source",s).

    node("target",t).

    run();

  PType preflow_test(g, cap, s, t);

  preflow_test.flowMap(flow);

  NodeIt tmp1(g,s);

  ++tmp1;

  if ( tmp1 != INVALID ) s=tmp1;

  NodeIt tmp2(g,t);

  ++tmp2;

  if ( tmp2 != INVALID ) t=tmp2;

  preflow_test.source(s);

  preflow_test.target(t);

  preflow_test.run();

  CutMap min_cut3(g);

  preflow_test.minCutMap(min_cut3);

  min_cut_value=cutValue(g,min_cut3,cap);

  check(preflow_test.flowValue() == min_cut_value,

        "The max flow value or the three min cut values are incorrect.");

  return 0;

}