test/edge_set_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 15:31:02 +0200
branch1.3
changeset 1287 fbb7ddd13c8b
parent 1259 8b2d4e5d96e4
permissions -rw-r--r--
Merge headmerge to branch 1.3
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     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 <iostream>
    20 #include <vector>
    21 
    22 #include <lemon/concepts/digraph.h>
    23 #include <lemon/concepts/graph.h>
    24 #include <lemon/concept_check.h>
    25 
    26 #include <lemon/list_graph.h>
    27 
    28 #include <lemon/edge_set.h>
    29 
    30 #include "graph_test.h"
    31 #include "test_tools.h"
    32 
    33 using namespace lemon;
    34 
    35 void checkSmartArcSet() {
    36   checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
    37 
    38   typedef ListDigraph Digraph;
    39   typedef SmartArcSet<Digraph> ArcSet;
    40 
    41   Digraph digraph;
    42   Digraph::Node
    43     n1 = digraph.addNode(),
    44     n2 = digraph.addNode();
    45 
    46   Digraph::Arc ga1 = digraph.addArc(n1, n2);
    47   ::lemon::ignore_unused_variable_warning(ga1);
    48 
    49   ArcSet arc_set(digraph);
    50 
    51   Digraph::Arc ga2 = digraph.addArc(n2, n1);
    52   ::lemon::ignore_unused_variable_warning(ga2);
    53 
    54   checkGraphNodeList(arc_set, 2);
    55   checkGraphArcList(arc_set, 0);
    56 
    57   Digraph::Node
    58     n3 = digraph.addNode();
    59   checkGraphNodeList(arc_set, 3);
    60   checkGraphArcList(arc_set, 0);
    61 
    62   ArcSet::Arc a1 = arc_set.addArc(n1, n2);
    63   check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
    64   checkGraphNodeList(arc_set, 3);
    65   checkGraphArcList(arc_set, 1);
    66 
    67   checkGraphOutArcList(arc_set, n1, 1);
    68   checkGraphOutArcList(arc_set, n2, 0);
    69   checkGraphOutArcList(arc_set, n3, 0);
    70 
    71   checkGraphInArcList(arc_set, n1, 0);
    72   checkGraphInArcList(arc_set, n2, 1);
    73   checkGraphInArcList(arc_set, n3, 0);
    74 
    75   checkGraphConArcList(arc_set, 1);
    76 
    77   ArcSet::Arc a2 = arc_set.addArc(n2, n1),
    78     a3 = arc_set.addArc(n2, n3),
    79     a4 = arc_set.addArc(n2, n3);
    80   ::lemon::ignore_unused_variable_warning(a2,a3,a4);
    81 
    82   checkGraphNodeList(arc_set, 3);
    83   checkGraphArcList(arc_set, 4);
    84 
    85   checkGraphOutArcList(arc_set, n1, 1);
    86   checkGraphOutArcList(arc_set, n2, 3);
    87   checkGraphOutArcList(arc_set, n3, 0);
    88 
    89   checkGraphInArcList(arc_set, n1, 1);
    90   checkGraphInArcList(arc_set, n2, 1);
    91   checkGraphInArcList(arc_set, n3, 2);
    92 
    93   checkGraphConArcList(arc_set, 4);
    94 
    95   checkNodeIds(arc_set);
    96   checkArcIds(arc_set);
    97   checkGraphNodeMap(arc_set);
    98   checkGraphArcMap(arc_set);
    99 
   100   check(arc_set.valid(), "Wrong validity");
   101   digraph.erase(n1);
   102   check(!arc_set.valid(), "Wrong validity");
   103 }
   104 
   105 void checkListArcSet() {
   106   checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
   107 
   108   typedef ListDigraph Digraph;
   109   typedef ListArcSet<Digraph> ArcSet;
   110 
   111   Digraph digraph;
   112   Digraph::Node
   113     n1 = digraph.addNode(),
   114     n2 = digraph.addNode();
   115 
   116   Digraph::Arc ga1 = digraph.addArc(n1, n2);
   117   ::lemon::ignore_unused_variable_warning(ga1);
   118 
   119   ArcSet arc_set(digraph);
   120 
   121   Digraph::Arc ga2 = digraph.addArc(n2, n1);
   122   ::lemon::ignore_unused_variable_warning(ga2);
   123 
   124   checkGraphNodeList(arc_set, 2);
   125   checkGraphArcList(arc_set, 0);
   126 
   127   Digraph::Node
   128     n3 = digraph.addNode();
   129   checkGraphNodeList(arc_set, 3);
   130   checkGraphArcList(arc_set, 0);
   131 
   132   ArcSet::Arc a1 = arc_set.addArc(n1, n2);
   133   check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
   134   checkGraphNodeList(arc_set, 3);
   135   checkGraphArcList(arc_set, 1);
   136 
   137   checkGraphOutArcList(arc_set, n1, 1);
   138   checkGraphOutArcList(arc_set, n2, 0);
   139   checkGraphOutArcList(arc_set, n3, 0);
   140 
   141   checkGraphInArcList(arc_set, n1, 0);
   142   checkGraphInArcList(arc_set, n2, 1);
   143   checkGraphInArcList(arc_set, n3, 0);
   144 
   145   checkGraphConArcList(arc_set, 1);
   146 
   147   ArcSet::Arc a2 = arc_set.addArc(n2, n1),
   148     a3 = arc_set.addArc(n2, n3),
   149     a4 = arc_set.addArc(n2, n3);
   150   ::lemon::ignore_unused_variable_warning(a2,a3,a4);
   151 
   152   checkGraphNodeList(arc_set, 3);
   153   checkGraphArcList(arc_set, 4);
   154 
   155   checkGraphOutArcList(arc_set, n1, 1);
   156   checkGraphOutArcList(arc_set, n2, 3);
   157   checkGraphOutArcList(arc_set, n3, 0);
   158 
   159   checkGraphInArcList(arc_set, n1, 1);
   160   checkGraphInArcList(arc_set, n2, 1);
   161   checkGraphInArcList(arc_set, n3, 2);
   162 
   163   checkGraphConArcList(arc_set, 4);
   164 
   165   checkNodeIds(arc_set);
   166   checkArcIds(arc_set);
   167   checkGraphNodeMap(arc_set);
   168   checkGraphArcMap(arc_set);
   169 
   170   digraph.erase(n1);
   171 
   172   checkGraphNodeList(arc_set, 2);
   173   checkGraphArcList(arc_set, 2);
   174 
   175   checkGraphOutArcList(arc_set, n2, 2);
   176   checkGraphOutArcList(arc_set, n3, 0);
   177 
   178   checkGraphInArcList(arc_set, n2, 0);
   179   checkGraphInArcList(arc_set, n3, 2);
   180 
   181   checkNodeIds(arc_set);
   182   checkArcIds(arc_set);
   183   checkGraphNodeMap(arc_set);
   184   checkGraphArcMap(arc_set);
   185 
   186   checkGraphConArcList(arc_set, 2);
   187 }
   188 
   189 void checkSmartEdgeSet() {
   190   checkConcept<concepts::Digraph, SmartEdgeSet<ListDigraph> >();
   191 
   192   typedef ListDigraph Digraph;
   193   typedef SmartEdgeSet<Digraph> EdgeSet;
   194 
   195   Digraph digraph;
   196   Digraph::Node
   197     n1 = digraph.addNode(),
   198     n2 = digraph.addNode();
   199 
   200   Digraph::Arc ga1 = digraph.addArc(n1, n2);
   201   ::lemon::ignore_unused_variable_warning(ga1);
   202 
   203   EdgeSet edge_set(digraph);
   204 
   205   Digraph::Arc ga2 = digraph.addArc(n2, n1);
   206   ::lemon::ignore_unused_variable_warning(ga2);
   207 
   208   checkGraphNodeList(edge_set, 2);
   209   checkGraphArcList(edge_set, 0);
   210   checkGraphEdgeList(edge_set, 0);
   211 
   212   Digraph::Node
   213     n3 = digraph.addNode();
   214   checkGraphNodeList(edge_set, 3);
   215   checkGraphArcList(edge_set, 0);
   216   checkGraphEdgeList(edge_set, 0);
   217 
   218   EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
   219   check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
   220         (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
   221   checkGraphNodeList(edge_set, 3);
   222   checkGraphArcList(edge_set, 2);
   223   checkGraphEdgeList(edge_set, 1);
   224 
   225   checkGraphOutArcList(edge_set, n1, 1);
   226   checkGraphOutArcList(edge_set, n2, 1);
   227   checkGraphOutArcList(edge_set, n3, 0);
   228 
   229   checkGraphInArcList(edge_set, n1, 1);
   230   checkGraphInArcList(edge_set, n2, 1);
   231   checkGraphInArcList(edge_set, n3, 0);
   232 
   233   checkGraphIncEdgeList(edge_set, n1, 1);
   234   checkGraphIncEdgeList(edge_set, n2, 1);
   235   checkGraphIncEdgeList(edge_set, n3, 0);
   236 
   237   checkGraphConEdgeList(edge_set, 1);
   238   checkGraphConArcList(edge_set, 2);
   239 
   240   EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
   241     e3 = edge_set.addEdge(n2, n3),
   242     e4 = edge_set.addEdge(n2, n3);
   243   ::lemon::ignore_unused_variable_warning(e2,e3,e4);
   244 
   245   checkGraphNodeList(edge_set, 3);
   246   checkGraphEdgeList(edge_set, 4);
   247 
   248   checkGraphOutArcList(edge_set, n1, 2);
   249   checkGraphOutArcList(edge_set, n2, 4);
   250   checkGraphOutArcList(edge_set, n3, 2);
   251 
   252   checkGraphInArcList(edge_set, n1, 2);
   253   checkGraphInArcList(edge_set, n2, 4);
   254   checkGraphInArcList(edge_set, n3, 2);
   255 
   256   checkGraphIncEdgeList(edge_set, n1, 2);
   257   checkGraphIncEdgeList(edge_set, n2, 4);
   258   checkGraphIncEdgeList(edge_set, n3, 2);
   259 
   260   checkGraphConEdgeList(edge_set, 4);
   261   checkGraphConArcList(edge_set, 8);
   262 
   263   checkArcDirections(edge_set);
   264 
   265   checkNodeIds(edge_set);
   266   checkArcIds(edge_set);
   267   checkEdgeIds(edge_set);
   268   checkGraphNodeMap(edge_set);
   269   checkGraphArcMap(edge_set);
   270   checkGraphEdgeMap(edge_set);
   271 
   272   check(edge_set.valid(), "Wrong validity");
   273   digraph.erase(n1);
   274   check(!edge_set.valid(), "Wrong validity");
   275 }
   276 
   277 void checkListEdgeSet() {
   278   checkConcept<concepts::Digraph, ListEdgeSet<ListDigraph> >();
   279 
   280   typedef ListDigraph Digraph;
   281   typedef ListEdgeSet<Digraph> EdgeSet;
   282 
   283   Digraph digraph;
   284   Digraph::Node
   285     n1 = digraph.addNode(),
   286     n2 = digraph.addNode();
   287 
   288   Digraph::Arc ga1 = digraph.addArc(n1, n2);
   289   ::lemon::ignore_unused_variable_warning(ga1);
   290 
   291   EdgeSet edge_set(digraph);
   292 
   293   Digraph::Arc ga2 = digraph.addArc(n2, n1);
   294   ::lemon::ignore_unused_variable_warning(ga2);
   295 
   296   checkGraphNodeList(edge_set, 2);
   297   checkGraphArcList(edge_set, 0);
   298   checkGraphEdgeList(edge_set, 0);
   299 
   300   Digraph::Node
   301     n3 = digraph.addNode();
   302   checkGraphNodeList(edge_set, 3);
   303   checkGraphArcList(edge_set, 0);
   304   checkGraphEdgeList(edge_set, 0);
   305 
   306   EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
   307   check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
   308         (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
   309   checkGraphNodeList(edge_set, 3);
   310   checkGraphArcList(edge_set, 2);
   311   checkGraphEdgeList(edge_set, 1);
   312 
   313   checkGraphOutArcList(edge_set, n1, 1);
   314   checkGraphOutArcList(edge_set, n2, 1);
   315   checkGraphOutArcList(edge_set, n3, 0);
   316 
   317   checkGraphInArcList(edge_set, n1, 1);
   318   checkGraphInArcList(edge_set, n2, 1);
   319   checkGraphInArcList(edge_set, n3, 0);
   320 
   321   checkGraphIncEdgeList(edge_set, n1, 1);
   322   checkGraphIncEdgeList(edge_set, n2, 1);
   323   checkGraphIncEdgeList(edge_set, n3, 0);
   324 
   325   checkGraphConEdgeList(edge_set, 1);
   326   checkGraphConArcList(edge_set, 2);
   327 
   328   EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
   329     e3 = edge_set.addEdge(n2, n3),
   330     e4 = edge_set.addEdge(n2, n3);
   331   ::lemon::ignore_unused_variable_warning(e2,e3,e4);
   332 
   333   checkGraphNodeList(edge_set, 3);
   334   checkGraphEdgeList(edge_set, 4);
   335 
   336   checkGraphOutArcList(edge_set, n1, 2);
   337   checkGraphOutArcList(edge_set, n2, 4);
   338   checkGraphOutArcList(edge_set, n3, 2);
   339 
   340   checkGraphInArcList(edge_set, n1, 2);
   341   checkGraphInArcList(edge_set, n2, 4);
   342   checkGraphInArcList(edge_set, n3, 2);
   343 
   344   checkGraphIncEdgeList(edge_set, n1, 2);
   345   checkGraphIncEdgeList(edge_set, n2, 4);
   346   checkGraphIncEdgeList(edge_set, n3, 2);
   347 
   348   checkGraphConEdgeList(edge_set, 4);
   349   checkGraphConArcList(edge_set, 8);
   350 
   351   checkArcDirections(edge_set);
   352 
   353   checkNodeIds(edge_set);
   354   checkArcIds(edge_set);
   355   checkEdgeIds(edge_set);
   356   checkGraphNodeMap(edge_set);
   357   checkGraphArcMap(edge_set);
   358   checkGraphEdgeMap(edge_set);
   359 
   360   digraph.erase(n1);
   361 
   362   checkGraphNodeList(edge_set, 2);
   363   checkGraphArcList(edge_set, 4);
   364   checkGraphEdgeList(edge_set, 2);
   365 
   366   checkGraphOutArcList(edge_set, n2, 2);
   367   checkGraphOutArcList(edge_set, n3, 2);
   368 
   369   checkGraphInArcList(edge_set, n2, 2);
   370   checkGraphInArcList(edge_set, n3, 2);
   371 
   372   checkGraphIncEdgeList(edge_set, n2, 2);
   373   checkGraphIncEdgeList(edge_set, n3, 2);
   374 
   375   checkNodeIds(edge_set);
   376   checkArcIds(edge_set);
   377   checkEdgeIds(edge_set);
   378   checkGraphNodeMap(edge_set);
   379   checkGraphArcMap(edge_set);
   380   checkGraphEdgeMap(edge_set);
   381 
   382   checkGraphConEdgeList(edge_set, 2);
   383   checkGraphConArcList(edge_set, 4);
   384 
   385 }
   386 
   387 
   388 int main() {
   389 
   390   checkSmartArcSet();
   391   checkListArcSet();
   392   checkSmartEdgeSet();
   393   checkListEdgeSet();
   394 
   395   return 0;
   396 }