Mercuriallemon / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/edge_set_test.cc
author Balazs Dezso <deba@google.com>
Thu, 08 Aug 2013 22:56:10 +0200
changeset 1265 552e3d1242c6
parent 1157 761fe0846f49
child 1258 bdfc038f364c
child 1259 8b2d4e5d96e4
permissions -rw-r--r--
Fix biNodeConnected() function (#439) 
     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-2008

     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 }
lemon