test/graph_copy_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 21 Sep 2010 06:00:18 +0200
branch1.0
changeset 1001 7d26a96745f7
parent 282 dc9e8d2c0df9
child 984 9f22c22fe227
child 1078 c59bdcc8e33e
permissions -rw-r--r--
Update NEWS file
     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-2008
     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   // Build a digraph
    33   SmartDigraph from;
    34   SmartDigraph::NodeMap<int> fnm(from);
    35   SmartDigraph::ArcMap<int> fam(from);
    36   SmartDigraph::Node fn = INVALID;
    37   SmartDigraph::Arc fa = INVALID;
    38 
    39   std::vector<SmartDigraph::Node> fnv;
    40   for (int i = 0; i < nn; ++i) {
    41     SmartDigraph::Node node = from.addNode();
    42     fnv.push_back(node);
    43     fnm[node] = i * i;
    44     if (i == 0) fn = node;
    45   }
    46 
    47   for (int i = 0; i < nn; ++i) {
    48     for (int j = 0; j < nn; ++j) {
    49       SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);
    50       fam[arc] = i + j * j;
    51       if (i == 0 && j == 0) fa = arc;
    52     }
    53   }
    54 
    55   // Test digraph copy
    56   ListDigraph to;
    57   ListDigraph::NodeMap<int> tnm(to);
    58   ListDigraph::ArcMap<int> tam(to);
    59   ListDigraph::Node tn;
    60   ListDigraph::Arc ta;
    61 
    62   SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
    63   SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
    64 
    65   ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
    66   ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
    67 
    68   digraphCopy(from, to).
    69     nodeMap(fnm, tnm).arcMap(fam, tam).
    70     nodeRef(nr).arcRef(er).
    71     nodeCrossRef(ncr).arcCrossRef(ecr).
    72     node(fn, tn).arc(fa, ta).run();
    73   
    74   check(countNodes(from) == countNodes(to), "Wrong copy.");
    75   check(countArcs(from) == countArcs(to), "Wrong copy.");
    76 
    77   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
    78     check(ncr[nr[it]] == it, "Wrong copy.");
    79     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
    80   }
    81 
    82   for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
    83     check(ecr[er[it]] == it, "Wrong copy.");
    84     check(fam[it] == tam[er[it]], "Wrong copy.");
    85     check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
    86     check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
    87   }
    88 
    89   for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
    90     check(nr[ncr[it]] == it, "Wrong copy.");
    91   }
    92 
    93   for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
    94     check(er[ecr[it]] == it, "Wrong copy.");
    95   }
    96   check(tn == nr[fn], "Wrong copy.");
    97   check(ta == er[fa], "Wrong copy.");
    98 
    99   // Test repeated copy
   100   digraphCopy(from, to).run();
   101   
   102   check(countNodes(from) == countNodes(to), "Wrong copy.");
   103   check(countArcs(from) == countArcs(to), "Wrong copy.");
   104 }
   105 
   106 void graph_copy_test() {
   107   const int nn = 10;
   108 
   109   // Build a graph
   110   SmartGraph from;
   111   SmartGraph::NodeMap<int> fnm(from);
   112   SmartGraph::ArcMap<int> fam(from);
   113   SmartGraph::EdgeMap<int> fem(from);
   114   SmartGraph::Node fn = INVALID;
   115   SmartGraph::Arc fa = INVALID;
   116   SmartGraph::Edge fe = INVALID;
   117 
   118   std::vector<SmartGraph::Node> fnv;
   119   for (int i = 0; i < nn; ++i) {
   120     SmartGraph::Node node = from.addNode();
   121     fnv.push_back(node);
   122     fnm[node] = i * i;
   123     if (i == 0) fn = node;
   124   }
   125 
   126   for (int i = 0; i < nn; ++i) {
   127     for (int j = 0; j < nn; ++j) {
   128       SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
   129       fem[edge] = i * i + j * j;
   130       fam[from.direct(edge, true)] = i + j * j;
   131       fam[from.direct(edge, false)] = i * i + j;
   132       if (i == 0 && j == 0) fa = from.direct(edge, true);
   133       if (i == 0 && j == 0) fe = edge;
   134     }
   135   }
   136 
   137   // Test graph copy
   138   ListGraph to;
   139   ListGraph::NodeMap<int> tnm(to);
   140   ListGraph::ArcMap<int> tam(to);
   141   ListGraph::EdgeMap<int> tem(to);
   142   ListGraph::Node tn;
   143   ListGraph::Arc ta;
   144   ListGraph::Edge te;
   145 
   146   SmartGraph::NodeMap<ListGraph::Node> nr(from);
   147   SmartGraph::ArcMap<ListGraph::Arc> ar(from);
   148   SmartGraph::EdgeMap<ListGraph::Edge> er(from);
   149 
   150   ListGraph::NodeMap<SmartGraph::Node> ncr(to);
   151   ListGraph::ArcMap<SmartGraph::Arc> acr(to);
   152   ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
   153 
   154   graphCopy(from, to).
   155     nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).
   156     nodeRef(nr).arcRef(ar).edgeRef(er).
   157     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
   158     node(fn, tn).arc(fa, ta).edge(fe, te).run();
   159 
   160   check(countNodes(from) == countNodes(to), "Wrong copy.");
   161   check(countEdges(from) == countEdges(to), "Wrong copy.");
   162   check(countArcs(from) == countArcs(to), "Wrong copy.");
   163 
   164   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
   165     check(ncr[nr[it]] == it, "Wrong copy.");
   166     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
   167   }
   168 
   169   for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
   170     check(acr[ar[it]] == it, "Wrong copy.");
   171     check(fam[it] == tam[ar[it]], "Wrong copy.");
   172     check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
   173     check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
   174   }
   175 
   176   for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
   177     check(ecr[er[it]] == it, "Wrong copy.");
   178     check(fem[it] == tem[er[it]], "Wrong copy.");
   179     check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
   180           "Wrong copy.");
   181     check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
   182           "Wrong copy.");
   183     check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
   184           "Wrong copy.");
   185   }
   186 
   187   for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
   188     check(nr[ncr[it]] == it, "Wrong copy.");
   189   }
   190 
   191   for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
   192     check(ar[acr[it]] == it, "Wrong copy.");
   193   }
   194   for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
   195     check(er[ecr[it]] == it, "Wrong copy.");
   196   }
   197   check(tn == nr[fn], "Wrong copy.");
   198   check(ta == ar[fa], "Wrong copy.");
   199   check(te == er[fe], "Wrong copy.");
   200 
   201   // Test repeated copy
   202   graphCopy(from, to).run();
   203   
   204   check(countNodes(from) == countNodes(to), "Wrong copy.");
   205   check(countEdges(from) == countEdges(to), "Wrong copy.");
   206   check(countArcs(from) == countArcs(to), "Wrong copy.");
   207 }
   208 
   209 
   210 int main() {
   211   digraph_copy_test();
   212   graph_copy_test();
   213 
   214   return 0;
   215 }