deba@2025: #include <iostream>
deba@2025: #include <set>
deba@2025: #include <vector>
deba@2025: #include <iterator>
deba@2025: 
deba@2025: #include <cmath>
deba@2025: #include <cstdlib>
deba@2025: 
deba@2025: #include <lemon/smart_graph.h>
deba@2025: #include <lemon/min_cost_arborescence.h>
deba@2025: 
deba@2025: #include <lemon/graph_utils.h>
deba@2025: #include <lemon/time_measure.h>
deba@2025: 
deba@2025: #include <lemon/tolerance.h>
deba@2025: 
deba@2025: using namespace lemon;
deba@2025: using namespace std;
deba@2025: 
deba@2025: int main(int argc, const char *argv[]) {
deba@2025:   srand(time(0));
deba@2025:   typedef SmartGraph Graph;
deba@2025:   GRAPH_TYPEDEFS(Graph);
deba@2025: 
deba@2025:   typedef Graph::EdgeMap<double> CostMap;
deba@2025: 
deba@2025:   const int n = argc > 1 ? atoi(argv[1]) : 100;
deba@2025:   const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n));
deba@2025: 
deba@2025:   Graph graph;
deba@2025:   CostMap cost(graph);
deba@2025:   vector<Node> nodes;
deba@2025:   
deba@2025:   for (int i = 0; i < n; ++i) {
deba@2025:     nodes.push_back(graph.addNode());
deba@2025:   }
deba@2025: 
deba@2025:   for (int i = 0; i < e; ++i) {
deba@2025:     int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@2025:     int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@2025:     double c = rand() / (1.0 + RAND_MAX) * 100.0 + 20.0;
deba@2025:     Edge edge = graph.addEdge(nodes[s], nodes[t]);
deba@2025:     cost[edge] = c;
deba@2025:   }
deba@2025: 
deba@2025:   Node source = nodes[(int)(n * (double)rand() / (RAND_MAX + 1.0))];
deba@2025: 
deba@2025:   MinCostArborescence<Graph, CostMap> mca(graph, cost);
deba@2025:   mca.run(source);
deba@2025: 
deba@2025:   vector<pair<double, set<Node> > > dualSolution(mca.dualSize());
deba@2025: 
deba@2025:   for (int i = 0; i < mca.dualSize(); ++i) {
deba@2025:     dualSolution[i].first = mca.dualValue(i);
deba@2025:     for (MinCostArborescence<Graph, CostMap>::DualIt it(mca, i); 
deba@2025:          it != INVALID; ++it) {
deba@2025:       dualSolution[i].second.insert(it);
deba@2025:     }
deba@2025:   }
deba@2025: 
deba@2025:   Tolerance<double> tolerance;
deba@2025: 
deba@2025:   for (EdgeIt it(graph); it != INVALID; ++it) {
deba@2025:     if (mca.reached(graph.source(it))) {
deba@2025:       double sum = 0.0;
deba@2025:       for (int i = 0; i < (int)dualSolution.size(); ++i) {
deba@2025:         if (dualSolution[i].second.find(graph.target(it)) 
deba@2025:             != dualSolution[i].second.end() &&
deba@2025:             dualSolution[i].second.find(graph.source(it)) 
deba@2025:             == dualSolution[i].second.end()) {
deba@2025:           sum += dualSolution[i].first;
deba@2025:         }
deba@2025:       }
deba@2025:       if (mca.arborescence(it)) {
deba@2025:         LEMON_ASSERT(!tolerance.less(sum, cost[it]), "INVALID DUAL");
deba@2025:       }
deba@2025:       LEMON_ASSERT(!tolerance.less(cost[it], sum), "INVALID DUAL");
deba@2025:     }
deba@2025:   }
deba@2025: 
deba@2025: 
deba@2025:   LEMON_ASSERT(!tolerance.different(mca.dualValue(), mca.arborescenceValue()),
deba@2025:                "INVALID DUAL");
deba@2025: 
deba@2025: 
deba@2025:   LEMON_ASSERT(mca.reached(source), "INVALID ARBORESCENCE");
deba@2025:   for (EdgeIt it(graph); it != INVALID; ++it) {
deba@2025:     LEMON_ASSERT(!mca.reached(graph.source(it)) || 
deba@2025:                  mca.reached(graph.target(it)), "INVALID ARBORESCENCE");
deba@2025:   }
deba@2025: 
deba@2025:   for (NodeIt it(graph); it != INVALID; ++it) {
deba@2025:     if (!mca.reached(it)) continue;
deba@2025:     int cnt = 0;
deba@2025:     for (InEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2025:       if (mca.arborescence(jt)) {
deba@2025:         ++cnt;
deba@2025:       }
deba@2025:     }
deba@2025:     LEMON_ASSERT((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
deba@2025:   }
deba@2025:   
deba@2025:   return 0;
deba@2025: }