test/min_cost_arborescence_test.cc
changeset 600 0ba8dfce7259
child 625 029a48052c67
equal deleted inserted replaced
-1:000000000000 0:3eac2cf61100
       
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library.
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 #include <iostream>
       
    20 #include <set>
       
    21 #include <vector>
       
    22 #include <iterator>
       
    23 
       
    24 #include <lemon/smart_graph.h>
       
    25 #include <lemon/min_cost_arborescence.h>
       
    26 #include <lemon/lgf_reader.h>
       
    27 
       
    28 #include "test_tools.h"
       
    29 
       
    30 using namespace lemon;
       
    31 using namespace std;
       
    32 
       
    33 const char test_lgf[] =
       
    34   "@nodes\n"
       
    35   "label\n"
       
    36   "0\n"
       
    37   "1\n"
       
    38   "2\n"
       
    39   "3\n"
       
    40   "4\n"
       
    41   "5\n"
       
    42   "6\n"
       
    43   "7\n"
       
    44   "8\n"
       
    45   "9\n"
       
    46   "@arcs\n"
       
    47   "     label  cost\n"
       
    48   "1 8  0      107\n"
       
    49   "0 3  1      70\n"
       
    50   "2 1  2      46\n"
       
    51   "4 1  3      28\n"
       
    52   "4 4  4      91\n"
       
    53   "3 9  5      76\n"
       
    54   "9 8  6      61\n"
       
    55   "8 1  7      39\n"
       
    56   "9 8  8      74\n"
       
    57   "8 0  9      39\n"
       
    58   "4 3  10     45\n"
       
    59   "2 2  11     34\n"
       
    60   "0 1  12     100\n"
       
    61   "6 3  13     95\n"
       
    62   "4 1  14     22\n"
       
    63   "1 1  15     31\n"
       
    64   "7 2  16     51\n"
       
    65   "2 6  17     29\n"
       
    66   "8 3  18     115\n"
       
    67   "6 9  19     32\n"
       
    68   "1 1  20     60\n"
       
    69   "0 3  21     40\n"
       
    70   "@attributes\n"
       
    71   "source 0\n";
       
    72 
       
    73 int main() {
       
    74   typedef SmartDigraph Digraph;
       
    75   DIGRAPH_TYPEDEFS(Digraph);
       
    76 
       
    77   typedef Digraph::ArcMap<double> CostMap;
       
    78 
       
    79   Digraph digraph;
       
    80   CostMap cost(digraph);
       
    81   Node source;
       
    82 
       
    83   std::istringstream is(test_lgf);
       
    84   digraphReader(digraph, is).
       
    85     arcMap("cost", cost).
       
    86     node("source", source).run();
       
    87 
       
    88   MinCostArborescence<Digraph, CostMap> mca(digraph, cost);
       
    89   mca.run(source);
       
    90 
       
    91   vector<pair<double, set<Node> > > dualSolution(mca.dualNum());
       
    92 
       
    93   for (int i = 0; i < mca.dualNum(); ++i) {
       
    94     dualSolution[i].first = mca.dualValue(i);
       
    95     for (MinCostArborescence<Digraph, CostMap>::DualIt it(mca, i);
       
    96          it != INVALID; ++it) {
       
    97       dualSolution[i].second.insert(it);
       
    98     }
       
    99   }
       
   100 
       
   101   for (ArcIt it(digraph); it != INVALID; ++it) {
       
   102     if (mca.reached(digraph.source(it))) {
       
   103       double sum = 0.0;
       
   104       for (int i = 0; i < int(dualSolution.size()); ++i) {
       
   105         if (dualSolution[i].second.find(digraph.target(it))
       
   106             != dualSolution[i].second.end() &&
       
   107             dualSolution[i].second.find(digraph.source(it))
       
   108             == dualSolution[i].second.end()) {
       
   109           sum += dualSolution[i].first;
       
   110         }
       
   111       }
       
   112       if (mca.arborescence(it)) {
       
   113         check(sum == cost[it], "INVALID DUAL");
       
   114       }
       
   115       check(sum <= cost[it], "INVALID DUAL");
       
   116     }
       
   117   }
       
   118 
       
   119 
       
   120   check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
       
   121 
       
   122   check(mca.reached(source), "INVALID ARBORESCENCE");
       
   123   for (ArcIt a(digraph); a != INVALID; ++a) {
       
   124     check(!mca.reached(digraph.source(a)) ||
       
   125           mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
       
   126   }
       
   127 
       
   128   for (NodeIt n(digraph); n != INVALID; ++n) {
       
   129     if (!mca.reached(n)) continue;
       
   130     int cnt = 0;
       
   131     for (InArcIt a(digraph, n); a != INVALID; ++a) {
       
   132       if (mca.arborescence(a)) {
       
   133         check(mca.pred(n) == a, "INVALID ARBORESCENCE");
       
   134         ++cnt;
       
   135       }
       
   136     }
       
   137     check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
       
   138   }
       
   139 
       
   140   Digraph::ArcMap<bool> arborescence(digraph);
       
   141   check(mca.arborescenceValue() ==
       
   142         minCostArborescence(digraph, cost, source, arborescence),
       
   143         "WRONG FUNCTION");
       
   144 
       
   145   return 0;
       
   146 }