test/edge_set_test.cc
changeset 473 17d918051964
child 488 9b9ffe7d9b75
equal deleted inserted replaced
-1:000000000000 0:cac8ff5ec2ef
       
     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<concepts::Digraph> >();
       
    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 
       
    48   ArcSet arc_set(digraph);
       
    49 
       
    50   Digraph::Arc ga2 = digraph.addArc(n2, n1);
       
    51 
       
    52   checkGraphNodeList(arc_set, 2);
       
    53   checkGraphArcList(arc_set, 0);
       
    54 
       
    55   Digraph::Node
       
    56     n3 = digraph.addNode();
       
    57   checkGraphNodeList(arc_set, 3);
       
    58   checkGraphArcList(arc_set, 0);
       
    59 
       
    60   ArcSet::Arc a1 = arc_set.addArc(n1, n2);
       
    61   check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
       
    62   checkGraphNodeList(arc_set, 3);
       
    63   checkGraphArcList(arc_set, 1);
       
    64 
       
    65   checkGraphOutArcList(arc_set, n1, 1);
       
    66   checkGraphOutArcList(arc_set, n2, 0);
       
    67   checkGraphOutArcList(arc_set, n3, 0);
       
    68 
       
    69   checkGraphInArcList(arc_set, n1, 0);
       
    70   checkGraphInArcList(arc_set, n2, 1);
       
    71   checkGraphInArcList(arc_set, n3, 0);
       
    72 
       
    73   checkGraphConArcList(arc_set, 1);
       
    74 
       
    75   ArcSet::Arc a2 = arc_set.addArc(n2, n1),
       
    76     a3 = arc_set.addArc(n2, n3),
       
    77     a4 = arc_set.addArc(n2, n3);
       
    78   checkGraphNodeList(arc_set, 3);
       
    79   checkGraphArcList(arc_set, 4);
       
    80 
       
    81   checkGraphOutArcList(arc_set, n1, 1);
       
    82   checkGraphOutArcList(arc_set, n2, 3);
       
    83   checkGraphOutArcList(arc_set, n3, 0);
       
    84 
       
    85   checkGraphInArcList(arc_set, n1, 1);
       
    86   checkGraphInArcList(arc_set, n2, 1);
       
    87   checkGraphInArcList(arc_set, n3, 2);
       
    88 
       
    89   checkGraphConArcList(arc_set, 4);
       
    90 
       
    91   checkNodeIds(arc_set);
       
    92   checkArcIds(arc_set);
       
    93   checkGraphNodeMap(arc_set);
       
    94   checkGraphArcMap(arc_set);
       
    95 
       
    96   check(arc_set.valid(), "Wrong validity");
       
    97   digraph.erase(n1);
       
    98   check(!arc_set.valid(), "Wrong validity");
       
    99 }
       
   100 
       
   101 void checkListArcSet() {
       
   102   checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
       
   103 
       
   104   typedef ListDigraph Digraph;
       
   105   typedef ListArcSet<Digraph> ArcSet;
       
   106 
       
   107   Digraph digraph;
       
   108   Digraph::Node
       
   109     n1 = digraph.addNode(),
       
   110     n2 = digraph.addNode();
       
   111 
       
   112   Digraph::Arc ga1 = digraph.addArc(n1, n2);
       
   113 
       
   114   ArcSet arc_set(digraph);
       
   115 
       
   116   Digraph::Arc ga2 = digraph.addArc(n2, n1);
       
   117 
       
   118   checkGraphNodeList(arc_set, 2);
       
   119   checkGraphArcList(arc_set, 0);
       
   120 
       
   121   Digraph::Node
       
   122     n3 = digraph.addNode();
       
   123   checkGraphNodeList(arc_set, 3);
       
   124   checkGraphArcList(arc_set, 0);
       
   125 
       
   126   ArcSet::Arc a1 = arc_set.addArc(n1, n2);
       
   127   check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
       
   128   checkGraphNodeList(arc_set, 3);
       
   129   checkGraphArcList(arc_set, 1);
       
   130 
       
   131   checkGraphOutArcList(arc_set, n1, 1);
       
   132   checkGraphOutArcList(arc_set, n2, 0);
       
   133   checkGraphOutArcList(arc_set, n3, 0);
       
   134 
       
   135   checkGraphInArcList(arc_set, n1, 0);
       
   136   checkGraphInArcList(arc_set, n2, 1);
       
   137   checkGraphInArcList(arc_set, n3, 0);
       
   138 
       
   139   checkGraphConArcList(arc_set, 1);
       
   140 
       
   141   ArcSet::Arc a2 = arc_set.addArc(n2, n1),
       
   142     a3 = arc_set.addArc(n2, n3),
       
   143     a4 = arc_set.addArc(n2, n3);
       
   144   checkGraphNodeList(arc_set, 3);
       
   145   checkGraphArcList(arc_set, 4);
       
   146 
       
   147   checkGraphOutArcList(arc_set, n1, 1);
       
   148   checkGraphOutArcList(arc_set, n2, 3);
       
   149   checkGraphOutArcList(arc_set, n3, 0);
       
   150 
       
   151   checkGraphInArcList(arc_set, n1, 1);
       
   152   checkGraphInArcList(arc_set, n2, 1);
       
   153   checkGraphInArcList(arc_set, n3, 2);
       
   154 
       
   155   checkGraphConArcList(arc_set, 4);
       
   156 
       
   157   checkNodeIds(arc_set);
       
   158   checkArcIds(arc_set);
       
   159   checkGraphNodeMap(arc_set);
       
   160   checkGraphArcMap(arc_set);
       
   161 
       
   162   digraph.erase(n1);
       
   163 
       
   164   checkGraphNodeList(arc_set, 2);
       
   165   checkGraphArcList(arc_set, 2);
       
   166 
       
   167   checkGraphOutArcList(arc_set, n2, 2);
       
   168   checkGraphOutArcList(arc_set, n3, 0);
       
   169 
       
   170   checkGraphInArcList(arc_set, n2, 0);
       
   171   checkGraphInArcList(arc_set, n3, 2);
       
   172 
       
   173   checkNodeIds(arc_set);
       
   174   checkArcIds(arc_set);
       
   175   checkGraphNodeMap(arc_set);
       
   176   checkGraphArcMap(arc_set);
       
   177 
       
   178   checkGraphConArcList(arc_set, 2);
       
   179 }
       
   180 
       
   181 void checkSmartEdgeSet() {
       
   182   checkConcept<concepts::Digraph, SmartEdgeSet<concepts::Digraph> >();
       
   183 
       
   184   typedef ListDigraph Digraph;
       
   185   typedef SmartEdgeSet<Digraph> EdgeSet;
       
   186 
       
   187   Digraph digraph;
       
   188   Digraph::Node
       
   189     n1 = digraph.addNode(),
       
   190     n2 = digraph.addNode();
       
   191 
       
   192   Digraph::Arc ga1 = digraph.addArc(n1, n2);
       
   193 
       
   194   EdgeSet edge_set(digraph);
       
   195 
       
   196   Digraph::Arc ga2 = digraph.addArc(n2, n1);
       
   197 
       
   198   checkGraphNodeList(edge_set, 2);
       
   199   checkGraphArcList(edge_set, 0);
       
   200   checkGraphEdgeList(edge_set, 0);
       
   201 
       
   202   Digraph::Node
       
   203     n3 = digraph.addNode();
       
   204   checkGraphNodeList(edge_set, 3);
       
   205   checkGraphArcList(edge_set, 0);
       
   206   checkGraphEdgeList(edge_set, 0);
       
   207 
       
   208   EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
       
   209   check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
       
   210         (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
       
   211   checkGraphNodeList(edge_set, 3);
       
   212   checkGraphArcList(edge_set, 2);
       
   213   checkGraphEdgeList(edge_set, 1);
       
   214 
       
   215   checkGraphOutArcList(edge_set, n1, 1);
       
   216   checkGraphOutArcList(edge_set, n2, 1);
       
   217   checkGraphOutArcList(edge_set, n3, 0);
       
   218 
       
   219   checkGraphInArcList(edge_set, n1, 1);
       
   220   checkGraphInArcList(edge_set, n2, 1);
       
   221   checkGraphInArcList(edge_set, n3, 0);
       
   222 
       
   223   checkGraphIncEdgeList(edge_set, n1, 1);
       
   224   checkGraphIncEdgeList(edge_set, n2, 1);
       
   225   checkGraphIncEdgeList(edge_set, n3, 0);
       
   226 
       
   227   checkGraphConEdgeList(edge_set, 1);
       
   228   checkGraphConArcList(edge_set, 2);
       
   229 
       
   230   EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
       
   231     e3 = edge_set.addEdge(n2, n3),
       
   232     e4 = edge_set.addEdge(n2, n3);
       
   233   checkGraphNodeList(edge_set, 3);
       
   234   checkGraphEdgeList(edge_set, 4);
       
   235 
       
   236   checkGraphOutArcList(edge_set, n1, 2);
       
   237   checkGraphOutArcList(edge_set, n2, 4);
       
   238   checkGraphOutArcList(edge_set, n3, 2);
       
   239 
       
   240   checkGraphInArcList(edge_set, n1, 2);
       
   241   checkGraphInArcList(edge_set, n2, 4);
       
   242   checkGraphInArcList(edge_set, n3, 2);
       
   243 
       
   244   checkGraphIncEdgeList(edge_set, n1, 2);
       
   245   checkGraphIncEdgeList(edge_set, n2, 4);
       
   246   checkGraphIncEdgeList(edge_set, n3, 2);
       
   247 
       
   248   checkGraphConEdgeList(edge_set, 4);
       
   249   checkGraphConArcList(edge_set, 8);
       
   250 
       
   251   checkArcDirections(edge_set);
       
   252 
       
   253   checkNodeIds(edge_set);
       
   254   checkArcIds(edge_set);
       
   255   checkEdgeIds(edge_set);
       
   256   checkGraphNodeMap(edge_set);
       
   257   checkGraphArcMap(edge_set);
       
   258   checkGraphEdgeMap(edge_set);
       
   259 
       
   260   check(edge_set.valid(), "Wrong validity");
       
   261   digraph.erase(n1);
       
   262   check(!edge_set.valid(), "Wrong validity");
       
   263 }
       
   264 
       
   265 void checkListEdgeSet() {
       
   266   checkConcept<concepts::Digraph, ListEdgeSet<concepts::Digraph> >();
       
   267 
       
   268   typedef ListDigraph Digraph;
       
   269   typedef ListEdgeSet<Digraph> EdgeSet;
       
   270 
       
   271   Digraph digraph;
       
   272   Digraph::Node
       
   273     n1 = digraph.addNode(),
       
   274     n2 = digraph.addNode();
       
   275 
       
   276   Digraph::Arc ga1 = digraph.addArc(n1, n2);
       
   277 
       
   278   EdgeSet edge_set(digraph);
       
   279 
       
   280   Digraph::Arc ga2 = digraph.addArc(n2, n1);
       
   281 
       
   282   checkGraphNodeList(edge_set, 2);
       
   283   checkGraphArcList(edge_set, 0);
       
   284   checkGraphEdgeList(edge_set, 0);
       
   285 
       
   286   Digraph::Node
       
   287     n3 = digraph.addNode();
       
   288   checkGraphNodeList(edge_set, 3);
       
   289   checkGraphArcList(edge_set, 0);
       
   290   checkGraphEdgeList(edge_set, 0);
       
   291 
       
   292   EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
       
   293   check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
       
   294         (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
       
   295   checkGraphNodeList(edge_set, 3);
       
   296   checkGraphArcList(edge_set, 2);
       
   297   checkGraphEdgeList(edge_set, 1);
       
   298 
       
   299   checkGraphOutArcList(edge_set, n1, 1);
       
   300   checkGraphOutArcList(edge_set, n2, 1);
       
   301   checkGraphOutArcList(edge_set, n3, 0);
       
   302 
       
   303   checkGraphInArcList(edge_set, n1, 1);
       
   304   checkGraphInArcList(edge_set, n2, 1);
       
   305   checkGraphInArcList(edge_set, n3, 0);
       
   306 
       
   307   checkGraphIncEdgeList(edge_set, n1, 1);
       
   308   checkGraphIncEdgeList(edge_set, n2, 1);
       
   309   checkGraphIncEdgeList(edge_set, n3, 0);
       
   310 
       
   311   checkGraphConEdgeList(edge_set, 1);
       
   312   checkGraphConArcList(edge_set, 2);
       
   313 
       
   314   EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
       
   315     e3 = edge_set.addEdge(n2, n3),
       
   316     e4 = edge_set.addEdge(n2, n3);
       
   317   checkGraphNodeList(edge_set, 3);
       
   318   checkGraphEdgeList(edge_set, 4);
       
   319 
       
   320   checkGraphOutArcList(edge_set, n1, 2);
       
   321   checkGraphOutArcList(edge_set, n2, 4);
       
   322   checkGraphOutArcList(edge_set, n3, 2);
       
   323 
       
   324   checkGraphInArcList(edge_set, n1, 2);
       
   325   checkGraphInArcList(edge_set, n2, 4);
       
   326   checkGraphInArcList(edge_set, n3, 2);
       
   327 
       
   328   checkGraphIncEdgeList(edge_set, n1, 2);
       
   329   checkGraphIncEdgeList(edge_set, n2, 4);
       
   330   checkGraphIncEdgeList(edge_set, n3, 2);
       
   331 
       
   332   checkGraphConEdgeList(edge_set, 4);
       
   333   checkGraphConArcList(edge_set, 8);
       
   334 
       
   335   checkArcDirections(edge_set);
       
   336 
       
   337   checkNodeIds(edge_set);
       
   338   checkArcIds(edge_set);
       
   339   checkEdgeIds(edge_set);
       
   340   checkGraphNodeMap(edge_set);
       
   341   checkGraphArcMap(edge_set);
       
   342   checkGraphEdgeMap(edge_set);
       
   343 
       
   344   digraph.erase(n1);
       
   345 
       
   346   checkGraphNodeList(edge_set, 2);
       
   347   checkGraphArcList(edge_set, 4);
       
   348   checkGraphEdgeList(edge_set, 2);
       
   349 
       
   350   checkGraphOutArcList(edge_set, n2, 2);
       
   351   checkGraphOutArcList(edge_set, n3, 2);
       
   352 
       
   353   checkGraphInArcList(edge_set, n2, 2);
       
   354   checkGraphInArcList(edge_set, n3, 2);
       
   355 
       
   356   checkGraphIncEdgeList(edge_set, n2, 2);
       
   357   checkGraphIncEdgeList(edge_set, n3, 2);
       
   358 
       
   359   checkNodeIds(edge_set);
       
   360   checkArcIds(edge_set);
       
   361   checkEdgeIds(edge_set);
       
   362   checkGraphNodeMap(edge_set);
       
   363   checkGraphArcMap(edge_set);
       
   364   checkGraphEdgeMap(edge_set);
       
   365 
       
   366   checkGraphConEdgeList(edge_set, 2);
       
   367   checkGraphConArcList(edge_set, 4);
       
   368 
       
   369 }
       
   370 
       
   371 
       
   372 int main() {
       
   373 
       
   374   checkSmartArcSet();
       
   375   checkListArcSet();
       
   376   checkSmartEdgeSet();
       
   377   checkListEdgeSet();
       
   378 
       
   379   return 0;
       
   380 }