1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/arborescence_test.cc	Fri Mar 31 11:10:44 2006 +0000
     1.3 @@ -0,0 +1,104 @@
     1.4 +#include <iostream>
     1.5 +#include <set>
     1.6 +#include <vector>
     1.7 +#include <iterator>
     1.8 +
     1.9 +#include <cmath>
    1.10 +#include <cstdlib>
    1.11 +
    1.12 +#include <lemon/smart_graph.h>
    1.13 +#include <lemon/min_cost_arborescence.h>
    1.14 +
    1.15 +#include <lemon/graph_utils.h>
    1.16 +#include <lemon/time_measure.h>
    1.17 +
    1.18 +#include <lemon/tolerance.h>
    1.19 +
    1.20 +using namespace lemon;
    1.21 +using namespace std;
    1.22 +
    1.23 +int main(int argc, const char *argv[]) {
    1.24 +  srand(time(0));
    1.25 +  typedef SmartGraph Graph;
    1.26 +  GRAPH_TYPEDEFS(Graph);
    1.27 +
    1.28 +  typedef Graph::EdgeMap<double> CostMap;
    1.29 +
    1.30 +  const int n = argc > 1 ? atoi(argv[1]) : 100;
    1.31 +  const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
    1.32 +
    1.33 +  Graph graph;
    1.34 +  CostMap cost(graph);
    1.35 +  vector<Node> nodes;
    1.36 +  
    1.37 +  for (int i = 0; i < n; ++i) {
    1.38 +    nodes.push_back(graph.addNode());
    1.39 +  }
    1.40 +
    1.41 +  for (int i = 0; i < e; ++i) {
    1.42 +    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    1.43 +    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    1.44 +    double c = rand() / (1.0 + RAND_MAX) * 100.0 + 20.0;
    1.45 +    Edge edge = graph.addEdge(nodes[s], nodes[t]);
    1.46 +    cost[edge] = c;
    1.47 +  }
    1.48 +
    1.49 +  Node source = nodes[(int)(n * (double)rand() / (RAND_MAX + 1.0))];
    1.50 +
    1.51 +  MinCostArborescence<Graph, CostMap> mca(graph, cost);
    1.52 +  mca.run(source);
    1.53 +
    1.54 +  vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
    1.55 +
    1.56 +  for (int i = 0; i < mca.dualSize(); ++i) {
    1.57 +    dualSolution[i].first = mca.dualValue(i);
    1.58 +    for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i); 
    1.59 +         it != INVALID; ++it) {
    1.60 +      dualSolution[i].second.insert(it);
    1.61 +    }
    1.62 +  }
    1.63 +
    1.64 +  Tolerance<double> tolerance;
    1.65 +
    1.66 +  for (EdgeIt it(graph); it != INVALID; ++it) {
    1.67 +    if (mca.reached(graph.source(it))) {
    1.68 +      double sum = 0.0;
    1.69 +      for (int i = 0; i < (int)dualSolution.size(); ++i) {
    1.70 +        if (dualSolution[i].second.find(graph.target(it)) 
    1.71 +            != dualSolution[i].second.end() &&
    1.72 +            dualSolution[i].second.find(graph.source(it)) 
    1.73 +            == dualSolution[i].second.end()) {
    1.74 +          sum += dualSolution[i].first;
    1.75 +        }
    1.76 +      }
    1.77 +      if (mca.arborescence(it)) {
    1.78 +        LEMON_ASSERT(!tolerance.less(sum, cost[it]), "INVALID DUAL");
    1.79 +      }
    1.80 +      LEMON_ASSERT(!tolerance.less(cost[it], sum), "INVALID DUAL");
    1.81 +    }
    1.82 +  }
    1.83 +
    1.84 +
    1.85 +  LEMON_ASSERT(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
    1.86 +               "INVALID DUAL");
    1.87 +
    1.88 +
    1.89 +  LEMON_ASSERT(mca.reached(source), "INVALID ARBORESCENCE");
    1.90 +  for (EdgeIt it(graph); it != INVALID; ++it) {
    1.91 +    LEMON_ASSERT(!mca.reached(graph.source(it)) || 
    1.92 +                 mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
    1.93 +  }
    1.94 +
    1.95 +  for (NodeIt it(graph); it != INVALID; ++it) {
    1.96 +    if (!mca.reached(it)) continue;
    1.97 +    int cnt = 0;
    1.98 +    for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    1.99 +      if (mca.arborescence(jt)) {
   1.100 +        ++cnt;
   1.101 +      }
   1.102 +    }
   1.103 +    LEMON_ASSERT((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
   1.104 +  }
   1.105 +  
   1.106 +  return 0;
   1.107 +}