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