test/graph_test.cc
changeset 196 420013ff029b
parent 149 2f7ae34e1333
child 209 765619b7cbb2
equal deleted inserted replaced
3:e96a06cbcd4f 4:7e804e82d355
    20 #include <lemon/list_graph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/smart_graph.h>
    21 #include <lemon/smart_graph.h>
    22 // #include <lemon/full_graph.h>
    22 // #include <lemon/full_graph.h>
    23 // #include <lemon/grid_graph.h>
    23 // #include <lemon/grid_graph.h>
    24 
    24 
    25 #include <lemon/graph_utils.h>
       
    26 
       
    27 #include "test_tools.h"
    25 #include "test_tools.h"
    28 
    26 #include "graph_test.h"
       
    27 #include "graph_maps_test.h"
    29 
    28 
    30 using namespace lemon;
    29 using namespace lemon;
    31 using namespace lemon::concepts;
    30 using namespace lemon::concepts;
    32 
    31 
    33 void check_concepts() {
    32 void check_concepts() {
    34 
    33   { // Checking graph components
    35   { // checking digraph components
       
    36     checkConcept<BaseGraphComponent, BaseGraphComponent >();
    34     checkConcept<BaseGraphComponent, BaseGraphComponent >();
    37 
    35 
    38     checkConcept<IDableGraphComponent<>, 
    36     checkConcept<IDableGraphComponent<>, 
    39       IDableGraphComponent<> >();
    37       IDableGraphComponent<> >();
    40 
    38 
    41     checkConcept<IterableGraphComponent<>, 
    39     checkConcept<IterableGraphComponent<>, 
    42       IterableGraphComponent<> >();
    40       IterableGraphComponent<> >();
    43 
    41 
    44     checkConcept<MappableGraphComponent<>, 
    42     checkConcept<MappableGraphComponent<>, 
    45       MappableGraphComponent<> >();
    43       MappableGraphComponent<> >();
    46 
    44   }
    47   }
    45   { // Checking skeleton graph
    48   {
    46     checkConcept<Graph, Graph>();
    49     checkConcept<Graph, ListGraph>();    
    47   }
    50     checkConcept<Graph, SmartGraph>();    
    48   { // Checking ListGraph
    51 //     checkConcept<Graph, FullGraph>();    
    49     checkConcept<Graph, ListGraph>();
    52 //     checkConcept<Graph, Graph>();    
    50     checkConcept<AlterableGraphComponent<>, ListGraph>();
    53 //     checkConcept<Graph, GridGraph>();
    51     checkConcept<ExtendableGraphComponent<>, ListGraph>();
    54   }
    52     checkConcept<ClearableGraphComponent<>, ListGraph>();
       
    53     checkConcept<ErasableGraphComponent<>, ListGraph>();
       
    54     checkGraphIterators<ListGraph>();
       
    55   }
       
    56   { // Checking SmartGraph
       
    57     checkConcept<Graph, SmartGraph>();
       
    58     checkConcept<AlterableGraphComponent<>, SmartGraph>();
       
    59     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
       
    60     checkConcept<ClearableGraphComponent<>, SmartGraph>();
       
    61     checkGraphIterators<SmartGraph>();
       
    62   }
       
    63 //  { // Checking FullGraph
       
    64 //    checkConcept<Graph, FullGraph>();
       
    65 //    checkGraphIterators<FullGraph>();
       
    66 //  }
       
    67 //  { // Checking GridGraph
       
    68 //    checkConcept<Graph, GridGraph>();
       
    69 //    checkGraphIterators<GridGraph>();
       
    70 //  }
    55 }
    71 }
    56 
    72 
    57 template <typename Graph>
    73 template <typename Graph>
    58 void check_item_counts(Graph &g, int n, int e) {
    74 void check_graph_validity() {
    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);
    75   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    88   Graph g;
    76   Graph g;
    89 
       
    90   check_item_counts(g,0,0);
       
    91 
    77 
    92   Node
    78   Node
    93     n1 = g.addNode(),
    79     n1 = g.addNode(),
    94     n2 = g.addNode(),
    80     n2 = g.addNode(),
    95     n3 = g.addNode();
    81     n3 = g.addNode();
    96 
    82 
    97   Edge
    83   Edge
    98     e1 = g.addEdge(n1, n2),
    84     e1 = g.addEdge(n1, n2),
    99     e2 = g.addEdge(n2, n3);
    85     e2 = g.addEdge(n2, n3);
   100 
    86 
   101   check_item_counts(g,3,2);
    87   check(g.valid(n1), "Wrong validity check");
       
    88   check(g.valid(e1), "Wrong validity check");
       
    89   check(g.valid(g.direct(e1, true)), "Wrong validity check");
       
    90 
       
    91   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
       
    92   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
       
    93   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   102 }
    94 }
   103 
    95 
   104 template <typename Graph>
    96 template <typename Graph>
   105 void check_graph_validity() {
    97 void check_graph_validity_erase() {
   106 
       
   107   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    98   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   108   Graph g;
    99   Graph g;
   109 
       
   110   check_item_counts(g,0,0);
       
   111 
   100 
   112   Node
   101   Node
   113     n1 = g.addNode(),
   102     n1 = g.addNode(),
   114     n2 = g.addNode(),
   103     n2 = g.addNode(),
   115     n3 = g.addNode();
   104     n3 = g.addNode();
   116 
   105 
   117   Edge
   106   Edge
   118     e1 = g.addEdge(n1, n2),
   107     e1 = g.addEdge(n1, n2),
   119     e2 = g.addEdge(n2, n3);
   108     e2 = g.addEdge(n2, n3);
   120 
   109 
   121   check(g.valid(n1), "Validity check");
   110   check(g.valid(n1), "Wrong validity check");
   122   check(g.valid(e1), "Validity check");
   111   check(g.valid(e1), "Wrong validity check");
   123   check(g.valid(g.direct(e1, true)), "Validity check");
   112   check(g.valid(g.direct(e1, true)), "Wrong 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 
   113 
   152   g.erase(n1);
   114   g.erase(n1);
   153 
   115 
   154   check(!g.valid(n1), "Validity check");
   116   check(!g.valid(n1), "Wrong validity check");
   155   check(g.valid(n2), "Validity check");
   117   check(g.valid(n2), "Wrong validity check");
   156   check(g.valid(n3), "Validity check");
   118   check(g.valid(n3), "Wrong validity check");
   157   check(!g.valid(e1), "Validity check");
   119   check(!g.valid(e1), "Wrong validity check");
   158   check(g.valid(e2), "Validity check");
   120   check(g.valid(e2), "Wrong validity check");
   159 
   121 
   160   check(!g.valid(g.nodeFromId(-1)), "Validity check");
   122   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   161   check(!g.valid(g.edgeFromId(-1)), "Validity check");
   123   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   162   check(!g.valid(g.arcFromId(-1)), "Validity check");
   124   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   163     
   125 }
   164 }
       
   165 
       
   166 
       
   167 
   126 
   168 // void checkGridGraph(const GridGraph& g, int w, int h) {
   127 // void checkGridGraph(const GridGraph& g, int w, int h) {
   169 //   check(g.width() == w, "Wrong width");
   128 //   check(g.width() == w, "Wrong width");
   170 //   check(g.height() == h, "Wrong height");
   129 //   check(g.height() == h, "Wrong height");
   171 
   130 
   207 //     }
   166 //     }
   208 //     check(g.left(g(0, j)) == INVALID, "Wrong left");    
   167 //     check(g.left(g(0, j)) == INVALID, "Wrong left");    
   209 //   }
   168 //   }
   210 // }
   169 // }
   211 
   170 
       
   171 void check_graphs() {
       
   172   { // Checking ListGraph
       
   173     checkGraph<ListGraph>();
       
   174     checkGraphNodeMap<ListGraph>();
       
   175     checkGraphEdgeMap<ListGraph>();
       
   176 
       
   177     check_graph_validity_erase<ListGraph>();
       
   178   }
       
   179   { // Checking SmartGraph
       
   180     checkGraph<SmartGraph>();
       
   181     checkGraphNodeMap<SmartGraph>();
       
   182     checkGraphEdgeMap<SmartGraph>();
       
   183 
       
   184     check_graph_validity<SmartGraph>();
       
   185   }
       
   186 //   { // Checking FullGraph
       
   187 //     FullGraph g(5);
       
   188 //     checkGraphNodeList(g, 5);
       
   189 //     checkGraphEdgeList(g, 10);
       
   190 //   }
       
   191 //   { // Checking GridGraph
       
   192 //     GridGraph g(5, 6);
       
   193 //     checkGraphNodeList(g, 30);
       
   194 //     checkGraphEdgeList(g, 49);
       
   195 //     checkGridGraph(g, 5, 6);
       
   196 //   }
       
   197 }
       
   198 
   212 int main() {
   199 int main() {
   213   check_concepts();
   200   check_concepts();
   214 
   201   check_graphs();
   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;
   202   return 0;
   235 }
   203 }