alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@200: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. deba@200: * alpar@440: * Copyright (C) 2003-2009 deba@200: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@200: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@200: * deba@200: * Permission to use, modify and distribute this software is granted deba@200: * provided that this copyright notice appears in all copies. For deba@200: * precise terms see the accompanying LICENSE file. deba@200: * deba@200: * This software is provided "AS IS" with no warranty of any kind, deba@200: * express or implied, and with no claim as to its suitability for any deba@200: * purpose. deba@200: * deba@200: */ deba@200: deba@200: #include deba@200: #include kpeter@894: #include deba@200: #include deba@200: #include deba@200: deba@200: #include "test_tools.h" deba@200: deba@200: using namespace std; deba@200: using namespace lemon; deba@200: kpeter@894: template deba@200: void digraph_copy_test() { deba@200: const int nn = 10; deba@200: kpeter@890: // Build a digraph deba@200: SmartDigraph from; deba@200: SmartDigraph::NodeMap fnm(from); deba@200: SmartDigraph::ArcMap fam(from); deba@200: SmartDigraph::Node fn = INVALID; deba@200: SmartDigraph::Arc fa = INVALID; deba@200: deba@200: std::vector fnv; deba@200: for (int i = 0; i < nn; ++i) { deba@200: SmartDigraph::Node node = from.addNode(); deba@200: fnv.push_back(node); deba@200: fnm[node] = i * i; deba@200: if (i == 0) fn = node; deba@200: } deba@200: deba@200: for (int i = 0; i < nn; ++i) { deba@200: for (int j = 0; j < nn; ++j) { deba@200: SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]); deba@200: fam[arc] = i + j * j; deba@200: if (i == 0 && j == 0) fa = arc; deba@200: } deba@200: } kpeter@894: kpeter@894: // Test digraph copy kpeter@894: GR to; kpeter@894: typename GR::template NodeMap tnm(to); kpeter@894: typename GR::template ArcMap tam(to); kpeter@894: typename GR::Node tn; kpeter@894: typename GR::Arc ta; deba@200: kpeter@894: SmartDigraph::NodeMap nr(from); kpeter@894: SmartDigraph::ArcMap er(from); deba@200: kpeter@894: typename GR::template NodeMap ncr(to); kpeter@894: typename GR::template ArcMap ecr(to); deba@200: kpeter@282: digraphCopy(from, to). kpeter@282: nodeMap(fnm, tnm).arcMap(fam, tam). deba@200: nodeRef(nr).arcRef(er). deba@200: nodeCrossRef(ncr).arcCrossRef(ecr). kpeter@282: node(fn, tn).arc(fa, ta).run(); kpeter@890: kpeter@890: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@890: check(countArcs(from) == countArcs(to), "Wrong copy."); deba@200: deba@200: for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { deba@200: check(ncr[nr[it]] == it, "Wrong copy."); deba@200: check(fnm[it] == tnm[nr[it]], "Wrong copy."); deba@200: } deba@200: deba@200: for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) { deba@200: check(ecr[er[it]] == it, "Wrong copy."); deba@200: check(fam[it] == tam[er[it]], "Wrong copy."); deba@200: check(nr[from.source(it)] == to.source(er[it]), "Wrong copy."); deba@200: check(nr[from.target(it)] == to.target(er[it]), "Wrong copy."); deba@200: } deba@200: kpeter@894: for (typename GR::NodeIt it(to); it != INVALID; ++it) { deba@200: check(nr[ncr[it]] == it, "Wrong copy."); deba@200: } deba@200: kpeter@894: for (typename GR::ArcIt it(to); it != INVALID; ++it) { deba@200: check(er[ecr[it]] == it, "Wrong copy."); deba@200: } deba@200: check(tn == nr[fn], "Wrong copy."); deba@200: check(ta == er[fa], "Wrong copy."); kpeter@890: kpeter@890: // Test repeated copy kpeter@890: digraphCopy(from, to).run(); kpeter@890: kpeter@890: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@890: check(countArcs(from) == countArcs(to), "Wrong copy."); deba@200: } deba@200: kpeter@894: template deba@200: void graph_copy_test() { deba@200: const int nn = 10; deba@200: kpeter@890: // Build a graph deba@200: SmartGraph from; deba@200: SmartGraph::NodeMap fnm(from); deba@200: SmartGraph::ArcMap fam(from); deba@200: SmartGraph::EdgeMap fem(from); deba@200: SmartGraph::Node fn = INVALID; deba@200: SmartGraph::Arc fa = INVALID; deba@200: SmartGraph::Edge fe = INVALID; deba@200: deba@200: std::vector fnv; deba@200: for (int i = 0; i < nn; ++i) { deba@200: SmartGraph::Node node = from.addNode(); deba@200: fnv.push_back(node); deba@200: fnm[node] = i * i; deba@200: if (i == 0) fn = node; deba@200: } deba@200: deba@200: for (int i = 0; i < nn; ++i) { deba@200: for (int j = 0; j < nn; ++j) { deba@200: SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]); deba@200: fem[edge] = i * i + j * j; deba@200: fam[from.direct(edge, true)] = i + j * j; deba@200: fam[from.direct(edge, false)] = i * i + j; deba@200: if (i == 0 && j == 0) fa = from.direct(edge, true); deba@200: if (i == 0 && j == 0) fe = edge; deba@200: } deba@200: } alpar@209: kpeter@890: // Test graph copy kpeter@894: GR to; kpeter@894: typename GR::template NodeMap tnm(to); kpeter@894: typename GR::template ArcMap tam(to); kpeter@894: typename GR::template EdgeMap tem(to); kpeter@894: typename GR::Node tn; kpeter@894: typename GR::Arc ta; kpeter@894: typename GR::Edge te; deba@200: kpeter@894: SmartGraph::NodeMap nr(from); kpeter@894: SmartGraph::ArcMap ar(from); kpeter@894: SmartGraph::EdgeMap er(from); deba@200: kpeter@894: typename GR::template NodeMap ncr(to); kpeter@894: typename GR::template ArcMap acr(to); kpeter@894: typename GR::template EdgeMap ecr(to); deba@200: kpeter@282: graphCopy(from, to). kpeter@282: nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem). deba@200: nodeRef(nr).arcRef(ar).edgeRef(er). deba@200: nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). kpeter@282: node(fn, tn).arc(fa, ta).edge(fe, te).run(); deba@200: kpeter@890: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@890: check(countEdges(from) == countEdges(to), "Wrong copy."); kpeter@890: check(countArcs(from) == countArcs(to), "Wrong copy."); kpeter@890: deba@200: for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { deba@200: check(ncr[nr[it]] == it, "Wrong copy."); deba@200: check(fnm[it] == tnm[nr[it]], "Wrong copy."); deba@200: } deba@200: deba@200: for (SmartGraph::ArcIt it(from); it != INVALID; ++it) { deba@200: check(acr[ar[it]] == it, "Wrong copy."); deba@200: check(fam[it] == tam[ar[it]], "Wrong copy."); deba@200: check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy."); deba@200: check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy."); deba@200: } deba@200: deba@200: for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) { deba@200: check(ecr[er[it]] == it, "Wrong copy."); deba@200: check(fem[it] == tem[er[it]], "Wrong copy."); alpar@209: check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]), alpar@209: "Wrong copy."); alpar@209: check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]), alpar@209: "Wrong copy."); alpar@209: check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])), alpar@209: "Wrong copy."); deba@200: } deba@200: kpeter@894: for (typename GR::NodeIt it(to); it != INVALID; ++it) { deba@200: check(nr[ncr[it]] == it, "Wrong copy."); deba@200: } deba@200: kpeter@894: for (typename GR::ArcIt it(to); it != INVALID; ++it) { deba@200: check(ar[acr[it]] == it, "Wrong copy."); deba@200: } kpeter@894: for (typename GR::EdgeIt it(to); it != INVALID; ++it) { deba@200: check(er[ecr[it]] == it, "Wrong copy."); deba@200: } deba@200: check(tn == nr[fn], "Wrong copy."); deba@200: check(ta == ar[fa], "Wrong copy."); deba@200: check(te == er[fe], "Wrong copy."); kpeter@890: kpeter@890: // Test repeated copy kpeter@890: graphCopy(from, to).run(); kpeter@890: kpeter@890: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@890: check(countEdges(from) == countEdges(to), "Wrong copy."); kpeter@890: check(countArcs(from) == countArcs(to), "Wrong copy."); deba@200: } deba@200: deba@1022: template deba@1022: void bpgraph_copy_test() { deba@1022: const int nn = 10; deba@1022: deba@1022: // Build a graph deba@1022: SmartBpGraph from; deba@1022: SmartBpGraph::NodeMap fnm(from); deba@1022: SmartBpGraph::RedMap frnm(from); deba@1022: SmartBpGraph::BlueMap fbnm(from); deba@1022: SmartBpGraph::ArcMap fam(from); deba@1022: SmartBpGraph::EdgeMap fem(from); deba@1022: SmartBpGraph::Node fn = INVALID; deba@1022: SmartBpGraph::Arc fa = INVALID; deba@1022: SmartBpGraph::Edge fe = INVALID; deba@1022: deba@1022: std::vector frnv; deba@1022: for (int i = 0; i < nn; ++i) { deba@1022: SmartBpGraph::Node node = from.addRedNode(); deba@1022: frnv.push_back(node); deba@1022: fnm[node] = i * i; deba@1022: frnm[node] = i + i; deba@1022: if (i == 0) fn = node; deba@1022: } deba@1022: deba@1022: std::vector fbnv; deba@1022: for (int i = 0; i < nn; ++i) { deba@1022: SmartBpGraph::Node node = from.addBlueNode(); deba@1022: fbnv.push_back(node); deba@1022: fnm[node] = i * i; deba@1022: fbnm[node] = i + i; deba@1022: } deba@1022: deba@1022: for (int i = 0; i < nn; ++i) { deba@1022: for (int j = 0; j < nn; ++j) { deba@1022: SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]); deba@1022: fem[edge] = i * i + j * j; deba@1022: fam[from.direct(edge, true)] = i + j * j; deba@1022: fam[from.direct(edge, false)] = i * i + j; deba@1022: if (i == 0 && j == 0) fa = from.direct(edge, true); deba@1022: if (i == 0 && j == 0) fe = edge; deba@1022: } deba@1022: } deba@1022: deba@1022: // Test graph copy deba@1022: GR to; deba@1022: typename GR::template NodeMap tnm(to); deba@1022: typename GR::template RedMap trnm(to); deba@1022: typename GR::template BlueMap tbnm(to); deba@1022: typename GR::template ArcMap tam(to); deba@1022: typename GR::template EdgeMap tem(to); deba@1022: typename GR::Node tn; deba@1022: typename GR::Arc ta; deba@1022: typename GR::Edge te; deba@1022: deba@1022: SmartBpGraph::NodeMap nr(from); deba@1022: SmartBpGraph::RedMap rnr(from); deba@1022: SmartBpGraph::BlueMap bnr(from); deba@1022: SmartBpGraph::ArcMap ar(from); deba@1022: SmartBpGraph::EdgeMap er(from); deba@1022: deba@1022: typename GR::template NodeMap ncr(to); deba@1022: typename GR::template RedMap rncr(to); deba@1022: typename GR::template BlueMap bncr(to); deba@1022: typename GR::template ArcMap acr(to); deba@1022: typename GR::template EdgeMap ecr(to); deba@1022: deba@1022: bpGraphCopy(from, to). deba@1022: nodeMap(fnm, tnm).redMap(frnm, trnm).blueMap(fbnm, tbnm). deba@1022: arcMap(fam, tam).edgeMap(fem, tem). deba@1022: nodeRef(nr).redRef(rnr).blueRef(bnr). deba@1022: arcRef(ar).edgeRef(er). deba@1022: nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr). deba@1022: arcCrossRef(acr).edgeCrossRef(ecr). deba@1022: node(fn, tn).arc(fa, ta).edge(fe, te).run(); deba@1022: deba@1022: check(countNodes(from) == countNodes(to), "Wrong copy."); deba@1022: check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); deba@1022: check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); deba@1022: check(countEdges(from) == countEdges(to), "Wrong copy."); deba@1022: check(countArcs(from) == countArcs(to), "Wrong copy."); deba@1022: deba@1022: for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) { deba@1022: check(ncr[nr[it]] == it, "Wrong copy."); deba@1022: check(fnm[it] == tnm[nr[it]], "Wrong copy."); deba@1022: if (from.red(it)) { deba@1022: check(rnr[it] == nr[it], "Wrong copy."); deba@1022: check(rncr[rnr[it]] == it, "Wrong copy."); deba@1022: check(frnm[it] == trnm[rnr[it]], "Wrong copy."); deba@1022: check(to.red(rnr[it]), "Wrong copy."); deba@1022: } else { deba@1022: check(bnr[it] == nr[it], "Wrong copy."); deba@1022: check(bncr[bnr[it]] == it, "Wrong copy."); deba@1022: check(fbnm[it] == tbnm[bnr[it]], "Wrong copy."); deba@1022: check(to.blue(bnr[it]), "Wrong copy."); deba@1022: } deba@1022: } deba@1022: deba@1022: for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) { deba@1022: check(acr[ar[it]] == it, "Wrong copy."); deba@1022: check(fam[it] == tam[ar[it]], "Wrong copy."); deba@1022: check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy."); deba@1022: check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy."); deba@1022: } deba@1022: deba@1022: for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) { deba@1022: check(ecr[er[it]] == it, "Wrong copy."); deba@1022: check(fem[it] == tem[er[it]], "Wrong copy."); deba@1022: check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]), deba@1022: "Wrong copy."); deba@1022: check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]), deba@1022: "Wrong copy."); deba@1022: check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])), deba@1022: "Wrong copy."); deba@1022: } deba@1022: deba@1022: for (typename GR::NodeIt it(to); it != INVALID; ++it) { deba@1022: check(nr[ncr[it]] == it, "Wrong copy."); deba@1022: } deba@1022: for (typename GR::RedIt it(to); it != INVALID; ++it) { deba@1022: check(rncr[it] == ncr[it], "Wrong copy."); deba@1022: check(rnr[rncr[it]] == it, "Wrong copy."); deba@1022: } deba@1022: for (typename GR::BlueIt it(to); it != INVALID; ++it) { deba@1022: check(bncr[it] == ncr[it], "Wrong copy."); deba@1022: check(bnr[bncr[it]] == it, "Wrong copy."); deba@1022: } deba@1022: for (typename GR::ArcIt it(to); it != INVALID; ++it) { deba@1022: check(ar[acr[it]] == it, "Wrong copy."); deba@1022: } deba@1022: for (typename GR::EdgeIt it(to); it != INVALID; ++it) { deba@1022: check(er[ecr[it]] == it, "Wrong copy."); deba@1022: } deba@1022: check(tn == nr[fn], "Wrong copy."); deba@1022: check(ta == ar[fa], "Wrong copy."); deba@1022: check(te == er[fe], "Wrong copy."); deba@1022: deba@1022: // Test repeated copy deba@1022: bpGraphCopy(from, to).run(); deba@1022: deba@1022: check(countNodes(from) == countNodes(to), "Wrong copy."); deba@1022: check(countRedNodes(from) == countRedNodes(to), "Wrong copy."); deba@1022: check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy."); deba@1022: check(countEdges(from) == countEdges(to), "Wrong copy."); deba@1022: check(countArcs(from) == countArcs(to), "Wrong copy."); deba@1022: } deba@1022: deba@200: deba@200: int main() { kpeter@894: digraph_copy_test(); kpeter@894: digraph_copy_test(); kpeter@894: digraph_copy_test(); kpeter@894: graph_copy_test(); kpeter@894: graph_copy_test(); deba@1022: bpgraph_copy_test(); deba@1022: bpgraph_copy_test(); deba@200: alpar@209: return 0; deba@200: }