test/bpugraph_test.cc
author deba
Fri, 03 Nov 2006 16:29:32 +0000
changeset 2293 1ee6e8788cc7
parent 2231 06faf3f06d67
child 2391 14a343be7a5a
permissions -rw-r--r--
First implementation of the static graph class
It could be improved to get better running times on benchmarks
     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/concepts/bpugraph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
    23 #include <lemon/grid_ugraph.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 graph components
    36     checkConcept<BaseBpUGraphComponent, BaseBpUGraphComponent >();
    37 
    38     checkConcept<IDableBpUGraphComponent<>, 
    39       IDableBpUGraphComponent<> >();
    40 
    41     checkConcept<IterableBpUGraphComponent<>, 
    42       IterableBpUGraphComponent<> >();
    43 
    44     checkConcept<MappableBpUGraphComponent<>, 
    45       MappableBpUGraphComponent<> >();
    46 
    47   }
    48   {
    49     checkConcept<BpUGraph, ListBpUGraph>();
    50     
    51     checkConcept<BpUGraph, SmartBpUGraph>();
    52     
    53     checkConcept<BpUGraph, FullBpUGraph>();
    54     
    55     checkConcept<BpUGraph, BpUGraph>();
    56     
    57   }
    58 }
    59 
    60 template <typename Graph>
    61 void check_item_counts(Graph &g, int an, int bn, int e) {
    62   int nn = 0;
    63   for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
    64     ++nn;
    65   }
    66 
    67   check(nn == an + bn, "Wrong node number.");
    68   check(countNodes(g) == an + bn, "Wrong node number.");
    69 
    70   int ann = 0;
    71   for (typename Graph::ANodeIt it(g); it != INVALID; ++it) {
    72     ++ann;
    73   }
    74 
    75   check(ann == an, "Wrong node number.");
    76   check(countANodes(g) == an, "Wrong node number.");
    77 
    78   int bnn = 0;
    79   for (typename Graph::BNodeIt it(g); it != INVALID; ++it) {
    80     ++bnn;
    81   }
    82 
    83   check(bnn == bn, "Wrong node number.");
    84   check(countBNodes(g) == bn, "Wrong node number.");
    85 
    86   int ee = 0;
    87   for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
    88     ++ee;
    89   }
    90 
    91   check(ee == 2*e, "Wrong edge number.");
    92   check(countEdges(g) == 2*e, "Wrong edge number.");
    93 
    94   int uee = 0;
    95   for (typename Graph::UEdgeIt it(g); it != INVALID; ++it) {
    96     ++uee;
    97   }
    98 
    99   check(uee == e, "Wrong uedge number.");
   100   check(countUEdges(g) == e, "Wrong uedge number.");
   101 }
   102 
   103 template <typename Graph>
   104 void check_graph() {
   105 
   106   typedef typename Graph::Node Node;
   107   typedef typename Graph::UEdge UEdge;
   108   typedef typename Graph::Edge Edge;
   109   typedef typename Graph::NodeIt NodeIt;
   110   typedef typename Graph::UEdgeIt UEdgeIt;
   111   typedef typename Graph::EdgeIt EdgeIt;
   112 
   113   Graph g;
   114 
   115   check_item_counts(g, 0, 0, 0);
   116 
   117   Node
   118     an1 = g.addANode(),
   119     an2 = g.addANode(),
   120     an3 = g.addANode(),
   121     bn1 = g.addBNode(),
   122     bn2 = g.addBNode();
   123 
   124   UEdge
   125     e1 = g.addEdge(an1, bn1),
   126     e2 = g.addEdge(an2, bn1),
   127     e3 = g.addEdge(an3, bn2);
   128 
   129   check_item_counts(g, 3, 2, 3);
   130 }
   131 
   132 int main() {
   133   check_concepts();
   134 
   135   check_graph<ListBpUGraph>();
   136   check_graph<SmartBpUGraph>();
   137 
   138   {
   139     FullBpUGraph g(5, 10);
   140     check_item_counts(g, 5, 10, 50);
   141   }
   142 
   143   std::cout << __FILE__ ": All tests passed.\n";
   144 
   145   return 0;
   146 }