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