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: * deba@200: * Copyright (C) 2003-2008 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 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: deba@200: void digraph_copy_test() { deba@200: const int nn = 10; deba@200: kpeter@731: // 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: } deba@200: kpeter@731: // Test digraph copy deba@200: ListDigraph to; deba@200: ListDigraph::NodeMap tnm(to); deba@200: ListDigraph::ArcMap tam(to); deba@200: ListDigraph::Node tn; deba@200: ListDigraph::Arc ta; deba@200: deba@200: SmartDigraph::NodeMap nr(from); deba@200: SmartDigraph::ArcMap er(from); deba@200: deba@200: ListDigraph::NodeMap ncr(to); deba@200: ListDigraph::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@731: kpeter@731: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@731: 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: deba@200: for (ListDigraph::NodeIt it(to); it != INVALID; ++it) { deba@200: check(nr[ncr[it]] == it, "Wrong copy."); deba@200: } deba@200: deba@200: for (ListDigraph::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@731: kpeter@731: // Test repeated copy kpeter@731: digraphCopy(from, to).run(); kpeter@731: kpeter@731: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@731: check(countArcs(from) == countArcs(to), "Wrong copy."); deba@200: } deba@200: deba@200: void graph_copy_test() { deba@200: const int nn = 10; deba@200: kpeter@731: // 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@731: // Test graph copy deba@200: ListGraph to; deba@200: ListGraph::NodeMap tnm(to); deba@200: ListGraph::ArcMap tam(to); deba@200: ListGraph::EdgeMap tem(to); deba@200: ListGraph::Node tn; deba@200: ListGraph::Arc ta; deba@200: ListGraph::Edge te; deba@200: deba@200: SmartGraph::NodeMap nr(from); deba@200: SmartGraph::ArcMap ar(from); deba@200: SmartGraph::EdgeMap er(from); deba@200: deba@200: ListGraph::NodeMap ncr(to); deba@200: ListGraph::ArcMap acr(to); deba@200: ListGraph::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@731: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@731: check(countEdges(from) == countEdges(to), "Wrong copy."); kpeter@731: check(countArcs(from) == countArcs(to), "Wrong copy."); kpeter@731: 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: deba@200: for (ListGraph::NodeIt it(to); it != INVALID; ++it) { deba@200: check(nr[ncr[it]] == it, "Wrong copy."); deba@200: } deba@200: deba@200: for (ListGraph::ArcIt it(to); it != INVALID; ++it) { deba@200: check(ar[acr[it]] == it, "Wrong copy."); deba@200: } deba@200: for (ListGraph::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@731: kpeter@731: // Test repeated copy kpeter@731: graphCopy(from, to).run(); kpeter@731: kpeter@731: check(countNodes(from) == countNodes(to), "Wrong copy."); kpeter@731: check(countEdges(from) == countEdges(to), "Wrong copy."); kpeter@731: check(countArcs(from) == countArcs(to), "Wrong copy."); deba@200: } deba@200: deba@200: deba@200: int main() { deba@200: digraph_copy_test(); deba@200: graph_copy_test(); deba@200: alpar@209: return 0; deba@200: }