test/euler_test.cc
changeset 537 0fec6a017ead
child 531 ba7bafdc458d
equal deleted inserted replaced
-1:000000000000 0:94ffa78f548d
       
     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 <test/test_tools.h>
       
    22 
       
    23 using namespace lemon;
       
    24 
       
    25 template <typename Digraph>
       
    26 void checkDiEulerIt(const Digraph& g)
       
    27 {
       
    28   typename Digraph::template ArcMap<int> visitationNumber(g);
       
    29 
       
    30   DiEulerIt<Digraph> e(g);
       
    31   typename Digraph::Node firstNode = g.source(e);
       
    32   typename Digraph::Node lastNode;
       
    33 
       
    34   for (; e != INVALID; ++e)
       
    35   {
       
    36     if (e != INVALID)
       
    37     {
       
    38       lastNode = g.target(e);
       
    39     }
       
    40     ++visitationNumber[e];
       
    41   }
       
    42 
       
    43   check(firstNode == lastNode,
       
    44       "checkDiEulerIt: first and last node are not the same");
       
    45 
       
    46   for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
       
    47   {
       
    48     check(visitationNumber[a] == 1,
       
    49         "checkDiEulerIt: not visited or multiple times visited arc found");
       
    50   }
       
    51 }
       
    52 
       
    53 template <typename Graph>
       
    54 void checkEulerIt(const Graph& g)
       
    55 {
       
    56   typename Graph::template EdgeMap<int> visitationNumber(g);
       
    57 
       
    58   EulerIt<Graph> e(g);
       
    59   typename Graph::Node firstNode = g.u(e);
       
    60   typename Graph::Node lastNode;
       
    61 
       
    62   for (; e != INVALID; ++e)
       
    63   {
       
    64     if (e != INVALID)
       
    65     {
       
    66       lastNode = g.v(e);
       
    67     }
       
    68     ++visitationNumber[e];
       
    69   }
       
    70 
       
    71   check(firstNode == lastNode,
       
    72       "checkEulerIt: first and last node are not the same");
       
    73 
       
    74   for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
       
    75   {
       
    76     check(visitationNumber[e] == 1,
       
    77         "checkEulerIt: not visited or multiple times visited edge found");
       
    78   }
       
    79 }
       
    80 
       
    81 int main()
       
    82 {
       
    83   typedef ListDigraph Digraph;
       
    84   typedef ListGraph Graph;
       
    85 
       
    86   Digraph digraphWithEulerianCircuit;
       
    87   {
       
    88     Digraph& g = digraphWithEulerianCircuit;
       
    89 
       
    90     Digraph::Node n0 = g.addNode();
       
    91     Digraph::Node n1 = g.addNode();
       
    92     Digraph::Node n2 = g.addNode();
       
    93 
       
    94     g.addArc(n0, n1);
       
    95     g.addArc(n1, n0);
       
    96     g.addArc(n1, n2);
       
    97     g.addArc(n2, n1);
       
    98   }
       
    99 
       
   100   Digraph digraphWithoutEulerianCircuit;
       
   101   {
       
   102     Digraph& g = digraphWithoutEulerianCircuit;
       
   103 
       
   104     Digraph::Node n0 = g.addNode();
       
   105     Digraph::Node n1 = g.addNode();
       
   106     Digraph::Node n2 = g.addNode();
       
   107 
       
   108     g.addArc(n0, n1);
       
   109     g.addArc(n1, n0);
       
   110     g.addArc(n1, n2);
       
   111   }
       
   112 
       
   113   Graph graphWithEulerianCircuit;
       
   114   {
       
   115     Graph& g = graphWithEulerianCircuit;
       
   116 
       
   117     Graph::Node n0 = g.addNode();
       
   118     Graph::Node n1 = g.addNode();
       
   119     Graph::Node n2 = g.addNode();
       
   120 
       
   121     g.addEdge(n0, n1);
       
   122     g.addEdge(n1, n2);
       
   123     g.addEdge(n2, n0);
       
   124   }
       
   125 
       
   126   Graph graphWithoutEulerianCircuit;
       
   127   {
       
   128     Graph& g = graphWithoutEulerianCircuit;
       
   129 
       
   130     Graph::Node n0 = g.addNode();
       
   131     Graph::Node n1 = g.addNode();
       
   132     Graph::Node n2 = g.addNode();
       
   133 
       
   134     g.addEdge(n0, n1);
       
   135     g.addEdge(n1, n2);
       
   136   }
       
   137 
       
   138   checkDiEulerIt(digraphWithEulerianCircuit);
       
   139 
       
   140   checkEulerIt(graphWithEulerianCircuit);
       
   141 
       
   142   check(eulerian(digraphWithEulerianCircuit),
       
   143       "this graph should have an Eulerian circuit");
       
   144   check(!eulerian(digraphWithoutEulerianCircuit),
       
   145       "this graph should not have an Eulerian circuit");
       
   146 
       
   147   check(eulerian(graphWithEulerianCircuit),
       
   148       "this graph should have an Eulerian circuit");
       
   149   check(!eulerian(graphWithoutEulerianCircuit),
       
   150       "this graph should have an Eulerian circuit");
       
   151 
       
   152   return 0;
       
   153 }