Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/graph_test.cc
changeset 200 c0e2c043c060
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 }
lemon