test/ugraph_test.cc
author deba
Thu, 01 Mar 2007 16:47:49 +0000
changeset 2382 678bea23ed75
parent 2231 06faf3f06d67
child 2391 14a343be7a5a
permissions -rw-r--r--
2-approximation of Steiner-tree problem
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     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/bits/graph_extender.h>
    20 #include <lemon/concepts/ugraph.h>
    21 #include <lemon/list_graph.h>
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/full_graph.h>
    24 #include <lemon/grid_ugraph.h>
    25 
    26 #include <lemon/graph_utils.h>
    27 
    28 #include "test_tools.h"
    29 
    30 
    31 using namespace lemon;
    32 using namespace lemon::concepts;
    33 
    34 void check_concepts() {
    35 
    36   { // checking graph components
    37     checkConcept<BaseUGraphComponent, BaseUGraphComponent >();
    38 
    39     checkConcept<IDableUGraphComponent<>, 
    40       IDableUGraphComponent<> >();
    41 
    42     checkConcept<IterableUGraphComponent<>, 
    43       IterableUGraphComponent<> >();
    44 
    45     checkConcept<MappableUGraphComponent<>, 
    46       MappableUGraphComponent<> >();
    47 
    48   }
    49   {
    50     checkConcept<UGraph, ListUGraph>();
    51     
    52     checkConcept<UGraph, SmartUGraph>();
    53     
    54     checkConcept<UGraph, FullUGraph>();
    55     
    56     checkConcept<UGraph, UGraph>();
    57     
    58     checkConcept<UGraph, GridUGraph>();
    59   }
    60 }
    61 
    62 template <typename Graph>
    63 void check_item_counts(Graph &g, int n, int e) {
    64   int nn = 0;
    65   for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
    66     ++nn;
    67   }
    68 
    69   check(nn == n, "Wrong node number.");
    70   check(countNodes(g) == n, "Wrong node number.");
    71 
    72   int ee = 0;
    73   for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
    74     ++ee;
    75   }
    76 
    77   check(ee == 2*e, "Wrong edge number.");
    78   check(countEdges(g) == 2*e, "Wrong edge number.");
    79 
    80   int uee = 0;
    81   for (typename Graph::UEdgeIt it(g); it != INVALID; ++it) {
    82     ++uee;
    83   }
    84 
    85   check(uee == e, "Wrong uedge number.");
    86   check(countUEdges(g) == e, "Wrong uedge number.");
    87 }
    88 
    89 template <typename Graph>
    90 void print_items(Graph &g) {
    91 
    92   typedef typename Graph::NodeIt NodeIt;
    93   typedef typename Graph::UEdgeIt UEdgeIt;
    94   typedef typename Graph::EdgeIt EdgeIt;
    95 
    96   std::cout << "Nodes" << std::endl;
    97   int i=0;
    98   for(NodeIt it(g); it!=INVALID; ++it, ++i) {
    99     std::cout << "  " << i << ": " << g.id(it) << std::endl;
   100   }
   101 
   102   std::cout << "UEdge" << std::endl;
   103   i=0;
   104   for(UEdgeIt it(g); it!=INVALID; ++it, ++i) {
   105     std::cout << "  " << i << ": " << g.id(it) 
   106 	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 
   107 	 << ")" << std::endl;
   108   }
   109 
   110   std::cout << "Edge" << std::endl;
   111   i=0;
   112   for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
   113     std::cout << "  " << i << ": " << g.id(it)
   114 	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 
   115 	 << ")" << std::endl;
   116   }
   117 
   118 }
   119 
   120 template <typename Graph>
   121 void check_graph() {
   122 
   123   typedef typename Graph::Node Node;
   124   typedef typename Graph::UEdge UEdge;
   125   typedef typename Graph::Edge Edge;
   126   typedef typename Graph::NodeIt NodeIt;
   127   typedef typename Graph::UEdgeIt UEdgeIt;
   128   typedef typename Graph::EdgeIt EdgeIt;
   129 
   130   Graph g;
   131 
   132   check_item_counts(g,0,0);
   133 
   134   Node
   135     n1 = g.addNode(),
   136     n2 = g.addNode(),
   137     n3 = g.addNode();
   138 
   139   UEdge
   140     e1 = g.addEdge(n1, n2),
   141     e2 = g.addEdge(n2, n3);
   142 
   143   // print_items(g);
   144 
   145   check_item_counts(g,3,2);
   146 }
   147 
   148 void checkGridUGraph(const GridUGraph& g, int w, int h) {
   149   check(g.width() == w, "Wrong width");
   150   check(g.height() == h, "Wrong height");
   151 
   152   for (int i = 0; i < w; ++i) {
   153     for (int j = 0; j < h; ++j) {
   154       check(g.col(g(i, j)) == i, "Wrong col");
   155       check(g.row(g(i, j)) == j, "Wrong row");
   156     }
   157   }
   158   
   159   for (int i = 0; i < w; ++i) {
   160     for (int j = 0; j < h - 1; ++j) {
   161       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
   162       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
   163     }
   164     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
   165   }
   166 
   167   for (int i = 0; i < w; ++i) {
   168     for (int j = 1; j < h; ++j) {
   169       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
   170       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
   171     }
   172     check(g.up(g(i, 0)) == INVALID, "Wrong up");
   173   }
   174 
   175   for (int j = 0; j < h; ++j) {
   176     for (int i = 0; i < w - 1; ++i) {
   177       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
   178       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");      
   179     }
   180     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");    
   181   }
   182 
   183   for (int j = 0; j < h; ++j) {
   184     for (int i = 1; i < w; ++i) {
   185       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
   186       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");      
   187     }
   188     check(g.left(g(0, j)) == INVALID, "Wrong left");    
   189   }
   190 }
   191 
   192 int main() {
   193   check_concepts();
   194 
   195   check_graph<ListUGraph>();
   196   check_graph<SmartUGraph>();
   197 
   198   {
   199     FullUGraph g(5);
   200     check_item_counts(g, 5, 10);
   201   }
   202 
   203   {
   204     GridUGraph g(5, 6);
   205     check_item_counts(g, 30, 49);
   206     checkGridUGraph(g, 5, 6);
   207   }
   208 
   209   std::cout << __FILE__ ": All tests passed.\n";
   210 
   211   return 0;
   212 }