test/euler_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 29 Apr 2009 15:54:30 +0100
changeset 633 f5c710df882c
parent 531 ba7bafdc458d
child 877 141f9c0db4a3
child 997 761fe0846f49
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-2009
     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/euler.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/adaptors.h>
    22 #include "test_tools.h"
    23 
    24 using namespace lemon;
    25 
    26 template <typename Digraph>
    27 void checkDiEulerIt(const Digraph& g,
    28                     const typename Digraph::Node& start = INVALID)
    29 {
    30   typename Digraph::template ArcMap<int> visitationNumber(g, 0);
    31 
    32   DiEulerIt<Digraph> e(g, start);
    33   if (e == INVALID) return;
    34   typename Digraph::Node firstNode = g.source(e);
    35   typename Digraph::Node lastNode = g.target(e);
    36   if (start != INVALID) {
    37     check(firstNode == start, "checkDiEulerIt: Wrong first node");
    38   }
    39 
    40   for (; e != INVALID; ++e) {
    41     if (e != INVALID) lastNode = g.target(e);
    42     ++visitationNumber[e];
    43   }
    44 
    45   check(firstNode == lastNode,
    46       "checkDiEulerIt: First and last nodes are not the same");
    47 
    48   for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
    49   {
    50     check(visitationNumber[a] == 1,
    51         "checkDiEulerIt: Not visited or multiple times visited arc found");
    52   }
    53 }
    54 
    55 template <typename Graph>
    56 void checkEulerIt(const Graph& g,
    57                   const typename Graph::Node& start = INVALID)
    58 {
    59   typename Graph::template EdgeMap<int> visitationNumber(g, 0);
    60 
    61   EulerIt<Graph> e(g, start);
    62   if (e == INVALID) return;
    63   typename Graph::Node firstNode = g.source(typename Graph::Arc(e));
    64   typename Graph::Node lastNode = g.target(typename Graph::Arc(e));
    65   if (start != INVALID) {
    66     check(firstNode == start, "checkEulerIt: Wrong first node");
    67   }
    68 
    69   for (; e != INVALID; ++e) {
    70     if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));
    71     ++visitationNumber[e];
    72   }
    73 
    74   check(firstNode == lastNode,
    75       "checkEulerIt: First and last nodes are not the same");
    76 
    77   for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
    78   {
    79     check(visitationNumber[e] == 1,
    80         "checkEulerIt: Not visited or multiple times visited edge found");
    81   }
    82 }
    83 
    84 int main()
    85 {
    86   typedef ListDigraph Digraph;
    87   typedef Undirector<Digraph> Graph;
    88   
    89   {
    90     Digraph d;
    91     Graph g(d);
    92     
    93     checkDiEulerIt(d);
    94     checkDiEulerIt(g);
    95     checkEulerIt(g);
    96 
    97     check(eulerian(d), "This graph is Eulerian");
    98     check(eulerian(g), "This graph is Eulerian");
    99   }
   100   {
   101     Digraph d;
   102     Graph g(d);
   103     Digraph::Node n = d.addNode();
   104 
   105     checkDiEulerIt(d);
   106     checkDiEulerIt(g);
   107     checkEulerIt(g);
   108 
   109     check(eulerian(d), "This graph is Eulerian");
   110     check(eulerian(g), "This graph is Eulerian");
   111   }
   112   {
   113     Digraph d;
   114     Graph g(d);
   115     Digraph::Node n = d.addNode();
   116     d.addArc(n, n);
   117 
   118     checkDiEulerIt(d);
   119     checkDiEulerIt(g);
   120     checkEulerIt(g);
   121 
   122     check(eulerian(d), "This graph is Eulerian");
   123     check(eulerian(g), "This graph is Eulerian");
   124   }
   125   {
   126     Digraph d;
   127     Graph g(d);
   128     Digraph::Node n1 = d.addNode();
   129     Digraph::Node n2 = d.addNode();
   130     Digraph::Node n3 = d.addNode();
   131     
   132     d.addArc(n1, n2);
   133     d.addArc(n2, n1);
   134     d.addArc(n2, n3);
   135     d.addArc(n3, n2);
   136 
   137     checkDiEulerIt(d);
   138     checkDiEulerIt(d, n2);
   139     checkDiEulerIt(g);
   140     checkDiEulerIt(g, n2);
   141     checkEulerIt(g);
   142     checkEulerIt(g, n2);
   143 
   144     check(eulerian(d), "This graph is Eulerian");
   145     check(eulerian(g), "This graph is Eulerian");
   146   }
   147   {
   148     Digraph d;
   149     Graph g(d);
   150     Digraph::Node n1 = d.addNode();
   151     Digraph::Node n2 = d.addNode();
   152     Digraph::Node n3 = d.addNode();
   153     Digraph::Node n4 = d.addNode();
   154     Digraph::Node n5 = d.addNode();
   155     Digraph::Node n6 = d.addNode();
   156     
   157     d.addArc(n1, n2);
   158     d.addArc(n2, n4);
   159     d.addArc(n1, n3);
   160     d.addArc(n3, n4);
   161     d.addArc(n4, n1);
   162     d.addArc(n3, n5);
   163     d.addArc(n5, n2);
   164     d.addArc(n4, n6);
   165     d.addArc(n2, n6);
   166     d.addArc(n6, n1);
   167     d.addArc(n6, n3);
   168 
   169     checkDiEulerIt(d);
   170     checkDiEulerIt(d, n1);
   171     checkDiEulerIt(d, n5);
   172 
   173     checkDiEulerIt(g);
   174     checkDiEulerIt(g, n1);
   175     checkDiEulerIt(g, n5);
   176     checkEulerIt(g);
   177     checkEulerIt(g, n1);
   178     checkEulerIt(g, n5);
   179 
   180     check(eulerian(d), "This graph is Eulerian");
   181     check(eulerian(g), "This graph is Eulerian");
   182   }
   183   {
   184     Digraph d;
   185     Graph g(d);
   186     Digraph::Node n0 = d.addNode();
   187     Digraph::Node n1 = d.addNode();
   188     Digraph::Node n2 = d.addNode();
   189     Digraph::Node n3 = d.addNode();
   190     Digraph::Node n4 = d.addNode();
   191     Digraph::Node n5 = d.addNode();
   192     
   193     d.addArc(n1, n2);
   194     d.addArc(n2, n3);
   195     d.addArc(n3, n1);
   196 
   197     checkDiEulerIt(d);
   198     checkDiEulerIt(d, n2);
   199 
   200     checkDiEulerIt(g);
   201     checkDiEulerIt(g, n2);
   202     checkEulerIt(g);
   203     checkEulerIt(g, n2);
   204 
   205     check(!eulerian(d), "This graph is not Eulerian");
   206     check(!eulerian(g), "This graph is not Eulerian");
   207   }
   208   {
   209     Digraph d;
   210     Graph g(d);
   211     Digraph::Node n1 = d.addNode();
   212     Digraph::Node n2 = d.addNode();
   213     Digraph::Node n3 = d.addNode();
   214     
   215     d.addArc(n1, n2);
   216     d.addArc(n2, n3);
   217 
   218     check(!eulerian(d), "This graph is not Eulerian");
   219     check(!eulerian(g), "This graph is not Eulerian");
   220   }
   221 
   222   return 0;
   223 }