test/min_cost_arborescence_test.cc
changeset 932 2eebc8f7dca5
parent 490 7f8560cb9d65
child 877 141f9c0db4a3
child 969 7e368d9b67f7
equal deleted inserted replaced
0:3eac2cf61100 1:f412d85ee700
    22 #include <iterator>
    22 #include <iterator>
    23 
    23 
    24 #include <lemon/smart_graph.h>
    24 #include <lemon/smart_graph.h>
    25 #include <lemon/min_cost_arborescence.h>
    25 #include <lemon/min_cost_arborescence.h>
    26 #include <lemon/lgf_reader.h>
    26 #include <lemon/lgf_reader.h>
       
    27 #include <lemon/concepts/digraph.h>
    27 
    28 
    28 #include "test_tools.h"
    29 #include "test_tools.h"
    29 
    30 
    30 using namespace lemon;
    31 using namespace lemon;
    31 using namespace std;
    32 using namespace std;
    68   "1 1  20     60\n"
    69   "1 1  20     60\n"
    69   "0 3  21     40\n"
    70   "0 3  21     40\n"
    70   "@attributes\n"
    71   "@attributes\n"
    71   "source 0\n";
    72   "source 0\n";
    72 
    73 
       
    74 
       
    75 void checkMinCostArborescenceCompile()
       
    76 {
       
    77   typedef double VType;
       
    78   typedef concepts::Digraph Digraph;
       
    79   typedef concepts::ReadMap<Digraph::Arc, VType> CostMap;
       
    80   typedef Digraph::Node Node;
       
    81   typedef Digraph::Arc Arc;
       
    82   typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap;
       
    83   typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap;
       
    84 
       
    85   typedef MinCostArborescence<Digraph, CostMap>::
       
    86             SetArborescenceMap<ArbMap>::
       
    87             SetPredMap<PredMap>::Create MinCostArbType;
       
    88 
       
    89   Digraph g;
       
    90   Node s, n;
       
    91   Arc e;
       
    92   VType c;
       
    93   bool b;
       
    94   int i;
       
    95   CostMap cost;
       
    96   ArbMap arb;
       
    97   PredMap pred;
       
    98 
       
    99   MinCostArbType mcarb_test(g, cost);
       
   100   const MinCostArbType& const_mcarb_test = mcarb_test;
       
   101 
       
   102   mcarb_test
       
   103     .arborescenceMap(arb)
       
   104     .predMap(pred)
       
   105     .run(s);
       
   106 
       
   107   mcarb_test.init();
       
   108   mcarb_test.addSource(s);
       
   109   mcarb_test.start();
       
   110   n = mcarb_test.processNextNode();
       
   111   b = const_mcarb_test.emptyQueue();
       
   112   i = const_mcarb_test.queueSize();
       
   113   
       
   114   c = const_mcarb_test.arborescenceCost();
       
   115   b = const_mcarb_test.arborescence(e);
       
   116   e = const_mcarb_test.pred(n);
       
   117   const MinCostArbType::ArborescenceMap &am =
       
   118     const_mcarb_test.arborescenceMap();
       
   119   const MinCostArbType::PredMap &pm =
       
   120     const_mcarb_test.predMap();
       
   121   b = const_mcarb_test.reached(n);
       
   122   b = const_mcarb_test.processed(n);
       
   123   
       
   124   i = const_mcarb_test.dualNum();
       
   125   c = const_mcarb_test.dualValue();
       
   126   i = const_mcarb_test.dualSize(i);
       
   127   c = const_mcarb_test.dualValue(i);
       
   128   
       
   129   ignore_unused_variable_warning(am);
       
   130   ignore_unused_variable_warning(pm);
       
   131 }
       
   132 
    73 int main() {
   133 int main() {
    74   typedef SmartDigraph Digraph;
   134   typedef SmartDigraph Digraph;
    75   DIGRAPH_TYPEDEFS(Digraph);
   135   DIGRAPH_TYPEDEFS(Digraph);
    76 
   136 
    77   typedef Digraph::ArcMap<double> CostMap;
   137   typedef Digraph::ArcMap<double> CostMap;
   108             == dualSolution[i].second.end()) {
   168             == dualSolution[i].second.end()) {
   109           sum += dualSolution[i].first;
   169           sum += dualSolution[i].first;
   110         }
   170         }
   111       }
   171       }
   112       if (mca.arborescence(it)) {
   172       if (mca.arborescence(it)) {
   113         check(sum == cost[it], "INVALID DUAL");
   173         check(sum == cost[it], "Invalid dual solution");
   114       }
   174       }
   115       check(sum <= cost[it], "INVALID DUAL");
   175       check(sum <= cost[it], "Invalid dual solution");
   116     }
   176     }
   117   }
   177   }
   118 
   178 
   119 
   179 
   120   check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
   180   check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution");
   121 
   181 
   122   check(mca.reached(source), "INVALID ARBORESCENCE");
   182   check(mca.reached(source), "Invalid arborescence");
   123   for (ArcIt a(digraph); a != INVALID; ++a) {
   183   for (ArcIt a(digraph); a != INVALID; ++a) {
   124     check(!mca.reached(digraph.source(a)) ||
   184     check(!mca.reached(digraph.source(a)) ||
   125           mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
   185           mca.reached(digraph.target(a)), "Invalid arborescence");
   126   }
   186   }
   127 
   187 
   128   for (NodeIt n(digraph); n != INVALID; ++n) {
   188   for (NodeIt n(digraph); n != INVALID; ++n) {
   129     if (!mca.reached(n)) continue;
   189     if (!mca.reached(n)) continue;
   130     int cnt = 0;
   190     int cnt = 0;
   131     for (InArcIt a(digraph, n); a != INVALID; ++a) {
   191     for (InArcIt a(digraph, n); a != INVALID; ++a) {
   132       if (mca.arborescence(a)) {
   192       if (mca.arborescence(a)) {
   133         check(mca.pred(n) == a, "INVALID ARBORESCENCE");
   193         check(mca.pred(n) == a, "Invalid arborescence");
   134         ++cnt;
   194         ++cnt;
   135       }
   195       }
   136     }
   196     }
   137     check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
   197     check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence");
   138   }
   198   }
   139 
   199 
   140   Digraph::ArcMap<bool> arborescence(digraph);
   200   Digraph::ArcMap<bool> arborescence(digraph);
   141   check(mca.arborescenceValue() ==
   201   check(mca.arborescenceCost() ==
   142         minCostArborescence(digraph, cost, source, arborescence),
   202         minCostArborescence(digraph, cost, source, arborescence),
   143         "WRONG FUNCTION");
   203         "Wrong result of the function interface");
   144 
   204 
   145   return 0;
   205   return 0;
   146 }
   206 }