test/arborescence_test.cc
author deba
Mon, 26 Mar 2007 10:44:03 +0000
changeset 2414 9e80927b7921
parent 2386 81b47fc5c444
child 2553 bfced05fa852
permissions -rw-r--r--
Bug fix
Wrong renaming
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2391
     5
 * Copyright (C) 2003-2007
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
deba@2025
    19
#include <iostream>
deba@2025
    20
#include <set>
deba@2025
    21
#include <vector>
deba@2025
    22
#include <iterator>
deba@2025
    23
deba@2025
    24
#include <cmath>
deba@2025
    25
#include <cstdlib>
deba@2025
    26
deba@2025
    27
#include <lemon/smart_graph.h>
deba@2025
    28
#include <lemon/min_cost_arborescence.h>
deba@2025
    29
deba@2025
    30
#include <lemon/graph_utils.h>
deba@2025
    31
#include <lemon/time_measure.h>
deba@2025
    32
deba@2025
    33
#include <lemon/tolerance.h>
deba@2025
    34
deba@2180
    35
#include "test_tools.h"
deba@2180
    36
deba@2025
    37
using namespace lemon;
deba@2025
    38
using namespace std;
deba@2025
    39
deba@2386
    40
const int NODES = 10;
deba@2386
    41
const int EDGES = 22;
deba@2180
    42
deba@2180
    43
int sourceNode = 0;
deba@2180
    44
deba@2386
    45
int sources[EDGES] = {
deba@2180
    46
  1, 0, 2, 4, 4, 3, 9, 8, 9, 8,
deba@2180
    47
  4, 2, 0, 6, 4, 1, 7, 2, 8, 6,
deba@2180
    48
  1, 0
deba@2180
    49
};
deba@2180
    50
deba@2386
    51
int targets[EDGES] = {
deba@2180
    52
  8, 3, 1, 1, 4, 9, 8, 1, 8, 0,
deba@2180
    53
  3, 2, 1, 3, 1, 1, 2, 6, 3, 9,
deba@2180
    54
  1, 3
deba@2180
    55
};
deba@2180
    56
deba@2386
    57
double costs[EDGES] = {
deba@2180
    58
  107.444, 70.3069, 46.0496, 28.3962, 91.4325,
deba@2180
    59
  76.9443, 61.986, 39.3754, 74.9575, 39.3153,
deba@2180
    60
  45.7094, 34.6184, 100.156, 95.726, 22.3429,
deba@2180
    61
  31.587, 51.6972, 29.6773, 115.038, 32.4137,
deba@2180
    62
  60.0038, 40.1237
deba@2180
    63
};
deba@2180
    64
deba@2180
    65
deba@2180
    66
deba@2180
    67
int main() {
deba@2025
    68
  typedef SmartGraph Graph;
deba@2025
    69
  GRAPH_TYPEDEFS(Graph);
deba@2025
    70
deba@2025
    71
  typedef Graph::EdgeMap<double> CostMap;
deba@2025
    72
deba@2025
    73
  Graph graph;
deba@2025
    74
  CostMap cost(graph);
deba@2025
    75
  vector<Node> nodes;
deba@2025
    76
  
deba@2386
    77
  for (int i = 0; i < NODES; ++i) {
deba@2025
    78
    nodes.push_back(graph.addNode());
deba@2025
    79
  }
deba@2025
    80
deba@2386
    81
  for (int i = 0; i < EDGES; ++i) {
deba@2180
    82
    Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
deba@2180
    83
    cost[edge] = costs[i];
deba@2025
    84
  }
deba@2025
    85
deba@2180
    86
  Node source = nodes[sourceNode];
deba@2025
    87
deba@2025
    88
  MinCostArborescence<Graph, CostMap> mca(graph, cost);
deba@2025
    89
  mca.run(source);
deba@2025
    90
deba@2025
    91
  vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
deba@2025
    92
deba@2025
    93
  for (int i = 0; i < mca.dualSize(); ++i) {
deba@2025
    94
    dualSolution[i].first = mca.dualValue(i);
deba@2025
    95
    for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i); 
deba@2025
    96
         it != INVALID; ++it) {
deba@2025
    97
      dualSolution[i].second.insert(it);
deba@2025
    98
    }
deba@2025
    99
  }
deba@2025
   100
deba@2025
   101
  Tolerance<double> tolerance;
deba@2025
   102
deba@2025
   103
  for (EdgeIt it(graph); it != INVALID; ++it) {
deba@2025
   104
    if (mca.reached(graph.source(it))) {
deba@2025
   105
      double sum = 0.0;
deba@2386
   106
      for (int i = 0; i < int(dualSolution.size()); ++i) {
deba@2025
   107
        if (dualSolution[i].second.find(graph.target(it)) 
deba@2025
   108
            != dualSolution[i].second.end() &&
deba@2025
   109
            dualSolution[i].second.find(graph.source(it)) 
deba@2025
   110
            == dualSolution[i].second.end()) {
deba@2025
   111
          sum += dualSolution[i].first;
deba@2025
   112
        }
deba@2025
   113
      }
deba@2025
   114
      if (mca.arborescence(it)) {
deba@2180
   115
        check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
deba@2025
   116
      }
deba@2180
   117
      check(!tolerance.less(cost[it], sum), "INVALID DUAL");
deba@2025
   118
    }
deba@2025
   119
  }
deba@2025
   120
deba@2025
   121
deba@2180
   122
  check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
deba@2025
   123
               "INVALID DUAL");
deba@2025
   124
deba@2025
   125
deba@2180
   126
  check(mca.reached(source), "INVALID ARBORESCENCE");
deba@2025
   127
  for (EdgeIt it(graph); it != INVALID; ++it) {
deba@2180
   128
    check(!mca.reached(graph.source(it)) || 
deba@2025
   129
                 mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
deba@2025
   130
  }
deba@2025
   131
deba@2025
   132
  for (NodeIt it(graph); it != INVALID; ++it) {
deba@2025
   133
    if (!mca.reached(it)) continue;
deba@2025
   134
    int cnt = 0;
deba@2025
   135
    for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2025
   136
      if (mca.arborescence(jt)) {
deba@2025
   137
        ++cnt;
deba@2025
   138
      }
deba@2025
   139
    }
deba@2180
   140
    check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
deba@2025
   141
  }
deba@2025
   142
  
deba@2025
   143
  return 0;
deba@2025
   144
}