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 Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 651 8c3112a66878
parent 491 68fe66e2b34a
child 956 141f9c0db4a3
child 1081 f1398882a928
child 1157 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 }
lemon