Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/undir_graph_test.cc
author deba
Mon, 12 Sep 2005 09:19:52 +0000
changeset 1680 4f8b9cee576b
parent 1568 f694f75de683
child 1795 ed3c253b9c29
permissions -rw-r--r--
Fixing and improving GridGraph 
     1 // -*- C++ -*-

     2 

     3 #include <lemon/bits/undir_graph_extender.h>

     4 #include <lemon/concept/undir_graph.h>

     5 #include <lemon/list_graph.h>

     6 #include <lemon/smart_graph.h>

     7 #include <lemon/full_graph.h>

     8 #include <lemon/grid_graph.h>

     9 

    10 #include <lemon/graph_utils.h>

    11 

    12 #include "test_tools.h"

    13 

    14 

    15 using namespace lemon;

    16 using namespace lemon::concept;

    17 

    18 void check_concepts() {

    19   typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;

    20 

    21   typedef IterableUndirGraphExtender<

    22     AlterableUndirGraphExtender<UndirListGraphBase> > IterableUndirListGraph;

    23 

    24   typedef MappableUndirGraphExtender<IterableUndirListGraph>

    25     MappableUndirListGraph;

    26 

    27   typedef ErasableUndirGraphExtender<

    28     ClearableUndirGraphExtender<

    29     ExtendableUndirGraphExtender<MappableUndirListGraph> > > Graph;

    30 

    31   checkConcept<BaseIterableUndirGraphConcept, Graph>();

    32   checkConcept<IterableUndirGraphConcept, Graph>();

    33   checkConcept<MappableUndirGraphConcept, Graph>();

    34 

    35   checkConcept<UndirGraph, Graph>();

    36   checkConcept<ErasableUndirGraph, Graph>();

    37 

    38   checkConcept<UndirGraph, UndirListGraph>();

    39   checkConcept<ErasableUndirGraph, UndirListGraph>();

    40 

    41   checkConcept<UndirGraph, UndirSmartGraph>();

    42   checkConcept<ExtendableUndirGraph, UndirSmartGraph>();

    43 

    44   checkConcept<UndirGraph, UndirFullGraph>();

    45 

    46   checkConcept<UndirGraph, UndirGraph>();

    47 

    48   checkConcept<UndirGraph, GridGraph>();

    49 }

    50 

    51 template <typename Graph>

    52 void check_item_counts(Graph &g, int n, int e) {

    53   int nn = 0;

    54   for (typename Graph::NodeIt it(g); it != INVALID; ++it) {

    55     ++nn;

    56   }

    57 

    58   check(nn == n, "Wrong node number.");

    59   check(countNodes(g) == n, "Wrong node number.");

    60 

    61   int ee = 0;

    62   for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {

    63     ++ee;

    64   }

    65 

    66   check(ee == 2*e, "Wrong edge number.");

    67   check(countEdges(g) == 2*e, "Wrong edge number.");

    68 

    69   int uee = 0;

    70   for (typename Graph::UndirEdgeIt it(g); it != INVALID; ++it) {

    71     ++uee;

    72   }

    73 

    74   check(uee == e, "Wrong undir edge number.");

    75   check(countUndirEdges(g) == e, "Wrong undir edge number.");

    76 }

    77 

    78 template <typename Graph>

    79 void print_items(Graph &g) {

    80 

    81   typedef typename Graph::NodeIt NodeIt;

    82   typedef typename Graph::UndirEdgeIt UEdgeIt;

    83   typedef typename Graph::EdgeIt EdgeIt;

    84 

    85   std::cout << "Nodes" << std::endl;

    86   int i=0;

    87   for(NodeIt it(g); it!=INVALID; ++it, ++i) {

    88     std::cout << "  " << i << ": " << g.id(it) << std::endl;

    89   }

    90 

    91   std::cout << "UndirEdge" << std::endl;

    92   i=0;

    93   for(UEdgeIt it(g); it!=INVALID; ++it, ++i) {

    94     std::cout << "  " << i << ": " << g.id(it) 

    95 	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 

    96 	 << ")" << std::endl;

    97   }

    98 

    99   std::cout << "Edge" << std::endl;

   100   i=0;

   101   for(EdgeIt it(g); it!=INVALID; ++it, ++i) {

   102     std::cout << "  " << i << ": " << g.id(it)

   103 	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 

   104 	 << ")" << std::endl;

   105   }

   106 

   107 }

   108 

   109 template <typename Graph>

   110 void check_graph() {

   111 

   112   typedef typename Graph::Node Node;

   113   typedef typename Graph::UndirEdge UEdge;

   114   typedef typename Graph::Edge Edge;

   115   typedef typename Graph::NodeIt NodeIt;

   116   typedef typename Graph::UndirEdgeIt UEdgeIt;

   117   typedef typename Graph::EdgeIt EdgeIt;

   118 

   119   Graph g;

   120 

   121   check_item_counts(g,0,0);

   122 

   123   Node

   124     n1 = g.addNode(),

   125     n2 = g.addNode(),

   126     n3 = g.addNode();

   127 

   128   UEdge

   129     e1 = g.addEdge(n1, n2),

   130     e2 = g.addEdge(n2, n3);

   131 

   132   // print_items(g);

   133 

   134   check_item_counts(g,3,2);

   135 }

   136 

   137 void checkGridGraph(const GridGraph& g, int w, int h) {

   138   check(g.width() == w, "Wrong width");

   139   check(g.height() == h, "Wrong height");

   140 

   141   for (int i = 0; i < w; ++i) {

   142     for (int j = 0; j < h; ++j) {

   143       check(g.col(g(i, j)) == i, "Wrong col");

   144       check(g.row(g(i, j)) == j, "Wrong row");

   145     }

   146   }

   147   

   148   for (int i = 0; i < w; ++i) {

   149     for (int j = 0; j < h - 1; ++j) {

   150       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");

   151       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");

   152     }

   153     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");

   154   }

   155 

   156   for (int i = 0; i < w; ++i) {

   157     for (int j = 1; j < h; ++j) {

   158       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");

   159       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");

   160     }

   161     check(g.up(g(i, 0)) == INVALID, "Wrong up");

   162   }

   163 

   164   for (int j = 0; j < h; ++j) {

   165     for (int i = 0; i < w - 1; ++i) {

   166       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");

   167       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");      

   168     }

   169     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");    

   170   }

   171 

   172   for (int j = 0; j < h; ++j) {

   173     for (int i = 1; i < w; ++i) {

   174       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");

   175       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");      

   176     }

   177     check(g.left(g(0, j)) == INVALID, "Wrong left");    

   178   }

   179 }

   180 

   181 int main() {

   182   check_concepts();

   183 

   184   check_graph<UndirListGraph>();

   185   check_graph<UndirSmartGraph>();

   186 

   187   {

   188     UndirFullGraph g(5);

   189     check_item_counts(g, 5, 10);

   190   }

   191 

   192   {

   193     GridGraph g(5, 6);

   194     check_item_counts(g, 30, 49);

   195     checkGridGraph(g, 5, 6);

   196   }

   197 

   198   std::cout << __FILE__ ": All tests passed.\n";

   199 

   200   return 0;

   201 }
lemon-0.x