alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2553: * Copyright (C) 2003-2008 alpar@2391: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2391: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2391: * alpar@2391: * Permission to use, modify and distribute this software is granted alpar@2391: * provided that this copyright notice appears in all copies. For alpar@2391: * precise terms see the accompanying LICENSE file. alpar@2391: * alpar@2391: * This software is provided "AS IS" with no warranty of any kind, alpar@2391: * express or implied, and with no claim as to its suitability for any alpar@2391: * purpose. alpar@2391: * alpar@2391: */ alpar@2391: deba@2025: #include deba@2025: #include deba@2025: #include deba@2025: #include deba@2025: alpar@2569: #include deba@2025: #include deba@2025: deba@2025: #include deba@2025: #include deba@2025: deba@2025: #include deba@2025: #include deba@2025: deba@2025: #include deba@2025: deba@2180: #include "test_tools.h" deba@2180: deba@2025: using namespace lemon; deba@2025: using namespace std; deba@2025: deba@2386: const int NODES = 10; deba@2386: const int EDGES = 22; deba@2180: deba@2180: int sourceNode = 0; deba@2180: deba@2386: int sources[EDGES] = { deba@2180: 1, 0, 2, 4, 4, 3, 9, 8, 9, 8, deba@2180: 4, 2, 0, 6, 4, 1, 7, 2, 8, 6, deba@2180: 1, 0 deba@2180: }; deba@2180: deba@2386: int targets[EDGES] = { deba@2180: 8, 3, 1, 1, 4, 9, 8, 1, 8, 0, deba@2180: 3, 2, 1, 3, 1, 1, 2, 6, 3, 9, deba@2180: 1, 3 deba@2180: }; deba@2180: deba@2386: double costs[EDGES] = { deba@2180: 107.444, 70.3069, 46.0496, 28.3962, 91.4325, deba@2180: 76.9443, 61.986, 39.3754, 74.9575, 39.3153, deba@2180: 45.7094, 34.6184, 100.156, 95.726, 22.3429, deba@2180: 31.587, 51.6972, 29.6773, 115.038, 32.4137, deba@2180: 60.0038, 40.1237 deba@2180: }; deba@2180: deba@2180: deba@2180: deba@2180: int main() { deba@2025: typedef SmartGraph Graph; deba@2025: GRAPH_TYPEDEFS(Graph); deba@2025: deba@2025: typedef Graph::EdgeMap CostMap; deba@2025: deba@2025: Graph graph; deba@2025: CostMap cost(graph); deba@2025: vector nodes; deba@2025: deba@2386: for (int i = 0; i < NODES; ++i) { deba@2025: nodes.push_back(graph.addNode()); deba@2025: } deba@2025: deba@2386: for (int i = 0; i < EDGES; ++i) { deba@2180: Edge edge = graph.addEdge(nodes[sources[i]], nodes[targets[i]]); deba@2180: cost[edge] = costs[i]; deba@2025: } deba@2025: deba@2180: Node source = nodes[sourceNode]; deba@2025: deba@2025: MinCostArborescence mca(graph, cost); deba@2025: mca.run(source); deba@2025: deba@2025: vector > > 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::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 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@2386: 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@2180: check(!tolerance.less(sum, cost[it]), "INVALID DUAL"); deba@2025: } deba@2180: check(!tolerance.less(cost[it], sum), "INVALID DUAL"); deba@2025: } deba@2025: } deba@2025: deba@2025: deba@2180: check(!tolerance.different(mca.dualValue(), mca.arborescenceValue()), deba@2025: "INVALID DUAL"); deba@2025: deba@2025: deba@2180: check(mca.reached(source), "INVALID ARBORESCENCE"); deba@2025: for (EdgeIt it(graph); it != INVALID; ++it) { deba@2180: check(!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@2180: check((it == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE"); deba@2025: } deba@2025: deba@2025: return 0; deba@2025: }