test/edge_set_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 468 68fe66e2b34a
child 877 141f9c0db4a3
child 997 761fe0846f49
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     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 
    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 }