test/arborescence_test.cc
changeset 2240 d93c034d3c98
parent 2025 93fcadf94ab0
child 2242 16523135943d
equal deleted inserted replaced
0:c439840dea46 1:dba5aceafe63
    12 #include <lemon/graph_utils.h>
    12 #include <lemon/graph_utils.h>
    13 #include <lemon/time_measure.h>
    13 #include <lemon/time_measure.h>
    14 
    14 
    15 #include <lemon/tolerance.h>
    15 #include <lemon/tolerance.h>
    16 
    16 
       
    17 #include "test_tools.h"
       
    18 
    17 using namespace lemon;
    19 using namespace lemon;
    18 using namespace std;
    20 using namespace std;
    19 
    21 
    20 int main(int argc, const char *argv[]) {
    22 const int n = 10;
       
    23 const int e = 22;
       
    24 
       
    25 int sourceNode = 0;
       
    26 
       
    27 int sources[e] = {
       
    28   1, 0, 2, 4, 4, 3, 9, 8, 9, 8,
       
    29   4, 2, 0, 6, 4, 1, 7, 2, 8, 6,
       
    30   1, 0
       
    31 };
       
    32 
       
    33 int targets[e] = {
       
    34   8, 3, 1, 1, 4, 9, 8, 1, 8, 0,
       
    35   3, 2, 1, 3, 1, 1, 2, 6, 3, 9,
       
    36   1, 3
       
    37 };
       
    38 
       
    39 double costs[e] = {
       
    40   107.444, 70.3069, 46.0496, 28.3962, 91.4325,
       
    41   76.9443, 61.986, 39.3754, 74.9575, 39.3153,
       
    42   45.7094, 34.6184, 100.156, 95.726, 22.3429,
       
    43   31.587, 51.6972, 29.6773, 115.038, 32.4137,
       
    44   60.0038, 40.1237
       
    45 };
       
    46 
       
    47 
       
    48 
       
    49 int main() {
    21   srand(time(0));
    50   srand(time(0));
    22   typedef SmartGraph Graph;
    51   typedef SmartGraph Graph;
    23   GRAPH_TYPEDEFS(Graph);
    52   GRAPH_TYPEDEFS(Graph);
    24 
    53 
    25   typedef Graph::EdgeMap<double> CostMap;
    54   typedef Graph::EdgeMap<double> CostMap;
    26 
       
    27   const int n = argc > 1 ? atoi(argv[1]) : 100;
       
    28   const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
       
    29 
    55 
    30   Graph graph;
    56   Graph graph;
    31   CostMap cost(graph);
    57   CostMap cost(graph);
    32   vector<Node> nodes;
    58   vector<Node> nodes;
    33   
    59   
    34   for (int i = 0; i < n; ++i) {
    60   for (int i = 0; i < n; ++i) {
    35     nodes.push_back(graph.addNode());
    61     nodes.push_back(graph.addNode());
    36   }
    62   }
    37 
    63 
    38   for (int i = 0; i < e; ++i) {
    64   for (int i = 0; i < e; ++i) {
    39     int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    65     Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
    40     int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    66     cost[edge] = costs[i];
    41     double c = rand() / (1.0 + RAND_MAX) * 100.0 + 20.0;
       
    42     Edge edge = graph.addEdge(nodes[s], nodes[t]);
       
    43     cost[edge] = c;
       
    44   }
    67   }
    45 
    68 
    46   Node source = nodes[(int)(n * (double)rand() / (RAND_MAX + 1.0))];
    69   Node source = nodes[sourceNode];
    47 
    70 
    48   MinCostArborescence<Graph, CostMap> mca(graph, cost);
    71   MinCostArborescence<Graph, CostMap> mca(graph, cost);
    49   mca.run(source);
    72   mca.run(source);
    50 
    73 
    51   vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
    74   vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
    70             == dualSolution[i].second.end()) {
    93             == dualSolution[i].second.end()) {
    71           sum += dualSolution[i].first;
    94           sum += dualSolution[i].first;
    72         }
    95         }
    73       }
    96       }
    74       if (mca.arborescence(it)) {
    97       if (mca.arborescence(it)) {
    75         LEMON_ASSERT(!tolerance.less(sum, cost[it]), "INVALID DUAL");
    98         check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
    76       }
    99       }
    77       LEMON_ASSERT(!tolerance.less(cost[it], sum), "INVALID DUAL");
   100       check(!tolerance.less(cost[it], sum), "INVALID DUAL");
    78     }
   101     }
    79   }
   102   }
    80 
   103 
    81 
   104 
    82   LEMON_ASSERT(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
   105   check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
    83                "INVALID DUAL");
   106                "INVALID DUAL");
    84 
   107 
    85 
   108 
    86   LEMON_ASSERT(mca.reached(source), "INVALID ARBORESCENCE");
   109   check(mca.reached(source), "INVALID ARBORESCENCE");
    87   for (EdgeIt it(graph); it != INVALID; ++it) {
   110   for (EdgeIt it(graph); it != INVALID; ++it) {
    88     LEMON_ASSERT(!mca.reached(graph.source(it)) || 
   111     check(!mca.reached(graph.source(it)) || 
    89                  mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
   112                  mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
    90   }
   113   }
    91 
   114 
    92   for (NodeIt it(graph); it != INVALID; ++it) {
   115   for (NodeIt it(graph); it != INVALID; ++it) {
    93     if (!mca.reached(it)) continue;
   116     if (!mca.reached(it)) continue;
    95     for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   118     for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    96       if (mca.arborescence(jt)) {
   119       if (mca.arborescence(jt)) {
    97         ++cnt;
   120         ++cnt;
    98       }
   121       }
    99     }
   122     }
   100     LEMON_ASSERT((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
   123     check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
   101   }
   124   }
   102   
   125   
   103   return 0;
   126   return 0;
   104 }
   127 }