test/min_cost_flow_test.cc
changeset 825 75e6020b19b1
parent 818 bc75ee2ad082
child 830 75c97c3786d6
equal deleted inserted replaced
10:3c01b296faed 11:3048b7fb1ec9
    22 
    22 
    23 #include <lemon/list_graph.h>
    23 #include <lemon/list_graph.h>
    24 #include <lemon/lgf_reader.h>
    24 #include <lemon/lgf_reader.h>
    25 
    25 
    26 #include <lemon/network_simplex.h>
    26 #include <lemon/network_simplex.h>
       
    27 #include <lemon/capacity_scaling.h>
       
    28 #include <lemon/cost_scaling.h>
       
    29 #include <lemon/cycle_canceling.h>
    27 
    30 
    28 #include <lemon/concepts/digraph.h>
    31 #include <lemon/concepts/digraph.h>
       
    32 #include <lemon/concepts/heap.h>
    29 #include <lemon/concept_check.h>
    33 #include <lemon/concept_check.h>
    30 
    34 
    31 #include "test_tools.h"
    35 #include "test_tools.h"
    32 
    36 
    33 using namespace lemon;
    37 using namespace lemon;
   455                   NetworkSimplex<GR, double> >();
   459                   NetworkSimplex<GR, double> >();
   456     checkConcept< McfClassConcept<GR, int, double>,
   460     checkConcept< McfClassConcept<GR, int, double>,
   457                   NetworkSimplex<GR, int, double> >();
   461                   NetworkSimplex<GR, int, double> >();
   458   }
   462   }
   459 
   463 
       
   464   // Check the interface of CapacityScaling
       
   465   {
       
   466     typedef concepts::Digraph GR;
       
   467     checkConcept< McfClassConcept<GR, int, int>,
       
   468                   CapacityScaling<GR> >();
       
   469     checkConcept< McfClassConcept<GR, double, double>,
       
   470                   CapacityScaling<GR, double> >();
       
   471     checkConcept< McfClassConcept<GR, int, double>,
       
   472                   CapacityScaling<GR, int, double> >();
       
   473     typedef CapacityScaling<GR>::
       
   474       SetHeap<concepts::Heap<int, RangeMap<int> > >::Create CAS;
       
   475     checkConcept< McfClassConcept<GR, int, int>, CAS >();
       
   476   }
       
   477 
       
   478   // Check the interface of CostScaling
       
   479   {
       
   480     typedef concepts::Digraph GR;
       
   481     checkConcept< McfClassConcept<GR, int, int>,
       
   482                   CostScaling<GR> >();
       
   483     checkConcept< McfClassConcept<GR, double, double>,
       
   484                   CostScaling<GR, double> >();
       
   485     checkConcept< McfClassConcept<GR, int, double>,
       
   486                   CostScaling<GR, int, double> >();
       
   487     typedef CostScaling<GR>::
       
   488       SetLargeCost<double>::Create COS;
       
   489     checkConcept< McfClassConcept<GR, int, int>, COS >();
       
   490   }
       
   491 
       
   492   // Check the interface of CycleCanceling
       
   493   {
       
   494     typedef concepts::Digraph GR;
       
   495     checkConcept< McfClassConcept<GR, int, int>,
       
   496                   CycleCanceling<GR> >();
       
   497     checkConcept< McfClassConcept<GR, double, double>,
       
   498                   CycleCanceling<GR, double> >();
       
   499     checkConcept< McfClassConcept<GR, int, double>,
       
   500                   CycleCanceling<GR, int, double> >();
       
   501   }
       
   502 
   460   // Test NetworkSimplex
   503   // Test NetworkSimplex
   461   { 
   504   { 
   462     typedef NetworkSimplex<Digraph> MCF;
   505     typedef NetworkSimplex<Digraph> MCF;
   463     runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
   506     runMcfGeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE", true);
   464     runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
   507     runMcfLeqTests<MCF>(MCF::FIRST_ELIGIBLE, "NS-FE");
   469     runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
   512     runMcfGeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL", true);
   470     runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
   513     runMcfLeqTests<MCF>(MCF::CANDIDATE_LIST, "NS-CL");
   471     runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
   514     runMcfGeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL", true);
   472     runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
   515     runMcfLeqTests<MCF>(MCF::ALTERING_LIST,  "NS-AL");
   473   }
   516   }
       
   517   
       
   518   // Test CapacityScaling
       
   519   {
       
   520     typedef CapacityScaling<Digraph> MCF;
       
   521     runMcfGeqTests<MCF>(0, "SSP");
       
   522     runMcfGeqTests<MCF>(2, "CAS");
       
   523   }
       
   524 
       
   525   // Test CostScaling
       
   526   {
       
   527     typedef CostScaling<Digraph> MCF;
       
   528     runMcfGeqTests<MCF>(MCF::PUSH, "COS-PR");
       
   529     runMcfGeqTests<MCF>(MCF::AUGMENT, "COS-AR");
       
   530     runMcfGeqTests<MCF>(MCF::PARTIAL_AUGMENT, "COS-PAR");
       
   531   }
       
   532 
       
   533   // Test CycleCanceling
       
   534   {
       
   535     typedef CycleCanceling<Digraph> MCF;
       
   536     runMcfGeqTests<MCF>(MCF::SIMPLE_CYCLE_CANCELING, "SCC");
       
   537     runMcfGeqTests<MCF>(MCF::MINIMUM_MEAN_CYCLE_CANCELING, "MMCC");
       
   538     runMcfGeqTests<MCF>(MCF::CANCEL_AND_TIGHTEN, "CAT");
       
   539   }
   474 
   540 
   475   return 0;
   541   return 0;
   476 }
   542 }