alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2391:  * Copyright (C) 2003-2007
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 <lemon/smart_graph.h>
deba@2290: #include <lemon/list_graph.h>
deba@2290: #include <lemon/graph_reader.h>
deba@2290: #include <lemon/graph_utils.h>
deba@2290: #include <lemon/error.h>
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<int> snm(source);
deba@2290:   SmartGraph::EdgeMap<int> sem(source);
deba@2290:   SmartGraph::Node sn = INVALID;
deba@2290:   SmartGraph::Edge se = INVALID;
deba@2290: 
deba@2290:   std::vector<SmartGraph::Node> 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<int> tnm(target);
deba@2290:   ListGraph::EdgeMap<int> tem(target);
deba@2290:   ListGraph::Node tn;
deba@2290:   ListGraph::Edge te;
deba@2290: 
deba@2290:   SmartGraph::NodeMap<ListGraph::Node> nr(source);
deba@2290:   SmartGraph::EdgeMap<ListGraph::Edge> er(source);
deba@2290: 
deba@2290:   ListGraph::NodeMap<SmartGraph::Node> ncr(target);
deba@2290:   ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);
deba@2290: 
deba@2290:   GraphCopy<ListGraph, SmartGraph>(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<int> snm(source);
deba@2290:   SmartUGraph::EdgeMap<int> sem(source);
deba@2290:   SmartUGraph::UEdgeMap<int> 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<SmartUGraph::Node> 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<int> tnm(target);
deba@2290:   ListUGraph::EdgeMap<int> tem(target);
deba@2290:   ListUGraph::UEdgeMap<int> tuem(target);
deba@2290:   ListUGraph::Node tn;
deba@2290:   ListUGraph::Edge te;
deba@2290:   ListUGraph::UEdge tue;
deba@2290: 
deba@2290:   SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
deba@2290:   SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
deba@2290:   SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);
deba@2290: 
deba@2290:   ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
deba@2290:   ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
deba@2290:   ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);
deba@2290: 
deba@2290:   UGraphCopy<ListUGraph, SmartUGraph>(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<int> sanm(source);
deba@2290:   SmartBpUGraph::BNodeMap<int> sbnm(source);
deba@2290:   SmartBpUGraph::NodeMap<int> snm(source);
deba@2290:   SmartBpUGraph::EdgeMap<int> sem(source);
deba@2290:   SmartBpUGraph::UEdgeMap<int> 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<SmartBpUGraph::Node> 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<SmartBpUGraph::Node> 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<int> tanm(target);
deba@2290:   ListBpUGraph::BNodeMap<int> tbnm(target);
deba@2290:   ListBpUGraph::NodeMap<int> tnm(target);
deba@2290:   ListBpUGraph::EdgeMap<int> tem(target);
deba@2290:   ListBpUGraph::UEdgeMap<int> tuem(target);
deba@2290:   ListBpUGraph::Node tn;
deba@2290:   ListBpUGraph::Edge te;
deba@2290:   ListBpUGraph::UEdge tue;
deba@2290: 
deba@2290:   SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);
deba@2290:   SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);
deba@2290:   SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);
deba@2290:   SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);
deba@2290:   SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);
deba@2290: 
deba@2290:   ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);
deba@2290:   ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);
deba@2290:   ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);
deba@2290:   ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);
deba@2290:   ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);
deba@2290: 
deba@2290:   BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(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: }