Mercuriallemon-main / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/graph_test.cc
changeset 391 624e673efa76
parent 372 7b6466ed488a
parent 374 49d9a36b3b84
child 440 88ed40ad0d4f
equal deleted inserted replaced
13:1039a3e0fca7 15:5b0062cba298 
    28 
    28 
    29 using namespace lemon;
 
    29 using namespace lemon;
 
    30 using namespace lemon::concepts;
 
    30 using namespace lemon::concepts;
 
    31 
    31 
    32 template <class Graph>
 
    32 template <class Graph>
 
    33 void checkGraph() {
 
    33 void checkGraphBuild() {
 
    34   TEMPLATE_GRAPH_TYPEDEFS(Graph);
 
    34   TEMPLATE_GRAPH_TYPEDEFS(Graph);
 
    35 
    35 
    36   Graph G;
 
    36   Graph G;
 
    37   checkGraphNodeList(G, 0);
 
    37   checkGraphNodeList(G, 0);
 
    38   checkGraphEdgeList(G, 0);
 
    38   checkGraphEdgeList(G, 0);
 
       
    39   checkGraphArcList(G, 0);
 
    39 
    40 
    40   Node
 
    41   Node
 
    41     n1 = G.addNode(),
 
    42     n1 = G.addNode(),
 
    42     n2 = G.addNode(),
 
    43     n2 = G.addNode(),
 
    43     n3 = G.addNode();
 
    44     n3 = G.addNode();
 
    44   checkGraphNodeList(G, 3);
 
    45   checkGraphNodeList(G, 3);
 
    45   checkGraphEdgeList(G, 0);
 
    46   checkGraphEdgeList(G, 0);
 
       
    47   checkGraphArcList(G, 0);
 
    46 
    48 
    47   Edge e1 = G.addEdge(n1, n2);
 
    49   Edge e1 = G.addEdge(n1, n2);
 
    48   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
 
    50   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
 
    49         "Wrong edge");
 
    51         "Wrong edge");
 
    50   checkGraphNodeList(G, 3);
 
    52 
       
    53   checkGraphNodeList(G, 3);
 
       
    54   checkGraphEdgeList(G, 1);
 
    51   checkGraphArcList(G, 2);
 
    55   checkGraphArcList(G, 2);
 
    52   checkGraphEdgeList(G, 1);
 
    56 
    53 
    57   checkGraphIncEdgeArcLists(G, n1, 1);
 
    54   checkGraphOutArcList(G, n1, 1);
 
    58   checkGraphIncEdgeArcLists(G, n2, 1);
 
    55   checkGraphOutArcList(G, n2, 1);
 
    59   checkGraphIncEdgeArcLists(G, n3, 0);
 
    56   checkGraphOutArcList(G, n3, 0);
 
    60 
    57 
    61   checkGraphConEdgeList(G, 1);
 
    58   checkGraphInArcList(G, n1, 1);
 
       
    59   checkGraphInArcList(G, n2, 1);
 
       
    60   checkGraphInArcList(G, n3, 0);
 
       
    61 
       
    62   checkGraphIncEdgeList(G, n1, 1);
 
       
    63   checkGraphIncEdgeList(G, n2, 1);
 
       
    64   checkGraphIncEdgeList(G, n3, 0);
 
       
    65 
       
    66   checkGraphConArcList(G, 2);
 
    62   checkGraphConArcList(G, 2);
 
    67   checkGraphConEdgeList(G, 1);
 
    63 
    68 
    64   Edge e2 = G.addEdge(n2, n1),
 
    69   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
 
    65        e3 = G.addEdge(n2, n3);
 
    70   checkGraphNodeList(G, 3);
 
    66 
       
    67   checkGraphNodeList(G, 3);
 
       
    68   checkGraphEdgeList(G, 3);
 
    71   checkGraphArcList(G, 6);
 
    69   checkGraphArcList(G, 6);
 
    72   checkGraphEdgeList(G, 3);
 
    70 
    73 
    71   checkGraphIncEdgeArcLists(G, n1, 2);
 
    74   checkGraphOutArcList(G, n1, 2);
 
    72   checkGraphIncEdgeArcLists(G, n2, 3);
 
    75   checkGraphOutArcList(G, n2, 3);
 
    73   checkGraphIncEdgeArcLists(G, n3, 1);
 
    76   checkGraphOutArcList(G, n3, 1);
 
    74 
    77 
    75   checkGraphConEdgeList(G, 3);
 
    78   checkGraphInArcList(G, n1, 2);
 
       
    79   checkGraphInArcList(G, n2, 3);
 
       
    80   checkGraphInArcList(G, n3, 1);
 
       
    81 
       
    82   checkGraphIncEdgeList(G, n1, 2);
 
       
    83   checkGraphIncEdgeList(G, n2, 3);
 
       
    84   checkGraphIncEdgeList(G, n3, 1);
 
       
    85 
       
    86   checkGraphConArcList(G, 6);
 
    76   checkGraphConArcList(G, 6);
 
    87   checkGraphConEdgeList(G, 3);
 
       
    88 
    77 
    89   checkArcDirections(G);
 
    78   checkArcDirections(G);
 
    90 
    79 
    91   checkNodeIds(G);
 
    80   checkNodeIds(G);
 
    92   checkArcIds(G);
 
    81   checkArcIds(G);
 
    93   checkEdgeIds(G);
 
    82   checkEdgeIds(G);
 
    94   checkGraphNodeMap(G);
 
    83   checkGraphNodeMap(G);
 
    95   checkGraphArcMap(G);
 
    84   checkGraphArcMap(G);
 
    96   checkGraphEdgeMap(G);
 
    85   checkGraphEdgeMap(G);
 
       
    86 }
 
       
    87 
       
    88 template <class Graph>
 
       
    89 void checkGraphAlter() {
 
       
    90   TEMPLATE_GRAPH_TYPEDEFS(Graph);
 
       
    91 
       
    92   Graph G;
 
       
    93   Node n1 = G.addNode(), n2 = G.addNode(),
 
       
    94        n3 = G.addNode(), n4 = G.addNode();
 
       
    95   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
 
       
    96        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
 
       
    97        e5 = G.addEdge(n4, n3);
 
       
    98 
       
    99   checkGraphNodeList(G, 4);
 
       
   100   checkGraphEdgeList(G, 5);
 
       
   101   checkGraphArcList(G, 10);
 
       
   102 
       
   103   // Check changeU() and changeV()
 
       
   104   if (G.u(e2) == n2) {
 
       
   105     G.changeU(e2, n3);
 
       
   106   } else {
 
       
   107     G.changeV(e2, n3);
 
       
   108   }
 
       
   109 
       
   110   checkGraphNodeList(G, 4);
 
       
   111   checkGraphEdgeList(G, 5);
 
       
   112   checkGraphArcList(G, 10);
 
       
   113 
       
   114   checkGraphIncEdgeArcLists(G, n1, 3);
 
       
   115   checkGraphIncEdgeArcLists(G, n2, 2);
 
       
   116   checkGraphIncEdgeArcLists(G, n3, 3);
 
       
   117   checkGraphIncEdgeArcLists(G, n4, 2);
 
       
   118 
       
   119   checkGraphConEdgeList(G, 5);
 
       
   120   checkGraphConArcList(G, 10);
 
       
   121 
       
   122   if (G.u(e2) == n1) {
 
       
   123     G.changeU(e2, n2);
 
       
   124   } else {
 
       
   125     G.changeV(e2, n2);
 
       
   126   }
 
       
   127 
       
   128   checkGraphNodeList(G, 4);
 
       
   129   checkGraphEdgeList(G, 5);
 
       
   130   checkGraphArcList(G, 10);
 
       
   131 
       
   132   checkGraphIncEdgeArcLists(G, n1, 2);
 
       
   133   checkGraphIncEdgeArcLists(G, n2, 3);
 
       
   134   checkGraphIncEdgeArcLists(G, n3, 3);
 
       
   135   checkGraphIncEdgeArcLists(G, n4, 2);
 
       
   136 
       
   137   checkGraphConEdgeList(G, 5);
 
       
   138   checkGraphConArcList(G, 10);
 
       
   139 
       
   140   // Check contract()
 
       
   141   G.contract(n1, n4, false);
 
       
   142 
       
   143   checkGraphNodeList(G, 3);
 
       
   144   checkGraphEdgeList(G, 5);
 
       
   145   checkGraphArcList(G, 10);
 
       
   146 
       
   147   checkGraphIncEdgeArcLists(G, n1, 4);
 
       
   148   checkGraphIncEdgeArcLists(G, n2, 3);
 
       
   149   checkGraphIncEdgeArcLists(G, n3, 3);
 
       
   150 
       
   151   checkGraphConEdgeList(G, 5);
 
       
   152   checkGraphConArcList(G, 10);
 
       
   153 
       
   154   G.contract(n2, n3);
 
       
   155 
       
   156   checkGraphNodeList(G, 2);
 
       
   157   checkGraphEdgeList(G, 3);
 
       
   158   checkGraphArcList(G, 6);
 
       
   159 
       
   160   checkGraphIncEdgeArcLists(G, n1, 4);
 
       
   161   checkGraphIncEdgeArcLists(G, n2, 2);
 
       
   162 
       
   163   checkGraphConEdgeList(G, 3);
 
       
   164   checkGraphConArcList(G, 6);
 
       
   165 }
 
       
   166 
       
   167 template <class Graph>
 
       
   168 void checkGraphErase() {
 
       
   169   TEMPLATE_GRAPH_TYPEDEFS(Graph);
 
       
   170 
       
   171   Graph G;
 
       
   172   Node n1 = G.addNode(), n2 = G.addNode(),
 
       
   173        n3 = G.addNode(), n4 = G.addNode();
 
       
   174   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
 
       
   175        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
 
       
   176        e5 = G.addEdge(n4, n3);
 
       
   177 
       
   178   // Check edge deletion
 
       
   179   G.erase(e2);
 
       
   180 
       
   181   checkGraphNodeList(G, 4);
 
       
   182   checkGraphEdgeList(G, 4);
 
       
   183   checkGraphArcList(G, 8);
 
       
   184 
       
   185   checkGraphIncEdgeArcLists(G, n1, 2);
 
       
   186   checkGraphIncEdgeArcLists(G, n2, 2);
 
       
   187   checkGraphIncEdgeArcLists(G, n3, 2);
 
       
   188   checkGraphIncEdgeArcLists(G, n4, 2);
 
       
   189 
       
   190   checkGraphConEdgeList(G, 4);
 
       
   191   checkGraphConArcList(G, 8);
 
       
   192 
       
   193   // Check node deletion
 
       
   194   G.erase(n3);
 
       
   195 
       
   196   checkGraphNodeList(G, 3);
 
       
   197   checkGraphEdgeList(G, 2);
 
       
   198   checkGraphArcList(G, 4);
 
       
   199 
       
   200   checkGraphIncEdgeArcLists(G, n1, 2);
 
       
   201   checkGraphIncEdgeArcLists(G, n2, 1);
 
       
   202   checkGraphIncEdgeArcLists(G, n4, 1);
 
       
   203 
       
   204   checkGraphConEdgeList(G, 2);
 
       
   205   checkGraphConArcList(G, 4);
 
       
   206 }
 
       
   207 
       
   208 
       
   209 template <class Graph>
 
       
   210 void checkGraphSnapshot() {
 
       
   211   TEMPLATE_GRAPH_TYPEDEFS(Graph);
 
       
   212 
       
   213   Graph G;
 
       
   214   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
 
       
   215   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
 
       
   216        e3 = G.addEdge(n2, n3);
 
       
   217 
       
   218   checkGraphNodeList(G, 3);
 
       
   219   checkGraphEdgeList(G, 3);
 
       
   220   checkGraphArcList(G, 6);
 
       
   221 
       
   222   typename Graph::Snapshot snapshot(G);
 
       
   223 
       
   224   Node n = G.addNode();
 
       
   225   G.addEdge(n3, n);
 
       
   226   G.addEdge(n, n3);
 
       
   227   G.addEdge(n3, n2);
 
       
   228 
       
   229   checkGraphNodeList(G, 4);
 
       
   230   checkGraphEdgeList(G, 6);
 
       
   231   checkGraphArcList(G, 12);
 
       
   232 
       
   233   snapshot.restore();
 
       
   234 
       
   235   checkGraphNodeList(G, 3);
 
       
   236   checkGraphEdgeList(G, 3);
 
       
   237   checkGraphArcList(G, 6);
 
       
   238 
       
   239   checkGraphIncEdgeArcLists(G, n1, 2);
 
       
   240   checkGraphIncEdgeArcLists(G, n2, 3);
 
       
   241   checkGraphIncEdgeArcLists(G, n3, 1);
 
       
   242 
       
   243   checkGraphConEdgeList(G, 3);
 
       
   244   checkGraphConArcList(G, 6);
 
       
   245 
       
   246   checkNodeIds(G);
 
       
   247   checkEdgeIds(G);
 
       
   248   checkArcIds(G);
 
       
   249   checkGraphNodeMap(G);
 
       
   250   checkGraphEdgeMap(G);
 
       
   251   checkGraphArcMap(G);
 
       
   252 
       
   253   G.addNode();
 
       
   254   snapshot.save(G);
 
       
   255 
       
   256   G.addEdge(G.addNode(), G.addNode());
 
       
   257 
       
   258   snapshot.restore();
 
       
   259 
       
   260   checkGraphNodeList(G, 4);
 
       
   261   checkGraphEdgeList(G, 3);
 
       
   262   checkGraphArcList(G, 6);
 
    97 }
 
   263 }
 
    98 
   264 
    99 void checkFullGraph(int num) {
 
   265 void checkFullGraph(int num) {
 
   100   typedef FullGraph Graph;
 
   266   typedef FullGraph Graph;
 
   101   GRAPH_TYPEDEFS(Graph);
 
   267   GRAPH_TYPEDEFS(Graph);
 
   364   checkGraphEdgeMap(G);
 
   530   checkGraphEdgeMap(G);
 
   365 }
 
   531 }
 
   366 
   532 
   367 void checkGraphs() {
 
   533 void checkGraphs() {
 
   368   { // Checking ListGraph
 
   534   { // Checking ListGraph
 
   369     checkGraph<ListGraph>();
 
   535     checkGraphBuild<ListGraph>();
 
       
   536     checkGraphAlter<ListGraph>();
 
       
   537     checkGraphErase<ListGraph>();
 
       
   538     checkGraphSnapshot<ListGraph>();
 
   370     checkGraphValidityErase<ListGraph>();
 
   539     checkGraphValidityErase<ListGraph>();
 
   371   }
 
   540   }
 
   372   { // Checking SmartGraph
 
   541   { // Checking SmartGraph
 
   373     checkGraph<SmartGraph>();
 
   542     checkGraphBuild<SmartGraph>();
 
       
   543     checkGraphSnapshot<SmartGraph>();
 
   374     checkGraphValidity<SmartGraph>();
 
   544     checkGraphValidity<SmartGraph>();
 
   375   }
 
   545   }
 
   376   { // Checking FullGraph
 
   546   { // Checking FullGraph
 
   377     checkFullGraph(7);
 
   547     checkFullGraph(7);
 
   378     checkFullGraph(8);
 
   548     checkFullGraph(8);
lemon-main