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@2290: #include deba@2290: #include deba@2290: #include deba@2290: #include deba@2290: #include deba@2290: deba@2290: #include "test_tools.h" deba@2290: deba@2290: using namespace std; deba@2290: using namespace lemon; deba@2290: deba@2290: void graph_copy_test() { deba@2290: const int nn = 10; deba@2290: deba@2290: SmartGraph source; deba@2290: SmartGraph::NodeMap snm(source); deba@2290: SmartGraph::EdgeMap sem(source); deba@2290: SmartGraph::Node sn = INVALID; deba@2290: SmartGraph::Edge se = INVALID; deba@2290: deba@2290: std::vector snv; deba@2290: for (int i = 0; i < nn; ++i) { deba@2290: SmartGraph::Node node = source.addNode(); deba@2290: snv.push_back(node); deba@2290: snm[node] = i * i; deba@2290: if (i == 0) sn = node; deba@2290: } deba@2290: deba@2290: for (int i = 0; i < nn; ++i) { deba@2290: for (int j = 0; j < nn; ++j) { deba@2290: SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]); deba@2290: sem[edge] = i + j * j; deba@2290: if (i == 0 && j == 0) se = edge; deba@2290: } deba@2290: } deba@2290: deba@2290: ListGraph target; deba@2290: ListGraph::NodeMap tnm(target); deba@2290: ListGraph::EdgeMap tem(target); deba@2290: ListGraph::Node tn; deba@2290: ListGraph::Edge te; deba@2290: deba@2290: SmartGraph::NodeMap nr(source); deba@2290: SmartGraph::EdgeMap er(source); deba@2290: deba@2290: ListGraph::NodeMap ncr(target); deba@2290: ListGraph::EdgeMap ecr(target); deba@2290: deba@2290: GraphCopy(target, source). deba@2290: nodeMap(tnm, snm).edgeMap(tem, sem). deba@2290: nodeRef(nr).edgeRef(er). deba@2290: nodeCrossRef(ncr).edgeCrossRef(ecr). deba@2290: node(tn, sn).edge(te, se).run(); deba@2290: deba@2290: for (SmartGraph::NodeIt it(source); it != INVALID; ++it) { deba@2290: check(ncr[nr[it]] == it, "Wrong copy."); deba@2290: check(snm[it] == tnm[nr[it]], "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) { deba@2290: check(ecr[er[it]] == it, "Wrong copy."); deba@2290: check(sem[it] == tem[er[it]], "Wrong copy."); deba@2290: check(nr[source.source(it)] == deba@2290: target.source(er[it]), "Wrong copy."); deba@2290: check(nr[source.target(it)] == deba@2290: target.target(er[it]), "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListGraph::NodeIt it(target); it != INVALID; ++it) { deba@2290: check(nr[ncr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListGraph::EdgeIt it(target); it != INVALID; ++it) { deba@2290: check(er[ecr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: check(tn == nr[sn], "Wrong copy."); deba@2290: check(te == er[se], "Wrong copy."); deba@2290: } deba@2290: deba@2290: void ugraph_copy_test() { deba@2290: const int nn = 10; deba@2290: deba@2290: SmartUGraph source; deba@2290: SmartUGraph::NodeMap snm(source); deba@2290: SmartUGraph::EdgeMap sem(source); deba@2290: SmartUGraph::UEdgeMap suem(source); deba@2290: SmartUGraph::Node sn = INVALID; deba@2290: SmartUGraph::Edge se = INVALID; deba@2290: SmartUGraph::UEdge sue = INVALID; deba@2290: deba@2344: std::vector snv; deba@2290: for (int i = 0; i < nn; ++i) { deba@2290: SmartUGraph::Node node = source.addNode(); deba@2290: snv.push_back(node); deba@2290: snm[node] = i * i; deba@2290: if (i == 0) sn = node; deba@2290: } deba@2290: deba@2290: for (int i = 0; i < nn; ++i) { deba@2290: for (int j = 0; j < nn; ++j) { deba@2290: SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]); deba@2290: suem[edge] = i * i + j * j; deba@2290: sem[source.direct(edge, true)] = i + j * j; deba@2290: sem[source.direct(edge, false)] = i * i + j; deba@2290: if (i == 0 && j == 0) se = source.direct(edge, true); deba@2290: if (i == 0 && j == 0) sue = edge; deba@2290: } deba@2290: } deba@2290: deba@2290: ListUGraph target; deba@2290: ListUGraph::NodeMap tnm(target); deba@2290: ListUGraph::EdgeMap tem(target); deba@2290: ListUGraph::UEdgeMap tuem(target); deba@2290: ListUGraph::Node tn; deba@2290: ListUGraph::Edge te; deba@2290: ListUGraph::UEdge tue; deba@2290: deba@2290: SmartUGraph::NodeMap nr(source); deba@2290: SmartUGraph::EdgeMap er(source); deba@2290: SmartUGraph::UEdgeMap uer(source); deba@2290: deba@2290: ListUGraph::NodeMap ncr(target); deba@2290: ListUGraph::EdgeMap ecr(target); deba@2290: ListUGraph::UEdgeMap uecr(target); deba@2290: deba@2290: UGraphCopy(target, source). deba@2290: nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem). deba@2290: nodeRef(nr).edgeRef(er).uEdgeRef(uer). deba@2290: nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr). deba@2290: node(tn, sn).edge(te, se).uEdge(tue, sue).run(); deba@2290: deba@2290: for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) { deba@2290: check(ncr[nr[it]] == it, "Wrong copy."); deba@2290: check(snm[it] == tnm[nr[it]], "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) { deba@2290: check(ecr[er[it]] == it, "Wrong copy."); deba@2290: check(sem[it] == tem[er[it]], "Wrong copy."); deba@2290: check(nr[source.source(it)] == deba@2290: target.source(er[it]), "Wrong copy."); deba@2290: check(nr[source.target(it)] == deba@2290: target.target(er[it]), "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) { deba@2290: check(uecr[uer[it]] == it, "Wrong copy."); deba@2290: check(suem[it] == tuem[uer[it]], "Wrong copy."); deba@2290: check(nr[source.source(it)] == target.source(uer[it]) || deba@2290: nr[source.source(it)] == target.target(uer[it]), deba@2290: "Wrong copy."); deba@2290: check(nr[source.target(it)] == target.source(uer[it]) || deba@2290: nr[source.target(it)] == target.target(uer[it]), deba@2290: "Wrong copy."); deba@2290: check((source.source(it) != source.target(it)) == deba@2290: (target.source(uer[it]) != target.target(uer[it])), deba@2290: "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListUGraph::NodeIt it(target); it != INVALID; ++it) { deba@2290: check(nr[ncr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) { deba@2290: check(er[ecr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) { deba@2290: check(uer[uecr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: check(tn == nr[sn], "Wrong copy."); deba@2290: check(te == er[se], "Wrong copy."); deba@2290: check(tue == uer[sue], "Wrong copy."); deba@2290: } deba@2290: deba@2290: void bpugraph_copy_test() { deba@2290: const int nn = 10; deba@2290: deba@2290: SmartBpUGraph source; deba@2290: SmartBpUGraph::ANodeMap sanm(source); deba@2290: SmartBpUGraph::BNodeMap sbnm(source); deba@2290: SmartBpUGraph::NodeMap snm(source); deba@2290: SmartBpUGraph::EdgeMap sem(source); deba@2290: SmartBpUGraph::UEdgeMap suem(source); deba@2290: SmartBpUGraph::Node sn = INVALID; deba@2290: SmartBpUGraph::Edge se = INVALID; deba@2290: SmartBpUGraph::UEdge sue = INVALID; deba@2290: deba@2290: std::vector sanv; deba@2290: for (int i = 0; i < nn; ++i) { deba@2290: SmartBpUGraph::Node node = source.addANode(); deba@2290: sanv.push_back(node); deba@2290: sanm[node] = i * i; deba@2290: snm[node] = i * i + i; deba@2290: if (i == 0) sn = node; deba@2290: } deba@2290: deba@2290: std::vector sbnv; deba@2290: for (int i = 0; i < nn; ++i) { deba@2290: SmartBpUGraph::Node node = source.addBNode(); deba@2290: sbnv.push_back(node); deba@2290: sbnm[node] = i * i - i; deba@2290: snm[node] = i * i + i + 1; deba@2290: } deba@2290: deba@2290: for (int i = 0; i < nn; ++i) { deba@2290: for (int j = 0; j < nn; ++j) { deba@2290: SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]); deba@2290: suem[edge] = i * i + j * j; deba@2290: sem[source.direct(edge, true)] = i + j * j; deba@2290: sem[source.direct(edge, false)] = i * i + j; deba@2290: if (i == 0 && j == 0) se = source.direct(edge, true); deba@2290: if (i == 0 && j == 0) sue = edge; deba@2290: } deba@2290: } deba@2290: deba@2290: ListBpUGraph target; deba@2290: ListBpUGraph::ANodeMap tanm(target); deba@2290: ListBpUGraph::BNodeMap tbnm(target); deba@2290: ListBpUGraph::NodeMap tnm(target); deba@2290: ListBpUGraph::EdgeMap tem(target); deba@2290: ListBpUGraph::UEdgeMap tuem(target); deba@2290: ListBpUGraph::Node tn; deba@2290: ListBpUGraph::Edge te; deba@2290: ListBpUGraph::UEdge tue; deba@2290: deba@2290: SmartBpUGraph::ANodeMap anr(source); deba@2290: SmartBpUGraph::BNodeMap bnr(source); deba@2290: SmartBpUGraph::NodeMap nr(source); deba@2290: SmartBpUGraph::EdgeMap er(source); deba@2290: SmartBpUGraph::UEdgeMap uer(source); deba@2290: deba@2290: ListBpUGraph::ANodeMap ancr(target); deba@2290: ListBpUGraph::BNodeMap bncr(target); deba@2290: ListBpUGraph::NodeMap ncr(target); deba@2290: ListBpUGraph::EdgeMap ecr(target); deba@2290: ListBpUGraph::UEdgeMap uecr(target); deba@2290: deba@2290: BpUGraphCopy(target, source). deba@2290: aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm). deba@2290: edgeMap(tem, sem).uEdgeMap(tuem, suem). deba@2290: aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer). deba@2290: aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr). deba@2290: edgeCrossRef(ecr).uEdgeCrossRef(uecr). deba@2290: node(tn, sn).edge(te, se).uEdge(tue, sue).run(); deba@2290: deba@2290: for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) { deba@2290: check(nr[it] == anr[it], "Wrong copy."); deba@2290: check(ancr[anr[it]] == it, "Wrong copy."); deba@2290: check(sanm[it] == tanm[anr[it]], "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) { deba@2290: check(nr[it] == bnr[it], "Wrong copy."); deba@2290: check(bncr[bnr[it]] == it, "Wrong copy."); deba@2290: check(sbnm[it] == tbnm[bnr[it]], "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) { deba@2290: check(ncr[nr[it]] == it, "Wrong copy."); deba@2290: check(snm[it] == tnm[nr[it]], "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) { deba@2290: check(ecr[er[it]] == it, "Wrong copy."); deba@2290: check(sem[it] == tem[er[it]], "Wrong copy."); deba@2290: check(nr[source.source(it)] == deba@2290: target.source(er[it]), "Wrong copy."); deba@2290: check(nr[source.target(it)] == deba@2290: target.target(er[it]), "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) { deba@2290: check(uecr[uer[it]] == it, "Wrong copy."); deba@2290: check(suem[it] == tuem[uer[it]], "Wrong copy."); deba@2290: check(nr[source.aNode(it)] == deba@2290: target.aNode(uer[it]), "Wrong copy."); deba@2290: check(nr[source.bNode(it)] == deba@2290: target.bNode(uer[it]), "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) { deba@2290: check(ancr[it] == ncr[it], "Wrong copy."); deba@2290: check(anr[ancr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) { deba@2290: check(bncr[it] == ncr[it], "Wrong copy."); deba@2290: check(bnr[bncr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) { deba@2290: check(nr[ncr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: deba@2290: for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) { deba@2290: check(er[ecr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) { deba@2290: check(uer[uecr[it]] == it, "Wrong copy."); deba@2290: } deba@2290: check(tn == nr[sn], "Wrong copy."); deba@2290: check(te == er[se], "Wrong copy."); deba@2290: check(tue == uer[sue], "Wrong copy."); deba@2290: } deba@2290: deba@2290: int main() { deba@2290: graph_copy_test(); deba@2290: ugraph_copy_test(); deba@2290: bpugraph_copy_test(); deba@2290: deba@2290: return 0; deba@2290: }