test/euler_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 12:53:30 +0200
branch1.1
changeset 815 eaed91c09e0f
parent 793 8d2e55fac752
parent 807 3e711ee55d31
permissions -rw-r--r--
Release series 1.1.x has reached its end of life.
     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-2011
     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     ::lemon::ignore_unused_variable_warning(n);
   105   
   106     checkDiEulerIt(d);
   107     checkDiEulerIt(g);
   108     checkEulerIt(g);
   109 
   110     check(eulerian(d), "This graph is Eulerian");
   111     check(eulerian(g), "This graph is Eulerian");
   112   }
   113   {
   114     Digraph d;
   115     Graph g(d);
   116     Digraph::Node n = d.addNode();
   117     d.addArc(n, n);
   118 
   119     checkDiEulerIt(d);
   120     checkDiEulerIt(g);
   121     checkEulerIt(g);
   122 
   123     check(eulerian(d), "This graph is Eulerian");
   124     check(eulerian(g), "This graph is Eulerian");
   125   }
   126   {
   127     Digraph d;
   128     Graph g(d);
   129     Digraph::Node n1 = d.addNode();
   130     Digraph::Node n2 = d.addNode();
   131     Digraph::Node n3 = d.addNode();
   132 
   133     d.addArc(n1, n2);
   134     d.addArc(n2, n1);
   135     d.addArc(n2, n3);
   136     d.addArc(n3, n2);
   137 
   138     checkDiEulerIt(d);
   139     checkDiEulerIt(d, n2);
   140     checkDiEulerIt(g);
   141     checkDiEulerIt(g, n2);
   142     checkEulerIt(g);
   143     checkEulerIt(g, n2);
   144 
   145     check(eulerian(d), "This graph is Eulerian");
   146     check(eulerian(g), "This graph is Eulerian");
   147   }
   148   {
   149     Digraph d;
   150     Graph g(d);
   151     Digraph::Node n1 = d.addNode();
   152     Digraph::Node n2 = d.addNode();
   153     Digraph::Node n3 = d.addNode();
   154     Digraph::Node n4 = d.addNode();
   155     Digraph::Node n5 = d.addNode();
   156     Digraph::Node n6 = d.addNode();
   157 
   158     d.addArc(n1, n2);
   159     d.addArc(n2, n4);
   160     d.addArc(n1, n3);
   161     d.addArc(n3, n4);
   162     d.addArc(n4, n1);
   163     d.addArc(n3, n5);
   164     d.addArc(n5, n2);
   165     d.addArc(n4, n6);
   166     d.addArc(n2, n6);
   167     d.addArc(n6, n1);
   168     d.addArc(n6, n3);
   169 
   170     checkDiEulerIt(d);
   171     checkDiEulerIt(d, n1);
   172     checkDiEulerIt(d, n5);
   173 
   174     checkDiEulerIt(g);
   175     checkDiEulerIt(g, n1);
   176     checkDiEulerIt(g, n5);
   177     checkEulerIt(g);
   178     checkEulerIt(g, n1);
   179     checkEulerIt(g, n5);
   180 
   181     check(eulerian(d), "This graph is Eulerian");
   182     check(eulerian(g), "This graph is Eulerian");
   183   }
   184   {
   185     Digraph d;
   186     Graph g(d);
   187     Digraph::Node n0 = d.addNode();
   188     Digraph::Node n1 = d.addNode();
   189     Digraph::Node n2 = d.addNode();
   190     Digraph::Node n3 = d.addNode();
   191     Digraph::Node n4 = d.addNode();
   192     Digraph::Node n5 = d.addNode();
   193     ::lemon::ignore_unused_variable_warning(n0,n4,n5);
   194 
   195     d.addArc(n1, n2);
   196     d.addArc(n2, n3);
   197     d.addArc(n3, n1);
   198 
   199     checkDiEulerIt(d);
   200     checkDiEulerIt(d, n2);
   201 
   202     checkDiEulerIt(g);
   203     checkDiEulerIt(g, n2);
   204     checkEulerIt(g);
   205     checkEulerIt(g, n2);
   206 
   207     check(!eulerian(d), "This graph is not Eulerian");
   208     check(!eulerian(g), "This graph is not Eulerian");
   209   }
   210   {
   211     Digraph d;
   212     Graph g(d);
   213     Digraph::Node n1 = d.addNode();
   214     Digraph::Node n2 = d.addNode();
   215     Digraph::Node n3 = d.addNode();
   216 
   217     d.addArc(n1, n2);
   218     d.addArc(n2, n3);
   219 
   220     check(!eulerian(d), "This graph is not Eulerian");
   221     check(!eulerian(g), "This graph is not Eulerian");
   222   }
   223 
   224   return 0;
   225 }