test/graph_copy_test.cc
changeset 207 574b963d0275
child 209 765619b7cbb2
equal deleted inserted replaced
-1:000000000000 0:e96498ebc142
       
     1 /* -*- C++ -*-
       
     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/graph_utils.h>
       
    23 #include <lemon/error.h>
       
    24 
       
    25 #include "test_tools.h"
       
    26 
       
    27 using namespace std;
       
    28 using namespace lemon;
       
    29 
       
    30 void digraph_copy_test() {
       
    31   const int nn = 10;
       
    32 
       
    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   ListDigraph to;
       
    56   ListDigraph::NodeMap<int> tnm(to);
       
    57   ListDigraph::ArcMap<int> tam(to);
       
    58   ListDigraph::Node tn;
       
    59   ListDigraph::Arc ta;
       
    60 
       
    61   SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
       
    62   SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
       
    63 
       
    64   ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
       
    65   ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
       
    66 
       
    67   DigraphCopy<ListDigraph, SmartDigraph>(to, from).
       
    68     nodeMap(tnm, fnm).arcMap(tam, fam).
       
    69     nodeRef(nr).arcRef(er).
       
    70     nodeCrossRef(ncr).arcCrossRef(ecr).
       
    71     node(tn, fn).arc(ta, fa).run();
       
    72 
       
    73   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
       
    74     check(ncr[nr[it]] == it, "Wrong copy.");
       
    75     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
       
    76   }
       
    77 
       
    78   for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
       
    79     check(ecr[er[it]] == it, "Wrong copy.");
       
    80     check(fam[it] == tam[er[it]], "Wrong copy.");
       
    81     check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
       
    82     check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
       
    83   }
       
    84 
       
    85   for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
       
    86     check(nr[ncr[it]] == it, "Wrong copy.");
       
    87   }
       
    88 
       
    89   for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
       
    90     check(er[ecr[it]] == it, "Wrong copy.");
       
    91   }
       
    92   check(tn == nr[fn], "Wrong copy.");
       
    93   check(ta == er[fa], "Wrong copy.");
       
    94 }
       
    95 
       
    96 void graph_copy_test() {
       
    97   const int nn = 10;
       
    98 
       
    99   SmartGraph from;
       
   100   SmartGraph::NodeMap<int> fnm(from);
       
   101   SmartGraph::ArcMap<int> fam(from);
       
   102   SmartGraph::EdgeMap<int> fem(from);
       
   103   SmartGraph::Node fn = INVALID;
       
   104   SmartGraph::Arc fa = INVALID;
       
   105   SmartGraph::Edge fe = INVALID;
       
   106 
       
   107   std::vector<SmartGraph::Node> fnv;
       
   108   for (int i = 0; i < nn; ++i) {
       
   109     SmartGraph::Node node = from.addNode();
       
   110     fnv.push_back(node);
       
   111     fnm[node] = i * i;
       
   112     if (i == 0) fn = node;
       
   113   }
       
   114 
       
   115   for (int i = 0; i < nn; ++i) {
       
   116     for (int j = 0; j < nn; ++j) {
       
   117       SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
       
   118       fem[edge] = i * i + j * j;
       
   119       fam[from.direct(edge, true)] = i + j * j;
       
   120       fam[from.direct(edge, false)] = i * i + j;
       
   121       if (i == 0 && j == 0) fa = from.direct(edge, true);
       
   122       if (i == 0 && j == 0) fe = edge;
       
   123     }
       
   124   }
       
   125   
       
   126   ListGraph to;
       
   127   ListGraph::NodeMap<int> tnm(to);
       
   128   ListGraph::ArcMap<int> tam(to);
       
   129   ListGraph::EdgeMap<int> tem(to);
       
   130   ListGraph::Node tn;
       
   131   ListGraph::Arc ta;
       
   132   ListGraph::Edge te;
       
   133 
       
   134   SmartGraph::NodeMap<ListGraph::Node> nr(from);
       
   135   SmartGraph::ArcMap<ListGraph::Arc> ar(from);
       
   136   SmartGraph::EdgeMap<ListGraph::Edge> er(from);
       
   137 
       
   138   ListGraph::NodeMap<SmartGraph::Node> ncr(to);
       
   139   ListGraph::ArcMap<SmartGraph::Arc> acr(to);
       
   140   ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
       
   141 
       
   142   GraphCopy<ListGraph, SmartGraph>(to, from).
       
   143     nodeMap(tnm, fnm).arcMap(tam, fam).edgeMap(tem, fem).
       
   144     nodeRef(nr).arcRef(ar).edgeRef(er).
       
   145     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
       
   146     node(tn, fn).arc(ta, fa).edge(te, fe).run();
       
   147 
       
   148   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
       
   149     check(ncr[nr[it]] == it, "Wrong copy.");
       
   150     check(fnm[it] == tnm[nr[it]], "Wrong copy.");
       
   151   }
       
   152 
       
   153   for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
       
   154     check(acr[ar[it]] == it, "Wrong copy.");
       
   155     check(fam[it] == tam[ar[it]], "Wrong copy.");
       
   156     check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
       
   157     check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
       
   158   }
       
   159 
       
   160   for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
       
   161     check(ecr[er[it]] == it, "Wrong copy.");
       
   162     check(fem[it] == tem[er[it]], "Wrong copy.");
       
   163     check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]), 
       
   164 	  "Wrong copy.");
       
   165     check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]), 
       
   166 	  "Wrong copy.");
       
   167     check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])), 
       
   168 	  "Wrong copy.");
       
   169   }
       
   170 
       
   171   for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
       
   172     check(nr[ncr[it]] == it, "Wrong copy.");
       
   173   }
       
   174 
       
   175   for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
       
   176     check(ar[acr[it]] == it, "Wrong copy.");
       
   177   }
       
   178   for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
       
   179     check(er[ecr[it]] == it, "Wrong copy.");
       
   180   }
       
   181   check(tn == nr[fn], "Wrong copy.");
       
   182   check(ta == ar[fa], "Wrong copy.");
       
   183   check(te == er[fe], "Wrong copy.");
       
   184 }
       
   185 
       
   186 
       
   187 int main() {
       
   188   digraph_copy_test();
       
   189   graph_copy_test();
       
   190 
       
   191   return 0; 
       
   192 }