// Check the interfaces

   // Read the test networks

   {

     typedef concepts::Digraph GR;

     checkConcept< McfClassConcept<GR, int, int>,

                   NetworkSimplex<GR> >();

     checkConcept< McfClassConcept<GR, double, double>,

                   NetworkSimplex<GR, double> >();

     checkConcept< McfClassConcept<GR, int, double>,

                   NetworkSimplex<GR, int, double> >();

   }

   // 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), l3(gr), u(gr);

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

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

   Node v, w;

   // Build test digraphs with negative costs

   std::istringstream neg_inp1(test_neg1_lgf);

   Digraph neg_gr;

   DigraphReader<Digraph>(neg1_gr, neg_inp1)

   Node n1 = neg_gr.addNode();

     .arcMap("cost", neg1_c)

   Node n2 = neg_gr.addNode();

     .arcMap("low1", neg1_l1)

   Node n3 = neg_gr.addNode();

     .arcMap("low2", neg1_l2)

   Node n4 = neg_gr.addNode();

     .nodeMap("sup", neg1_s)

   Node n5 = neg_gr.addNode();

     .run();

   Node n6 = neg_gr.addNode();

   Node n7 = neg_gr.addNode();

   std::istringstream neg_inp2(test_neg2_lgf);

   DigraphReader<Digraph>(neg2_gr, neg_inp2)

   Arc a1 = neg_gr.addArc(n1, n2);

     .arcMap("cost", neg2_c)

   Arc a2 = neg_gr.addArc(n1, n3);

     .nodeMap("sup", neg2_s)

   Arc a3 = neg_gr.addArc(n2, n4);

     .run();

   Arc a4 = neg_gr.addArc(n3, n4);

   Arc a5 = neg_gr.addArc(n3, n2);

   // Check the interface of NetworkSimplex

   Arc a6 = neg_gr.addArc(n5, n3);

   Arc a7 = neg_gr.addArc(n5, n6);

   Arc a8 = neg_gr.addArc(n6, n7);

   Arc a9 = neg_gr.addArc(n7, n5);

   Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);

   ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);

   Digraph::NodeMap<int> neg_s(neg_gr, 0);

   neg_l2[a7] =  1000;

   neg_l2[a8] = -1000;

   neg_s[n1] =  100;

   neg_s[n4] = -100;

   neg_c[a1] =  100;

   neg_c[a2] =   30;

   neg_c[a3] =   20;

   neg_c[a4] =   80;

   neg_c[a5] =   50;

   neg_c[a6] =   10;

   neg_c[a7] =   80;

   neg_c[a8] =   30;

   neg_c[a9] = -120;

   Digraph negs_gr;

   Digraph::NodeMap<int> negs_s(negs_gr);

   Digraph::ArcMap<int> negs_c(negs_gr);

   ConstMap<Arc, int> negs_l(0), negs_u(1000);

   n1 = negs_gr.addNode();

   n2 = negs_gr.addNode();

   negs_s[n1] = 100;

   negs_s[n2] = -300;

   negs_c[negs_gr.addArc(n1, n2)] = -1;

   // A. Test NetworkSimplex with the default pivot rule

     NetworkSimplex<Digraph> mcf(gr);

     typedef concepts::Digraph GR;

     checkConcept< McfClassConcept<GR, int, int>,

     // Check the equality form

                   NetworkSimplex<GR> >();

     mcf.upperMap(u).costMap(c);

     checkConcept< McfClassConcept<GR, double, double>,

     checkMcf(mcf, mcf.supplyMap(s1).run(),

                   NetworkSimplex<GR, double> >();

              gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");

     checkConcept< McfClassConcept<GR, int, double>,

     checkMcf(mcf, mcf.stSupply(v, w, 27).run(),

                   NetworkSimplex<GR, int, double> >();

              gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");

   }

     mcf.lowerMap(l2);

     checkMcf(mcf, mcf.supplyMap(s1).run(),

   // Test NetworkSimplex

              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");

   { 

     checkMcf(mcf, mcf.stSupply(v, w, 27).run(),

     typedef NetworkSimplex<Digraph> MCF;

              gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");

     runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);

     mcf.reset();

     runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");

     checkMcf(mcf, mcf.supplyMap(s1).run(),

     runMcfGeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE", true);

              gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");

     runMcfLeqTests<MCF>(MCF::BEST_ELIGIBLE,  "NS-BE");

     checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),

     runMcfGeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS", true);

              gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");

     runMcfLeqTests<MCF>(MCF::BLOCK_SEARCH,   "NS-BS");

     mcf.reset();

     runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);

     checkMcf(mcf, mcf.run(),

     runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");

              gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");

     runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);

     checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),

     runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");

              gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");

     mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);

     checkMcf(mcf, mcf.run(),

              gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");

     // Check the GEQ form

     mcf.reset().upperMap(u).costMap(c).supplyMap(s5);

     checkMcf(mcf, mcf.run(),

              gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);

     mcf.supplyType(mcf.GEQ);

     checkMcf(mcf, mcf.lowerMap(l2).run(),

              gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);

     mcf.supplyMap(s6);

     checkMcf(mcf, mcf.run(),

              gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);

     // Check the LEQ form

     mcf.reset().supplyType(mcf.LEQ);

     mcf.upperMap(u).costMap(c).supplyMap(s6);

     checkMcf(mcf, mcf.run(),

              gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);

     checkMcf(mcf, mcf.lowerMap(l2).run(),

              gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);

     mcf.supplyMap(s5);

     checkMcf(mcf, mcf.run(),

              gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);

     // Check negative costs

     NetworkSimplex<Digraph> neg_mcf(neg_gr);

     neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);

     checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,

       neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");

     neg_mcf.upperMap(neg_u2);

     checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,

       neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");

     neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);

     checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,

       neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");

     NetworkSimplex<Digraph> negs_mcf(negs_gr);

     negs_mcf.costMap(negs_c).supplyMap(negs_s);

     checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,

       negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);

   }

   // B. Test NetworkSimplex with each pivot rule

   {

     NetworkSimplex<Digraph> mcf(gr);

     mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);

     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),

              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");

     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),

              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");

     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),

              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");

     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),

              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");

     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),

              gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");