test/graph_copy_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 12:47:13 +0100
changeset 789 8ddb7deabab9
parent 282 dc9e8d2c0df9
child 893 d395358592df
permissions -rw-r--r--
Map utility functions (#320)
     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/lgf_reader.h>
    22 #include <lemon/error.h>
    23 
    24 #include "test_tools.h"
    25 
    26 using namespace std;
    27 using namespace lemon;
    28 
    29 void digraph_copy_test() {
    30   const int nn = 10;
    31 
    32   SmartDigraph from;
    33   SmartDigraph::NodeMap<int> fnm(from);
    34   SmartDigraph::ArcMap<int> fam(from);
    35   SmartDigraph::Node fn = INVALID;
    36   SmartDigraph::Arc fa = INVALID;
    37 
    38   std::vector<SmartDigraph::Node> fnv;
    39   for (int i = 0; i < nn; ++i) {
    40     SmartDigraph::Node node = from.addNode();
    41     fnv.push_back(node);
    42     fnm[node] = i * i;
    43     if (i == 0) fn = node;
    44   }
    45 
    46   for (int i = 0; i < nn; ++i) {
    47     for (int j = 0; j < nn; ++j) {
    48       SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);
    49       fam[arc] = i + j * j;
    50       if (i == 0 && j == 0) fa = arc;
    51     }
    52   }
    53 
    54   ListDigraph to;
    55   ListDigraph::NodeMap<int> tnm(to);
    56   ListDigraph::ArcMap<int> tam(to);
    57   ListDigraph::Node tn;
    58   ListDigraph::Arc ta;
    59 
    60   SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
    61   SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
    62 
    63   ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
    64   ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
    65 
    66   digraphCopy(from, to).
    67     nodeMap(fnm, tnm).arcMap(fam, tam).
    68     nodeRef(nr).arcRef(er).
    69     nodeCrossRef(ncr).arcCrossRef(ecr).
    70     node(fn, tn).arc(fa, ta).run();
    71 
    72   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
    73     check(ncr[nr[it]] == it, "Wrong copy.");
    74     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
    75   }
    76 
    77   for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
    78     check(ecr[er[it]] == it, "Wrong copy.");
    79     check(fam[it] == tam[er[it]], "Wrong copy.");
    80     check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
    81     check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
    82   }
    83 
    84   for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
    85     check(nr[ncr[it]] == it, "Wrong copy.");
    86   }
    87 
    88   for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
    89     check(er[ecr[it]] == it, "Wrong copy.");
    90   }
    91   check(tn == nr[fn], "Wrong copy.");
    92   check(ta == er[fa], "Wrong copy.");
    93 }
    94 
    95 void graph_copy_test() {
    96   const int nn = 10;
    97 
    98   SmartGraph from;
    99   SmartGraph::NodeMap<int> fnm(from);
   100   SmartGraph::ArcMap<int> fam(from);
   101   SmartGraph::EdgeMap<int> fem(from);
   102   SmartGraph::Node fn = INVALID;
   103   SmartGraph::Arc fa = INVALID;
   104   SmartGraph::Edge fe = INVALID;
   105 
   106   std::vector<SmartGraph::Node> fnv;
   107   for (int i = 0; i < nn; ++i) {
   108     SmartGraph::Node node = from.addNode();
   109     fnv.push_back(node);
   110     fnm[node] = i * i;
   111     if (i == 0) fn = node;
   112   }
   113 
   114   for (int i = 0; i < nn; ++i) {
   115     for (int j = 0; j < nn; ++j) {
   116       SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
   117       fem[edge] = i * i + j * j;
   118       fam[from.direct(edge, true)] = i + j * j;
   119       fam[from.direct(edge, false)] = i * i + j;
   120       if (i == 0 && j == 0) fa = from.direct(edge, true);
   121       if (i == 0 && j == 0) fe = edge;
   122     }
   123   }
   124 
   125   ListGraph to;
   126   ListGraph::NodeMap<int> tnm(to);
   127   ListGraph::ArcMap<int> tam(to);
   128   ListGraph::EdgeMap<int> tem(to);
   129   ListGraph::Node tn;
   130   ListGraph::Arc ta;
   131   ListGraph::Edge te;
   132 
   133   SmartGraph::NodeMap<ListGraph::Node> nr(from);
   134   SmartGraph::ArcMap<ListGraph::Arc> ar(from);
   135   SmartGraph::EdgeMap<ListGraph::Edge> er(from);
   136 
   137   ListGraph::NodeMap<SmartGraph::Node> ncr(to);
   138   ListGraph::ArcMap<SmartGraph::Arc> acr(to);
   139   ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
   140 
   141   graphCopy(from, to).
   142     nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).
   143     nodeRef(nr).arcRef(ar).edgeRef(er).
   144     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
   145     node(fn, tn).arc(fa, ta).edge(fe, te).run();
   146 
   147   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
   148     check(ncr[nr[it]] == it, "Wrong copy.");
   149     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
   150   }
   151 
   152   for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
   153     check(acr[ar[it]] == it, "Wrong copy.");
   154     check(fam[it] == tam[ar[it]], "Wrong copy.");
   155     check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
   156     check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
   157   }
   158 
   159   for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
   160     check(ecr[er[it]] == it, "Wrong copy.");
   161     check(fem[it] == tem[er[it]], "Wrong copy.");
   162     check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
   163           "Wrong copy.");
   164     check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
   165           "Wrong copy.");
   166     check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
   167           "Wrong copy.");
   168   }
   169 
   170   for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
   171     check(nr[ncr[it]] == it, "Wrong copy.");
   172   }
   173 
   174   for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
   175     check(ar[acr[it]] == it, "Wrong copy.");
   176   }
   177   for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
   178     check(er[ecr[it]] == it, "Wrong copy.");
   179   }
   180   check(tn == nr[fn], "Wrong copy.");
   181   check(ta == ar[fa], "Wrong copy.");
   182   check(te == er[fe], "Wrong copy.");
   183 }
   184 
   185 
   186 int main() {
   187   digraph_copy_test();
   188   graph_copy_test();
   189 
   190   return 0;
   191 }