test/arborescence_test.cc
author alpar
Fri, 08 Feb 2008 11:04:37 +0000
changeset 2571 f5c6e63f51d1
parent 2553 bfced05fa852
permissions -rw-r--r--
Hopefully fix all compilation errors.
     1 /* -*- C++ -*-
     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/math.h>
    25 #include <cstdlib>
    26 
    27 #include <lemon/smart_graph.h>
    28 #include <lemon/min_cost_arborescence.h>
    29 
    30 #include <lemon/graph_utils.h>
    31 #include <lemon/time_measure.h>
    32 
    33 #include <lemon/tolerance.h>
    34 
    35 #include "test_tools.h"
    36 
    37 using namespace lemon;
    38 using namespace std;
    39 
    40 const int NODES = 10;
    41 const int EDGES = 22;
    42 
    43 int sourceNode = 0;
    44 
    45 int sources[EDGES] = {
    46   1, 0, 2, 4, 4, 3, 9, 8, 9, 8,
    47   4, 2, 0, 6, 4, 1, 7, 2, 8, 6,
    48   1, 0
    49 };
    50 
    51 int targets[EDGES] = {
    52   8, 3, 1, 1, 4, 9, 8, 1, 8, 0,
    53   3, 2, 1, 3, 1, 1, 2, 6, 3, 9,
    54   1, 3
    55 };
    56 
    57 double costs[EDGES] = {
    58   107.444, 70.3069, 46.0496, 28.3962, 91.4325,
    59   76.9443, 61.986, 39.3754, 74.9575, 39.3153,
    60   45.7094, 34.6184, 100.156, 95.726, 22.3429,
    61   31.587, 51.6972, 29.6773, 115.038, 32.4137,
    62   60.0038, 40.1237
    63 };
    64 
    65 
    66 
    67 int main() {
    68   typedef SmartGraph Graph;
    69   GRAPH_TYPEDEFS(Graph);
    70 
    71   typedef Graph::EdgeMap<double> CostMap;
    72 
    73   Graph graph;
    74   CostMap cost(graph);
    75   vector<Node> nodes;
    76   
    77   for (int i = 0; i < NODES; ++i) {
    78     nodes.push_back(graph.addNode());
    79   }
    80 
    81   for (int i = 0; i < EDGES; ++i) {
    82     Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]);
    83     cost[edge] = costs[i];
    84   }
    85 
    86   Node source = nodes[sourceNode];
    87 
    88   MinCostArborescence<Graph, CostMap> mca(graph, cost);
    89   mca.run(source);
    90 
    91   vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
    92 
    93   for (int i = 0; i < mca.dualSize(); ++i) {
    94     dualSolution[i].first = mca.dualValue(i);
    95     for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i); 
    96          it != INVALID; ++it) {
    97       dualSolution[i].second.insert(it);
    98     }
    99   }
   100 
   101   Tolerance<double> tolerance;
   102 
   103   for (EdgeIt it(graph); it != INVALID; ++it) {
   104     if (mca.reached(graph.source(it))) {
   105       double sum = 0.0;
   106       for (int i = 0; i < int(dualSolution.size()); ++i) {
   107         if (dualSolution[i].second.find(graph.target(it)) 
   108             != dualSolution[i].second.end() &&
   109             dualSolution[i].second.find(graph.source(it)) 
   110             == dualSolution[i].second.end()) {
   111           sum += dualSolution[i].first;
   112         }
   113       }
   114       if (mca.arborescence(it)) {
   115         check(!tolerance.less(sum, cost[it]), "INVALID DUAL");
   116       }
   117       check(!tolerance.less(cost[it], sum), "INVALID DUAL");
   118     }
   119   }
   120 
   121 
   122   check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
   123                "INVALID DUAL");
   124 
   125 
   126   check(mca.reached(source), "INVALID ARBORESCENCE");
   127   for (EdgeIt it(graph); it != INVALID; ++it) {
   128     check(!mca.reached(graph.source(it)) || 
   129                  mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
   130   }
   131 
   132   for (NodeIt it(graph); it != INVALID; ++it) {
   133     if (!mca.reached(it)) continue;
   134     int cnt = 0;
   135     for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   136       if (mca.arborescence(jt)) {
   137         ++cnt;
   138       }
   139     }
   140     check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
   141   }
   142   
   143   return 0;
   144 }