test/graph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 05 May 2008 11:41:30 +0200
changeset 155 5c3604513ed0
parent 109 abddaa08b507
child 171 02f4d5d9bfd7
permissions -rw-r--r--
Update .hgignore
     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/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 check_graph_counts() {
    86 
    87   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    88   Graph g;
    89 
    90   check_item_counts(g,0,0);
    91 
    92   Node
    93     n1 = g.addNode(),
    94     n2 = g.addNode(),
    95     n3 = g.addNode();
    96 
    97   Edge
    98     e1 = g.addEdge(n1, n2),
    99     e2 = g.addEdge(n2, n3);
   100 
   101   check_item_counts(g,3,2);
   102 }
   103 
   104 template <typename Graph>
   105 void check_graph_validity() {
   106 
   107   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   108   Graph g;
   109 
   110   check_item_counts(g,0,0);
   111 
   112   Node
   113     n1 = g.addNode(),
   114     n2 = g.addNode(),
   115     n3 = g.addNode();
   116 
   117   Edge
   118     e1 = g.addEdge(n1, n2),
   119     e2 = g.addEdge(n2, n3);
   120 
   121   check(g.valid(n1), "Validity check");
   122   check(g.valid(e1), "Validity check");
   123   check(g.valid(g.direct(e1, true)), "Validity check");
   124 
   125   check(!g.valid(g.nodeFromId(-1)), "Validity check");
   126   check(!g.valid(g.edgeFromId(-1)), "Validity check");
   127   check(!g.valid(g.arcFromId(-1)), "Validity check");
   128     
   129 }
   130 
   131 template <typename Graph>
   132 void check_graph_validity_erase() {
   133 
   134   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   135   Graph g;
   136 
   137   check_item_counts(g,0,0);
   138 
   139   Node
   140     n1 = g.addNode(),
   141     n2 = g.addNode(),
   142     n3 = g.addNode();
   143 
   144   Edge
   145     e1 = g.addEdge(n1, n2),
   146     e2 = g.addEdge(n2, n3);
   147 
   148   check(g.valid(n1), "Validity check");
   149   check(g.valid(e1), "Validity check");
   150   check(g.valid(g.direct(e1, true)), "Validity check");
   151 
   152   g.erase(n1);
   153 
   154   check(!g.valid(n1), "Validity check");
   155   check(g.valid(n2), "Validity check");
   156   check(g.valid(n3), "Validity check");
   157   check(!g.valid(e1), "Validity check");
   158   check(g.valid(e2), "Validity check");
   159 
   160   check(!g.valid(g.nodeFromId(-1)), "Validity check");
   161   check(!g.valid(g.edgeFromId(-1)), "Validity check");
   162   check(!g.valid(g.arcFromId(-1)), "Validity check");
   163     
   164 }
   165 
   166 
   167 
   168 // void checkGridGraph(const GridGraph& g, int w, int h) {
   169 //   check(g.width() == w, "Wrong width");
   170 //   check(g.height() == h, "Wrong height");
   171 
   172 //   for (int i = 0; i < w; ++i) {
   173 //     for (int j = 0; j < h; ++j) {
   174 //       check(g.col(g(i, j)) == i, "Wrong col");
   175 //       check(g.row(g(i, j)) == j, "Wrong row");
   176 //     }
   177 //   }
   178   
   179 //   for (int i = 0; i < w; ++i) {
   180 //     for (int j = 0; j < h - 1; ++j) {
   181 //       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
   182 //       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
   183 //     }
   184 //     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
   185 //   }
   186 
   187 //   for (int i = 0; i < w; ++i) {
   188 //     for (int j = 1; j < h; ++j) {
   189 //       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
   190 //       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
   191 //     }
   192 //     check(g.up(g(i, 0)) == INVALID, "Wrong up");
   193 //   }
   194 
   195 //   for (int j = 0; j < h; ++j) {
   196 //     for (int i = 0; i < w - 1; ++i) {
   197 //       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
   198 //       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");      
   199 //     }
   200 //     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");    
   201 //   }
   202 
   203 //   for (int j = 0; j < h; ++j) {
   204 //     for (int i = 1; i < w; ++i) {
   205 //       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
   206 //       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");      
   207 //     }
   208 //     check(g.left(g(0, j)) == INVALID, "Wrong left");    
   209 //   }
   210 // }
   211 
   212 int main() {
   213   check_concepts();
   214 
   215   check_graph_counts<ListGraph>();
   216   check_graph_counts<SmartGraph>();
   217 
   218   check_graph_validity_erase<ListGraph>();
   219   check_graph_validity<SmartGraph>();
   220 
   221 //   {
   222 //     FullGraph g(5);
   223 //     check_item_counts(g, 5, 10);
   224 //   }
   225 
   226 //   {
   227 //     GridGraph g(5, 6);
   228 //     check_item_counts(g, 30, 49);
   229 //     checkGridGraph(g, 5, 6);
   230 //   }
   231 
   232   std::cout << __FILE__ ": All tests passed.\n";
   233 
   234   return 0;
   235 }