test/graph_copy_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 24 Aug 2012 16:10:31 +0200
changeset 994 20ae244b4779
parent 893 d395358592df
child 1022 523e45e37e52
permissions -rw-r--r--
Merge bugfix #447
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/smart_graph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/static_graph.h>
    22 #include <lemon/lgf_reader.h>
    23 #include <lemon/error.h>
    24 
    25 #include "test_tools.h"
    26 
    27 using namespace std;
    28 using namespace lemon;
    29 
    30 template <typename GR>
    31 void digraph_copy_test() {
    32   const int nn = 10;
    33 
    34   // Build a digraph
    35   SmartDigraph from;
    36   SmartDigraph::NodeMap<int> fnm(from);
    37   SmartDigraph::ArcMap<int> fam(from);
    38   SmartDigraph::Node fn = INVALID;
    39   SmartDigraph::Arc fa = INVALID;
    40 
    41   std::vector<SmartDigraph::Node> fnv;
    42   for (int i = 0; i < nn; ++i) {
    43     SmartDigraph::Node node = from.addNode();
    44     fnv.push_back(node);
    45     fnm[node] = i * i;
    46     if (i == 0) fn = node;
    47   }
    48 
    49   for (int i = 0; i < nn; ++i) {
    50     for (int j = 0; j < nn; ++j) {
    51       SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);
    52       fam[arc] = i + j * j;
    53       if (i == 0 && j == 0) fa = arc;
    54     }
    55   }
    56   
    57   // Test digraph copy
    58   GR to;
    59   typename GR::template NodeMap<int> tnm(to);
    60   typename GR::template ArcMap<int> tam(to);
    61   typename GR::Node tn;
    62   typename GR::Arc ta;
    63 
    64   SmartDigraph::NodeMap<typename GR::Node> nr(from);
    65   SmartDigraph::ArcMap<typename GR::Arc> er(from);
    66 
    67   typename GR::template NodeMap<SmartDigraph::Node> ncr(to);
    68   typename GR::template ArcMap<SmartDigraph::Arc> ecr(to);
    69 
    70   digraphCopy(from, to).
    71     nodeMap(fnm, tnm).arcMap(fam, tam).
    72     nodeRef(nr).arcRef(er).
    73     nodeCrossRef(ncr).arcCrossRef(ecr).
    74     node(fn, tn).arc(fa, ta).run();
    75   
    76   check(countNodes(from) == countNodes(to), "Wrong copy.");
    77   check(countArcs(from) == countArcs(to), "Wrong copy.");
    78 
    79   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
    80     check(ncr[nr[it]] == it, "Wrong copy.");
    81     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
    82   }
    83 
    84   for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
    85     check(ecr[er[it]] == it, "Wrong copy.");
    86     check(fam[it] == tam[er[it]], "Wrong copy.");
    87     check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
    88     check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
    89   }
    90 
    91   for (typename GR::NodeIt it(to); it != INVALID; ++it) {
    92     check(nr[ncr[it]] == it, "Wrong copy.");
    93   }
    94 
    95   for (typename GR::ArcIt it(to); it != INVALID; ++it) {
    96     check(er[ecr[it]] == it, "Wrong copy.");
    97   }
    98   check(tn == nr[fn], "Wrong copy.");
    99   check(ta == er[fa], "Wrong copy.");
   100 
   101   // Test repeated copy
   102   digraphCopy(from, to).run();
   103   
   104   check(countNodes(from) == countNodes(to), "Wrong copy.");
   105   check(countArcs(from) == countArcs(to), "Wrong copy.");
   106 }
   107 
   108 template <typename GR>
   109 void graph_copy_test() {
   110   const int nn = 10;
   111 
   112   // Build a graph
   113   SmartGraph from;
   114   SmartGraph::NodeMap<int> fnm(from);
   115   SmartGraph::ArcMap<int> fam(from);
   116   SmartGraph::EdgeMap<int> fem(from);
   117   SmartGraph::Node fn = INVALID;
   118   SmartGraph::Arc fa = INVALID;
   119   SmartGraph::Edge fe = INVALID;
   120 
   121   std::vector<SmartGraph::Node> fnv;
   122   for (int i = 0; i < nn; ++i) {
   123     SmartGraph::Node node = from.addNode();
   124     fnv.push_back(node);
   125     fnm[node] = i * i;
   126     if (i == 0) fn = node;
   127   }
   128 
   129   for (int i = 0; i < nn; ++i) {
   130     for (int j = 0; j < nn; ++j) {
   131       SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
   132       fem[edge] = i * i + j * j;
   133       fam[from.direct(edge, true)] = i + j * j;
   134       fam[from.direct(edge, false)] = i * i + j;
   135       if (i == 0 && j == 0) fa = from.direct(edge, true);
   136       if (i == 0 && j == 0) fe = edge;
   137     }
   138   }
   139 
   140   // Test graph copy
   141   GR to;
   142   typename GR::template NodeMap<int> tnm(to);
   143   typename GR::template ArcMap<int> tam(to);
   144   typename GR::template EdgeMap<int> tem(to);
   145   typename GR::Node tn;
   146   typename GR::Arc ta;
   147   typename GR::Edge te;
   148 
   149   SmartGraph::NodeMap<typename GR::Node> nr(from);
   150   SmartGraph::ArcMap<typename GR::Arc> ar(from);
   151   SmartGraph::EdgeMap<typename GR::Edge> er(from);
   152 
   153   typename GR::template NodeMap<SmartGraph::Node> ncr(to);
   154   typename GR::template ArcMap<SmartGraph::Arc> acr(to);
   155   typename GR::template EdgeMap<SmartGraph::Edge> ecr(to);
   156 
   157   graphCopy(from, to).
   158     nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).
   159     nodeRef(nr).arcRef(ar).edgeRef(er).
   160     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
   161     node(fn, tn).arc(fa, ta).edge(fe, te).run();
   162 
   163   check(countNodes(from) == countNodes(to), "Wrong copy.");
   164   check(countEdges(from) == countEdges(to), "Wrong copy.");
   165   check(countArcs(from) == countArcs(to), "Wrong copy.");
   166 
   167   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
   168     check(ncr[nr[it]] == it, "Wrong copy.");
   169     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
   170   }
   171 
   172   for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
   173     check(acr[ar[it]] == it, "Wrong copy.");
   174     check(fam[it] == tam[ar[it]], "Wrong copy.");
   175     check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
   176     check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
   177   }
   178 
   179   for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
   180     check(ecr[er[it]] == it, "Wrong copy.");
   181     check(fem[it] == tem[er[it]], "Wrong copy.");
   182     check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
   183           "Wrong copy.");
   184     check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
   185           "Wrong copy.");
   186     check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
   187           "Wrong copy.");
   188   }
   189 
   190   for (typename GR::NodeIt it(to); it != INVALID; ++it) {
   191     check(nr[ncr[it]] == it, "Wrong copy.");
   192   }
   193 
   194   for (typename GR::ArcIt it(to); it != INVALID; ++it) {
   195     check(ar[acr[it]] == it, "Wrong copy.");
   196   }
   197   for (typename GR::EdgeIt it(to); it != INVALID; ++it) {
   198     check(er[ecr[it]] == it, "Wrong copy.");
   199   }
   200   check(tn == nr[fn], "Wrong copy.");
   201   check(ta == ar[fa], "Wrong copy.");
   202   check(te == er[fe], "Wrong copy.");
   203 
   204   // Test repeated copy
   205   graphCopy(from, to).run();
   206   
   207   check(countNodes(from) == countNodes(to), "Wrong copy.");
   208   check(countEdges(from) == countEdges(to), "Wrong copy.");
   209   check(countArcs(from) == countArcs(to), "Wrong copy.");
   210 }
   211 
   212 
   213 int main() {
   214   digraph_copy_test<SmartDigraph>();
   215   digraph_copy_test<ListDigraph>();
   216   digraph_copy_test<StaticDigraph>();
   217   graph_copy_test<SmartGraph>();
   218   graph_copy_test<ListGraph>();
   219 
   220   return 0;
   221 }