test/euler_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sat, 28 Mar 2009 10:36:53 +0000
changeset 557 3bd0484f4cc2
parent 522 22f932bbb305
child 592 2ebfdb89ec66
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 <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, 0);
    29 
    30   DiEulerIt<Digraph> e(g);
    31   typename Digraph::Node firstNode = g.source(e);
    32   typename Digraph::Node lastNode = g.target(e);
    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, 0);
    57 
    58   EulerIt<Graph> e(g);
    59   typename Graph::Node firstNode = g.u(e);
    60   typename Graph::Node lastNode = g.v(e);
    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 }