test/arborescence_test.cc
author deba
Tue, 31 Oct 2006 14:27:58 +0000
changeset 2282 9d7b12f83daa
parent 2180 d5544c9409e4
child 2386 81b47fc5c444
permissions -rw-r--r--
Bug fixes
deba@2025
     1
#include <iostream>
deba@2025
     2
#include <set>
deba@2025
     3
#include <vector>
deba@2025
     4
#include <iterator>
deba@2025
     5
deba@2025
     6
#include <cmath>
deba@2025
     7
#include <cstdlib>
deba@2025
     8
deba@2025
     9
#include <lemon/smart_graph.h>
deba@2025
    10
#include <lemon/min_cost_arborescence.h>
deba@2025
    11
deba@2025
    12
#include <lemon/graph_utils.h>
deba@2025
    13
#include <lemon/time_measure.h>
deba@2025
    14
deba@2025
    15
#include <lemon/tolerance.h>
deba@2025
    16
deba@2180
    17
#include "test_tools.h"
deba@2180
    18
deba@2025
    19
using namespace lemon;
deba@2025
    20
using namespace std;
deba@2025
    21
deba@2180
    22
const int n = 10;
deba@2180
    23
const int e = 22;
deba@2180
    24
deba@2180
    25
int sourceNode = 0;
deba@2180
    26
deba@2180
    27
int sources[e] = {
deba@2180
    28
  1, 0, 2, 4, 4, 3, 9, 8, 9, 8,
deba@2180
    29
  4, 2, 0, 6, 4, 1, 7, 2, 8, 6,
deba@2180
    30
  1, 0
deba@2180
    31
};
deba@2180
    32
deba@2180
    33
int targets[e] = {
deba@2180
    34
  8, 3, 1, 1, 4, 9, 8, 1, 8, 0,
deba@2180
    35
  3, 2, 1, 3, 1, 1, 2, 6, 3, 9,
deba@2180
    36
  1, 3
deba@2180
    37
};
deba@2180
    38
deba@2180
    39
double costs[e] = {
deba@2180
    40
  107.444, 70.3069, 46.0496, 28.3962, 91.4325,
deba@2180
    41
  76.9443, 61.986, 39.3754, 74.9575, 39.3153,
deba@2180
    42
  45.7094, 34.6184, 100.156, 95.726, 22.3429,
deba@2180
    43
  31.587, 51.6972, 29.6773, 115.038, 32.4137,
deba@2180
    44
  60.0038, 40.1237
deba@2180
    45
};
deba@2180
    46
deba@2180
    47
deba@2180
    48
deba@2180
    49
int main() {
deba@2025
    50
  typedef SmartGraph Graph;
deba@2025
    51
  GRAPH_TYPEDEFS(Graph);
deba@2025
    52
deba@2025
    53
  typedef Graph::EdgeMap<double> CostMap;
deba@2025
    54
deba@2025
    55
  Graph graph;
deba@2025
    56
  CostMap cost(graph);
deba@2025
    57
  vector<Node> nodes;
deba@2025
    58
  
deba@2025
    59
  for (int i = 0; i < n; ++i) {
deba@2025
    60
    nodes.push_back(graph.addNode());
deba@2025
    61
  }
deba@2025
    62
deba@2025
    63
  for (int i = 0; i < e; ++i) {
deba@2180
    64
    Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
deba@2180
    65
    cost[edge] = costs[i];
deba@2025
    66
  }
deba@2025
    67
deba@2180
    68
  Node source = nodes[sourceNode];
deba@2025
    69
deba@2025
    70
  MinCostArborescence<Graph, CostMap> mca(graph, cost);
deba@2025
    71
  mca.run(source);
deba@2025
    72
deba@2025
    73
  vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
deba@2025
    74
deba@2025
    75
  for (int i = 0; i < mca.dualSize(); ++i) {
deba@2025
    76
    dualSolution[i].first = mca.dualValue(i);
deba@2025
    77
    for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i); 
deba@2025
    78
         it != INVALID; ++it) {
deba@2025
    79
      dualSolution[i].second.insert(it);
deba@2025
    80
    }
deba@2025
    81
  }
deba@2025
    82
deba@2025
    83
  Tolerance<double> tolerance;
deba@2025
    84
deba@2025
    85
  for (EdgeIt it(graph); it != INVALID; ++it) {
deba@2025
    86
    if (mca.reached(graph.source(it))) {
deba@2025
    87
      double sum = 0.0;
deba@2025
    88
      for (int i = 0; i < (int)dualSolution.size(); ++i) {
deba@2025
    89
        if (dualSolution[i].second.find(graph.target(it)) 
deba@2025
    90
            != dualSolution[i].second.end() &&
deba@2025
    91
            dualSolution[i].second.find(graph.source(it)) 
deba@2025
    92
            == dualSolution[i].second.end()) {
deba@2025
    93
          sum += dualSolution[i].first;
deba@2025
    94
        }
deba@2025
    95
      }
deba@2025
    96
      if (mca.arborescence(it)) {
deba@2180
    97
        check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
deba@2025
    98
      }
deba@2180
    99
      check(!tolerance.less(cost[it], sum), "INVALID DUAL");
deba@2025
   100
    }
deba@2025
   101
  }
deba@2025
   102
deba@2025
   103
deba@2180
   104
  check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
deba@2025
   105
               "INVALID DUAL");
deba@2025
   106
deba@2025
   107
deba@2180
   108
  check(mca.reached(source), "INVALID ARBORESCENCE");
deba@2025
   109
  for (EdgeIt it(graph); it != INVALID; ++it) {
deba@2180
   110
    check(!mca.reached(graph.source(it)) || 
deba@2025
   111
                 mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
deba@2025
   112
  }
deba@2025
   113
deba@2025
   114
  for (NodeIt it(graph); it != INVALID; ++it) {
deba@2025
   115
    if (!mca.reached(it)) continue;
deba@2025
   116
    int cnt = 0;
deba@2025
   117
    for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2025
   118
      if (mca.arborescence(jt)) {
deba@2025
   119
        ++cnt;
deba@2025
   120
      }
deba@2025
   121
    }
deba@2180
   122
    check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
deba@2025
   123
  }
deba@2025
   124
  
deba@2025
   125
  return 0;
deba@2025
   126
}