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