test/digraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 04 Nov 2008 21:37:59 +0100
changeset 361 f58410582b9b
parent 353 37557a46e298
child 364 b4a01426c0d9
permissions -rw-r--r--
Doc improvements for the graph related tools in lemon/bits
     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 <lemon/concepts/digraph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
    23 //#include <lemon/hypercube_graph.h>
    24 
    25 #include "test_tools.h"
    26 #include "graph_test.h"
    27 
    28 using namespace lemon;
    29 using namespace lemon::concepts;
    30 
    31 template <class Digraph>
    32 void checkDigraph() {
    33   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    34   Digraph G;
    35 
    36   checkGraphNodeList(G, 0);
    37   checkGraphArcList(G, 0);
    38 
    39   Node
    40     n1 = G.addNode(),
    41     n2 = G.addNode(),
    42     n3 = G.addNode();
    43   checkGraphNodeList(G, 3);
    44   checkGraphArcList(G, 0);
    45 
    46   Arc a1 = G.addArc(n1, n2);
    47   check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
    48   checkGraphNodeList(G, 3);
    49   checkGraphArcList(G, 1);
    50 
    51   checkGraphOutArcList(G, n1, 1);
    52   checkGraphOutArcList(G, n2, 0);
    53   checkGraphOutArcList(G, n3, 0);
    54 
    55   checkGraphInArcList(G, n1, 0);
    56   checkGraphInArcList(G, n2, 1);
    57   checkGraphInArcList(G, n3, 0);
    58 
    59   checkGraphConArcList(G, 1);
    60 
    61   Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    62   checkGraphNodeList(G, 3);
    63   checkGraphArcList(G, 4);
    64 
    65   checkGraphOutArcList(G, n1, 1);
    66   checkGraphOutArcList(G, n2, 3);
    67   checkGraphOutArcList(G, n3, 0);
    68 
    69   checkGraphInArcList(G, n1, 1);
    70   checkGraphInArcList(G, n2, 1);
    71   checkGraphInArcList(G, n3, 2);
    72 
    73   checkGraphConArcList(G, 4);
    74 
    75   checkNodeIds(G);
    76   checkArcIds(G);
    77   checkGraphNodeMap(G);
    78   checkGraphArcMap(G);
    79 
    80 }
    81 
    82 void checkFullDigraph(int num) {
    83   typedef FullDigraph Digraph;
    84   DIGRAPH_TYPEDEFS(Digraph);
    85   Digraph G(num);
    86 
    87   checkGraphNodeList(G, num);
    88   checkGraphArcList(G, num * num);
    89 
    90   for (NodeIt n(G); n != INVALID; ++n) {
    91     checkGraphOutArcList(G, n, num);
    92     checkGraphInArcList(G, n, num);
    93   }
    94 
    95   checkGraphConArcList(G, num * num);
    96 
    97   checkNodeIds(G);
    98   checkArcIds(G);
    99   checkGraphNodeMap(G);
   100   checkGraphArcMap(G);
   101 
   102   for (int i = 0; i < G.nodeNum(); ++i) {
   103     check(G.index(G(i)) == i, "Wrong index");
   104   }
   105 
   106   for (NodeIt s(G); s != INVALID; ++s) {
   107     for (NodeIt t(G); t != INVALID; ++t) {
   108       Arc a = G.arc(s, t);
   109       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
   110     }
   111   }
   112 
   113 }
   114 
   115 
   116 void checkConcepts() {
   117   { // Checking digraph components
   118     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   119 
   120     checkConcept<IDableDigraphComponent<>,
   121       IDableDigraphComponent<> >();
   122 
   123     checkConcept<IterableDigraphComponent<>,
   124       IterableDigraphComponent<> >();
   125 
   126     checkConcept<MappableDigraphComponent<>,
   127       MappableDigraphComponent<> >();
   128   }
   129   { // Checking skeleton digraph
   130     checkConcept<Digraph, Digraph>();
   131   }
   132   { // Checking ListDigraph
   133     checkConcept<Digraph, ListDigraph>();
   134     checkConcept<AlterableDigraphComponent<>, ListDigraph>();
   135     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
   136     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
   137     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
   138   }
   139   { // Checking SmartDigraph
   140     checkConcept<Digraph, SmartDigraph>();
   141     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
   142     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
   143     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   144   }
   145   { // Checking FullDigraph
   146     checkConcept<Digraph, FullDigraph>();
   147   }
   148 //  { // Checking HyperCubeDigraph
   149 //    checkConcept<Digraph, HyperCubeDigraph>();
   150 //  }
   151 }
   152 
   153 template <typename Digraph>
   154 void checkDigraphValidity() {
   155   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   156   Digraph g;
   157 
   158   Node
   159     n1 = g.addNode(),
   160     n2 = g.addNode(),
   161     n3 = g.addNode();
   162 
   163   Arc
   164     e1 = g.addArc(n1, n2),
   165     e2 = g.addArc(n2, n3);
   166 
   167   check(g.valid(n1), "Wrong validity check");
   168   check(g.valid(e1), "Wrong validity check");
   169 
   170   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   171   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   172 }
   173 
   174 template <typename Digraph>
   175 void checkDigraphValidityErase() {
   176   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   177   Digraph g;
   178 
   179   Node
   180     n1 = g.addNode(),
   181     n2 = g.addNode(),
   182     n3 = g.addNode();
   183 
   184   Arc
   185     e1 = g.addArc(n1, n2),
   186     e2 = g.addArc(n2, n3);
   187 
   188   check(g.valid(n1), "Wrong validity check");
   189   check(g.valid(e1), "Wrong validity check");
   190 
   191   g.erase(n1);
   192 
   193   check(!g.valid(n1), "Wrong validity check");
   194   check(g.valid(n2), "Wrong validity check");
   195   check(g.valid(n3), "Wrong validity check");
   196   check(!g.valid(e1), "Wrong validity check");
   197   check(g.valid(e2), "Wrong validity check");
   198 
   199   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   200   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   201 }
   202 
   203 void checkDigraphs() {
   204   { // Checking ListDigraph
   205     checkDigraph<ListDigraph>();
   206     checkDigraphValidityErase<ListDigraph>();
   207   }
   208   { // Checking SmartDigraph
   209     checkDigraph<SmartDigraph>();
   210     checkDigraphValidity<SmartDigraph>();
   211   }
   212   { // Checking FullDigraph
   213     checkFullDigraph(8);
   214   }
   215 }
   216 
   217 int main() {
   218   checkDigraphs();
   219   checkConcepts();
   220   return 0;
   221 }