test/edge_set_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 06 May 2012 16:52:11 +0200
branch1.2
changeset 1142 4764031c082c
parent 559 9b9ffe7d9b75
child 1159 7fdaa05a69a1
permissions -rw-r--r--
Merge bugfix #441 to branch 1.2
     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-2010
     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 
    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<ListDigraph> >();
   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<ListDigraph> >();
   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<ListDigraph> >();
   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 }