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 hegyi
Mon, 21 Nov 2005 18:03:20 +0000
changeset 1823 cb082cdf3667
parent 1680 4f8b9cee576b
permissions -rw-r--r--
NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before. 
     1 // -*- C++ -*-

     2 

     3 #include <lemon/bits/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