COIN-OR::LEMON - Graph Library

Changeset 592:2ebfdb89ec66 in lemon-1.2 for test


Ignore:
Timestamp:
04/15/09 11:47:19 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements for the Euler tools and the test file (#264)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/euler_test.cc

    r531 r592  
    1919#include <lemon/euler.h>
    2020#include <lemon/list_graph.h>
    21 #include <test/test_tools.h>
     21#include <lemon/adaptors.h>
     22#include "test_tools.h"
    2223
    2324using namespace lemon;
    2425
    2526template <typename Digraph>
    26 void checkDiEulerIt(const Digraph& g)
     27void checkDiEulerIt(const Digraph& g,
     28                    const typename Digraph::Node& start = INVALID)
    2729{
    2830  typename Digraph::template ArcMap<int> visitationNumber(g, 0);
    2931
    30   DiEulerIt<Digraph> e(g);
     32  DiEulerIt<Digraph> e(g, start);
     33  if (e == INVALID) return;
    3134  typename Digraph::Node firstNode = g.source(e);
    3235  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     }
     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);
    4042    ++visitationNumber[e];
    4143  }
    4244
    4345  check(firstNode == lastNode,
    44       "checkDiEulerIt: first and last node are not the same");
     46      "checkDiEulerIt: First and last nodes are not the same");
    4547
    4648  for (typename Digraph::ArcIt a(g); a != INVALID; ++a)
    4749  {
    4850    check(visitationNumber[a] == 1,
    49         "checkDiEulerIt: not visited or multiple times visited arc found");
     51        "checkDiEulerIt: Not visited or multiple times visited arc found");
    5052  }
    5153}
    5254
    5355template <typename Graph>
    54 void checkEulerIt(const Graph& g)
     56void checkEulerIt(const Graph& g,
     57                  const typename Graph::Node& start = INVALID)
    5558{
    5659  typename Graph::template EdgeMap<int> visitationNumber(g, 0);
    5760
    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     }
     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));
    6871    ++visitationNumber[e];
    6972  }
    7073
    7174  check(firstNode == lastNode,
    72       "checkEulerIt: first and last node are not the same");
     75      "checkEulerIt: First and last nodes are not the same");
    7376
    7477  for (typename Graph::EdgeIt e(g); e != INVALID; ++e)
    7578  {
    7679    check(visitationNumber[e] == 1,
    77         "checkEulerIt: not visited or multiple times visited edge found");
     80        "checkEulerIt: Not visited or multiple times visited edge found");
    7881  }
    7982}
     
    8285{
    8386  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");
     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  }
    151221
    152222  return 0;
Note: See TracChangeset for help on using the changeset viewer.