RhodeCode

        _supply[_node_id[_ptarget]] = -_pstflow;

      }

      if (!valid_supply) return false;

      // Infinite capacity value

      Flow inf_cap =

        std::numeric_limits<Flow>::has_infinity ?

        std::numeric_limits<Flow>::infinity() :

        std::numeric_limits<Flow>::max();

      // Initialize artifical cost

      Cost art_cost;

      if (std::numeric_limits<Cost>::is_exact) {

        art_cost = std::numeric_limits<Cost>::max() / 4 + 1;

      } else {

        art_cost = std::numeric_limits<Cost>::min();

        for (int i = 0; i != _arc_num; ++i) {

          if (_cost[i] > art_cost) art_cost = _cost[i];

        }

        art_cost = (art_cost + 1) * _node_num;

      }

      // Run Circulation to check if a feasible solution exists

      typedef ConstMap<Arc, Flow> ConstArcMap;

      FlowNodeMap *csup = NULL;

      bool local_csup = false;

      if (_psupply) {

        csup = _psupply;

      } else {

        csup = new FlowNodeMap(_graph, 0);

        (*csup)[_psource] =  _pstflow;

        (*csup)[_ptarget] = -_pstflow;

        local_csup = true;

      }

      bool circ_result = false;

      if (_ptype == GEQ || (_ptype == LEQ && sum_supply == 0)) {

        // GEQ problem type

        if (_plower) {

          if (_pupper) {

            Circulation<GR, FlowArcMap, FlowArcMap, FlowNodeMap>

              circ(_graph, *_plower, *_pupper, *csup);

            circ_result = circ.run();

          } else {

            Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>

            circ_result = circ.run();

          }

        } else {

          if (_pupper) {

            Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>

            circ_result = circ.run();

          } else {

            Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>

            circ_result = circ.run();

          }

        }

      } else {

        // LEQ problem type

        typedef ReverseDigraph<const GR> RevGraph;

        typedef NegMap<FlowNodeMap> NegNodeMap;

        RevGraph rgraph(_graph);

        NegNodeMap neg_csup(*csup);

        if (_plower) {

          if (_pupper) {

            Circulation<RevGraph, FlowArcMap, FlowArcMap, NegNodeMap>

              circ(rgraph, *_plower, *_pupper, neg_csup);

            circ_result = circ.run();

          } else {

            Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>

            circ_result = circ.run();

          }

        } else {

          if (_pupper) {

            Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>

            circ_result = circ.run();

          } else {

            Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>

            circ_result = circ.run();

          }

        }

      }

      if (local_csup) delete csup;

      if (!circ_result) return false;

      // Set data for the artificial root node

      _root = _node_num;

      _parent[_root] = -1;

      _pred[_root] = -1;

      _thread[_root] = 0;

      _rev_thread[0] = _root;

      _succ_num[_root] = all_node_num;

      _last_succ[_root] = _root - 1;

      _supply[_root] = -sum_supply;

      if (sum_supply < 0) {

        _pi[_root] = -art_cost;

      } else {

        _pi[_root] = art_cost;

      }

      // Store the arcs in a mixed order

      int k = std::max(int(std::sqrt(double(_arc_num))), 10);

void checkMcf( const MCF& mcf, bool mcf_result,

               const GR& gr, const LM& lower, const UM& upper,

               const CM& cost, const SM& supply,

               bool result, typename CM::Value total,

               const std::string &test_id = "",

               ProblemType type = EQ )

{

  check(mcf_result == result, "Wrong result " + test_id);

  if (result) {

    check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),

          "The flow is not feasible " + test_id);

    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);

    check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(),

                         mcf.potentialMap()),

          "Wrong potentials " + test_id);

  }

}

int main()

{

  // Check the interfaces

  {

    typedef int Flow;

    typedef int Cost;

    checkConcept< McfClassConcept<GR, Flow, Cost>,

                  NetworkSimplex<GR, Flow, Cost> >();

  }

  // Run various MCF tests

  typedef ListDigraph Digraph;

  DIGRAPH_TYPEDEFS(ListDigraph);

  // Read the test digraph

  Digraph gr;

  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);

  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);

  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());

  Node v, w;

  std::istringstream input(test_lgf);

  DigraphReader<Digraph>(gr, input)

    .arcMap("cost", c)

    .arcMap("cap", u)

    .arcMap("low1", l1)

    .arcMap("low2", l2)

    .nodeMap("sup1", s1)

    .nodeMap("sup2", s2)

    .nodeMap("sup3", s3)

template<class Value>

void solve_max(ArgParser &ap, std::istream &is, std::ostream &,

               Value infty, DimacsDescriptor &desc)

{

  bool report = !ap.given("q");

  Digraph g;

  Node s,t;

  Digraph::ArcMap<Value> cap(g);

  Timer ti;

  ti.restart();

  readDimacsMax(is, g, cap, s, t, infty, desc);

  if(report) std::cerr << "Read the file: " << ti << '\n';

  ti.restart();

  Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t);

  if(report) std::cerr << "Setup Preflow class: " << ti << '\n';

  ti.restart();

  pre.run();

  if(report) std::cerr << "Run Preflow: " << ti << '\n';

  if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n';  

}

template<class Value>

void solve_min(ArgParser &ap, std::istream &is, std::ostream &,

{

  bool report = !ap.given("q");

  Digraph g;

  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);

  Digraph::NodeMap<Value> sup(g);

  Timer ti;

  ti.restart();

  if (report) std::cerr << "Read the file: " << ti << '\n';

  ti.restart();

  NetworkSimplex<Digraph, Value> ns(g);

  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);

  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';

  ti.restart();

}

void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,

              DimacsDescriptor &desc)

{

  bool report = !ap.given("q");

  Graph g;

  Timer ti;

  ti.restart();

  readDimacsMat(is, g, desc);

  if(report) std::cerr << "Read the file: " << ti << '\n';

  ti.restart();

  MaxMatching<Graph> mat(g);

  if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n';

  ti.restart();

  mat.run();

  if(report) std::cerr << "Run MaxMatching: " << ti << '\n';

  if(report) std::cerr << "\nCardinality of max matching: "

                       << mat.matchingSize() << '\n';  

}

template<class Value>

void solve(ArgParser &ap, std::istream &is, std::ostream &os,

           DimacsDescriptor &desc)

{

  std::stringstream iss(static_cast<std::string>(ap["infcap"]));

  Value infty;

  iss >> infty;

  if(iss.fail())

    {

      std::cerr << "Cannot interpret '"

                << static_cast<std::string>(ap["infcap"]) << "' as infinite"

                << std::endl;

      exit(1);

    }

  switch(desc.type)

    {

    case DimacsDescriptor::MIN:

      break;

    case DimacsDescriptor::MAX:

      solve_max<Value>(ap,is,os,infty,desc);

      break;

    case DimacsDescriptor::SP:

      solve_sp<Value>(ap,is,os,desc);

      break;

    case DimacsDescriptor::MAT:

      solve_mat(ap,is,os,desc);

      break;

    default:

      break;

    }

}

int main(int argc, const char *argv[]) {

  typedef SmartDigraph Digraph;

  typedef Digraph::Arc Arc;

  std::string inputName;

  std::string outputName;

  ArgParser ap(argc, argv);