test/graph_test.cc
branch1.0
changeset 428 a1d8d1736c68
parent 228 b6732e0d38c5
equal deleted inserted replaced
6:1c3fb61c4e8f 7:b84a28667862
    27 
    27 
    28 using namespace lemon;
    28 using namespace lemon;
    29 using namespace lemon::concepts;
    29 using namespace lemon::concepts;
    30 
    30 
    31 template <class Graph>
    31 template <class Graph>
    32 void checkGraph() {
    32 void checkGraphBuild() {
    33   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    33   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    34 
    34 
    35   Graph G;
    35   Graph G;
    36   checkGraphNodeList(G, 0);
    36   checkGraphNodeList(G, 0);
    37   checkGraphEdgeList(G, 0);
    37   checkGraphEdgeList(G, 0);
       
    38   checkGraphArcList(G, 0);
    38 
    39 
    39   Node
    40   Node
    40     n1 = G.addNode(),
    41     n1 = G.addNode(),
    41     n2 = G.addNode(),
    42     n2 = G.addNode(),
    42     n3 = G.addNode();
    43     n3 = G.addNode();
    43   checkGraphNodeList(G, 3);
    44   checkGraphNodeList(G, 3);
    44   checkGraphEdgeList(G, 0);
    45   checkGraphEdgeList(G, 0);
       
    46   checkGraphArcList(G, 0);
    45 
    47 
    46   Edge e1 = G.addEdge(n1, n2);
    48   Edge e1 = G.addEdge(n1, n2);
    47   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    49   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    48         "Wrong edge");
    50         "Wrong edge");
    49   checkGraphNodeList(G, 3);
    51 
       
    52   checkGraphNodeList(G, 3);
       
    53   checkGraphEdgeList(G, 1);
    50   checkGraphArcList(G, 2);
    54   checkGraphArcList(G, 2);
    51   checkGraphEdgeList(G, 1);
    55 
    52 
    56   checkGraphIncEdgeArcLists(G, n1, 1);
    53   checkGraphOutArcList(G, n1, 1);
    57   checkGraphIncEdgeArcLists(G, n2, 1);
    54   checkGraphOutArcList(G, n2, 1);
    58   checkGraphIncEdgeArcLists(G, n3, 0);
    55   checkGraphOutArcList(G, n3, 0);
    59 
    56 
    60   checkGraphConEdgeList(G, 1);
    57   checkGraphInArcList(G, n1, 1);
       
    58   checkGraphInArcList(G, n2, 1);
       
    59   checkGraphInArcList(G, n3, 0);
       
    60 
       
    61   checkGraphIncEdgeList(G, n1, 1);
       
    62   checkGraphIncEdgeList(G, n2, 1);
       
    63   checkGraphIncEdgeList(G, n3, 0);
       
    64 
       
    65   checkGraphConArcList(G, 2);
    61   checkGraphConArcList(G, 2);
    66   checkGraphConEdgeList(G, 1);
    62 
    67 
    63   Edge e2 = G.addEdge(n2, n1),
    68   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    64        e3 = G.addEdge(n2, n3);
    69   checkGraphNodeList(G, 3);
    65 
       
    66   checkGraphNodeList(G, 3);
       
    67   checkGraphEdgeList(G, 3);
    70   checkGraphArcList(G, 6);
    68   checkGraphArcList(G, 6);
    71   checkGraphEdgeList(G, 3);
    69 
    72 
    70   checkGraphIncEdgeArcLists(G, n1, 2);
    73   checkGraphOutArcList(G, n1, 2);
    71   checkGraphIncEdgeArcLists(G, n2, 3);
    74   checkGraphOutArcList(G, n2, 3);
    72   checkGraphIncEdgeArcLists(G, n3, 1);
    75   checkGraphOutArcList(G, n3, 1);
    73 
    76 
    74   checkGraphConEdgeList(G, 3);
    77   checkGraphInArcList(G, n1, 2);
       
    78   checkGraphInArcList(G, n2, 3);
       
    79   checkGraphInArcList(G, n3, 1);
       
    80 
       
    81   checkGraphIncEdgeList(G, n1, 2);
       
    82   checkGraphIncEdgeList(G, n2, 3);
       
    83   checkGraphIncEdgeList(G, n3, 1);
       
    84 
       
    85   checkGraphConArcList(G, 6);
    75   checkGraphConArcList(G, 6);
    86   checkGraphConEdgeList(G, 3);
       
    87 
    76 
    88   checkArcDirections(G);
    77   checkArcDirections(G);
    89 
    78 
    90   checkNodeIds(G);
    79   checkNodeIds(G);
    91   checkArcIds(G);
    80   checkArcIds(G);
    92   checkEdgeIds(G);
    81   checkEdgeIds(G);
    93   checkGraphNodeMap(G);
    82   checkGraphNodeMap(G);
    94   checkGraphArcMap(G);
    83   checkGraphArcMap(G);
    95   checkGraphEdgeMap(G);
    84   checkGraphEdgeMap(G);
       
    85 }
       
    86 
       
    87 template <class Graph>
       
    88 void checkGraphAlter() {
       
    89   TEMPLATE_GRAPH_TYPEDEFS(Graph);
       
    90 
       
    91   Graph G;
       
    92   Node n1 = G.addNode(), n2 = G.addNode(),
       
    93        n3 = G.addNode(), n4 = G.addNode();
       
    94   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
       
    95        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
       
    96        e5 = G.addEdge(n4, n3);
       
    97 
       
    98   checkGraphNodeList(G, 4);
       
    99   checkGraphEdgeList(G, 5);
       
   100   checkGraphArcList(G, 10);
       
   101 
       
   102   // Check changeU() and changeV()
       
   103   if (G.u(e2) == n2) {
       
   104     G.changeU(e2, n3);
       
   105   } else {
       
   106     G.changeV(e2, n3);
       
   107   }
       
   108 
       
   109   checkGraphNodeList(G, 4);
       
   110   checkGraphEdgeList(G, 5);
       
   111   checkGraphArcList(G, 10);
       
   112 
       
   113   checkGraphIncEdgeArcLists(G, n1, 3);
       
   114   checkGraphIncEdgeArcLists(G, n2, 2);
       
   115   checkGraphIncEdgeArcLists(G, n3, 3);
       
   116   checkGraphIncEdgeArcLists(G, n4, 2);
       
   117 
       
   118   checkGraphConEdgeList(G, 5);
       
   119   checkGraphConArcList(G, 10);
       
   120 
       
   121   if (G.u(e2) == n1) {
       
   122     G.changeU(e2, n2);
       
   123   } else {
       
   124     G.changeV(e2, n2);
       
   125   }
       
   126 
       
   127   checkGraphNodeList(G, 4);
       
   128   checkGraphEdgeList(G, 5);
       
   129   checkGraphArcList(G, 10);
       
   130 
       
   131   checkGraphIncEdgeArcLists(G, n1, 2);
       
   132   checkGraphIncEdgeArcLists(G, n2, 3);
       
   133   checkGraphIncEdgeArcLists(G, n3, 3);
       
   134   checkGraphIncEdgeArcLists(G, n4, 2);
       
   135 
       
   136   checkGraphConEdgeList(G, 5);
       
   137   checkGraphConArcList(G, 10);
       
   138 
       
   139   // Check contract()
       
   140   G.contract(n1, n4, false);
       
   141 
       
   142   checkGraphNodeList(G, 3);
       
   143   checkGraphEdgeList(G, 5);
       
   144   checkGraphArcList(G, 10);
       
   145 
       
   146   checkGraphIncEdgeArcLists(G, n1, 4);
       
   147   checkGraphIncEdgeArcLists(G, n2, 3);
       
   148   checkGraphIncEdgeArcLists(G, n3, 3);
       
   149 
       
   150   checkGraphConEdgeList(G, 5);
       
   151   checkGraphConArcList(G, 10);
       
   152 
       
   153   G.contract(n2, n3);
       
   154 
       
   155   checkGraphNodeList(G, 2);
       
   156   checkGraphEdgeList(G, 3);
       
   157   checkGraphArcList(G, 6);
       
   158 
       
   159   checkGraphIncEdgeArcLists(G, n1, 4);
       
   160   checkGraphIncEdgeArcLists(G, n2, 2);
       
   161 
       
   162   checkGraphConEdgeList(G, 3);
       
   163   checkGraphConArcList(G, 6);
       
   164 }
       
   165 
       
   166 template <class Graph>
       
   167 void checkGraphErase() {
       
   168   TEMPLATE_GRAPH_TYPEDEFS(Graph);
       
   169 
       
   170   Graph G;
       
   171   Node n1 = G.addNode(), n2 = G.addNode(),
       
   172        n3 = G.addNode(), n4 = G.addNode();
       
   173   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
       
   174        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
       
   175        e5 = G.addEdge(n4, n3);
       
   176 
       
   177   // Check edge deletion
       
   178   G.erase(e2);
       
   179 
       
   180   checkGraphNodeList(G, 4);
       
   181   checkGraphEdgeList(G, 4);
       
   182   checkGraphArcList(G, 8);
       
   183 
       
   184   checkGraphIncEdgeArcLists(G, n1, 2);
       
   185   checkGraphIncEdgeArcLists(G, n2, 2);
       
   186   checkGraphIncEdgeArcLists(G, n3, 2);
       
   187   checkGraphIncEdgeArcLists(G, n4, 2);
       
   188 
       
   189   checkGraphConEdgeList(G, 4);
       
   190   checkGraphConArcList(G, 8);
       
   191 
       
   192   // Check node deletion
       
   193   G.erase(n3);
       
   194 
       
   195   checkGraphNodeList(G, 3);
       
   196   checkGraphEdgeList(G, 2);
       
   197   checkGraphArcList(G, 4);
       
   198 
       
   199   checkGraphIncEdgeArcLists(G, n1, 2);
       
   200   checkGraphIncEdgeArcLists(G, n2, 1);
       
   201   checkGraphIncEdgeArcLists(G, n4, 1);
       
   202 
       
   203   checkGraphConEdgeList(G, 2);
       
   204   checkGraphConArcList(G, 4);
       
   205 }
       
   206 
       
   207 
       
   208 template <class Graph>
       
   209 void checkGraphSnapshot() {
       
   210   TEMPLATE_GRAPH_TYPEDEFS(Graph);
       
   211 
       
   212   Graph G;
       
   213   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
       
   214   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
       
   215        e3 = G.addEdge(n2, n3);
       
   216 
       
   217   checkGraphNodeList(G, 3);
       
   218   checkGraphEdgeList(G, 3);
       
   219   checkGraphArcList(G, 6);
       
   220 
       
   221   typename Graph::Snapshot snapshot(G);
       
   222 
       
   223   Node n = G.addNode();
       
   224   G.addEdge(n3, n);
       
   225   G.addEdge(n, n3);
       
   226   G.addEdge(n3, n2);
       
   227 
       
   228   checkGraphNodeList(G, 4);
       
   229   checkGraphEdgeList(G, 6);
       
   230   checkGraphArcList(G, 12);
       
   231 
       
   232   snapshot.restore();
       
   233 
       
   234   checkGraphNodeList(G, 3);
       
   235   checkGraphEdgeList(G, 3);
       
   236   checkGraphArcList(G, 6);
       
   237 
       
   238   checkGraphIncEdgeArcLists(G, n1, 2);
       
   239   checkGraphIncEdgeArcLists(G, n2, 3);
       
   240   checkGraphIncEdgeArcLists(G, n3, 1);
       
   241 
       
   242   checkGraphConEdgeList(G, 3);
       
   243   checkGraphConArcList(G, 6);
       
   244 
       
   245   checkNodeIds(G);
       
   246   checkEdgeIds(G);
       
   247   checkArcIds(G);
       
   248   checkGraphNodeMap(G);
       
   249   checkGraphEdgeMap(G);
       
   250   checkGraphArcMap(G);
       
   251 
       
   252   G.addNode();
       
   253   snapshot.save(G);
       
   254 
       
   255   G.addEdge(G.addNode(), G.addNode());
       
   256 
       
   257   snapshot.restore();
       
   258 
       
   259   checkGraphNodeList(G, 4);
       
   260   checkGraphEdgeList(G, 3);
       
   261   checkGraphArcList(G, 6);
    96 }
   262 }
    97 
   263 
    98 void checkConcepts() {
   264 void checkConcepts() {
    99   { // Checking graph components
   265   { // Checking graph components
   100     checkConcept<BaseGraphComponent, BaseGraphComponent >();
   266     checkConcept<BaseGraphComponent, BaseGraphComponent >();
   232 //   }
   398 //   }
   233 // }
   399 // }
   234 
   400 
   235 void checkGraphs() {
   401 void checkGraphs() {
   236   { // Checking ListGraph
   402   { // Checking ListGraph
   237     checkGraph<ListGraph>();
   403     checkGraphBuild<ListGraph>();
       
   404     checkGraphAlter<ListGraph>();
       
   405     checkGraphErase<ListGraph>();
       
   406     checkGraphSnapshot<ListGraph>();
   238     checkGraphValidityErase<ListGraph>();
   407     checkGraphValidityErase<ListGraph>();
   239   }
   408   }
   240   { // Checking SmartGraph
   409   { // Checking SmartGraph
   241     checkGraph<SmartGraph>();
   410     checkGraphBuild<SmartGraph>();
       
   411     checkGraphSnapshot<SmartGraph>();
   242     checkGraphValidity<SmartGraph>();
   412     checkGraphValidity<SmartGraph>();
   243   }
   413   }
   244 //   { // Checking FullGraph
   414 //   { // Checking FullGraph
   245 //     FullGraph g(5);
   415 //     FullGraph g(5);
   246 //     checkGraphNodeList(g, 5);
   416 //     checkGraphNodeList(g, 5);