Changeset - r592:2ebfdb89ec66
« 591:493533
595:16d725 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Improvements for the Euler tools and the test file (#264)
0 2 0
default
2 files changed with 238 insertions and 157 deletions:
lemon/euler.h
95
84
test/euler_test.cc
143
73
↑ Collapse diff ↑
lemon/euler.h
Ignore white space 6 line context
... ... 
@@ -28,7 +28,7 @@
28 28 
/// \file
29 
/// \brief Euler tour
29 
/// \brief Euler tour iterators and a function for checking the \e Eulerian
30 
/// property.
30 31 
///
31 
///This file provides an Euler tour iterator and ways to check
32 
///if a digraph is euler.
33 

			




	
	32
	
		
///This file provides Euler tour iterators and a function to check


			




	
	33
	
		
///if a (di)graph is \e Eulerian.


			




	34
	34
	
		

			




	...
	...
	
		
@@ -36,21 +36,19 @@


			




	36
	36
	
		

			




	37
	
	
		
  ///Euler iterator for digraphs.


			




	
	37
	
		
  ///Euler tour iterator for digraphs.


			




	38
	38
	
		

			




	39
	
	
		
  /// \ingroup graph_properties


			




	40
	
	
		
  ///This iterator converts to the \c Arc type of the digraph and using


			




	41
	
	
		
  ///operator ++, it provides an Euler tour of a \e directed


			




	42
	
	
		
  ///graph (if there exists).


			




	
	39
	
		
  /// \ingroup graph_prop


			




	
	40
	
		
  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed


			




	
	41
	
		
  ///graph (if there exists) and it converts to the \c Arc type of the digraph.


			




	43
	42
	
		
  ///


			




	44
	
	
		
  ///For example


			




	45
	
	
		
  ///if the given digraph is Euler (i.e it has only one nontrivial component


			




	46
	
	
		
  ///and the in-degree is equal to the out-degree for all nodes),


			




	47
	
	
		
  ///the following code will put the arcs of \c g


			




	48
	
	
		
  ///to the vector \c et according to an


			




	49
	
	
		
  ///Euler tour of \c g.


			




	
	43
	
		
  ///For example, if the given digraph has an Euler tour (i.e it has only one


			




	
	44
	
		
  ///non-trivial component and the in-degree is equal to the out-degree 


			




	
	45
	
		
  ///for all nodes), then the following code will put the arcs of \c g


			




	
	46
	
		
  ///to the vector \c et according to an Euler tour of \c g.


			




	50
	47
	
		
  ///\code


			




	51
	48
	
		
  ///  std::vector<ListDigraph::Arc> et;


			




	52
	
	
		
  ///  for(DiEulerIt<ListDigraph> e(g),e!=INVALID;++e)


			




	
	49
	
		
  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)


			




	53
	50
	
		
  ///    et.push_back(e);


			




	54
	51
	
		
  ///\endcode


			




	55
	
	
		
  ///If \c g is not Euler then the resulted tour will not be full or closed.


			




	
	52
	
		
  ///If \c g has no Euler tour, then the resulted walk will not be closed


			




	
	53
	
		
  ///or not contain all arcs.


			




	56
	54
	
		
  ///\sa EulerIt


			




	...
	...
	
		
@@ -67,3 +65,3 @@


			




	67
	65
	
		
    const GR &g;


			




	68
	
	
		
    typename GR::template NodeMap<OutArcIt> nedge;


			




	
	66
	
		
    typename GR::template NodeMap<OutArcIt> narc;


			




	69
	67
	
		
    std::list<Arc> euler;


			




	...
	...
	
		
@@ -74,7 +72,8 @@


			




	74
	72
	
		

			




	
	73
	
		
    ///Constructor.


			




	75
	74
	
		
    ///\param gr A digraph.


			




	76
	
	
		
    ///\param start The starting point of the tour. If it is not given


			




	77
	
	
		
    ///       the tour will start from the first node.


			




	
	75
	
		
    ///\param start The starting point of the tour. If it is not given,


			




	
	76
	
		
    ///the tour will start from the first node that has an outgoing arc.


			




	78
	77
	
		
    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)


			




	79
	
	
		
      : g(gr), nedge(g)


			




	
	78
	
		
      : g(gr), narc(g)


			




	80
	79
	
		
    {


			




	...
	...
	
		
@@ -86,7 +85,7 @@


			




	86
	85
	
		
      if (start!=INVALID) {


			




	87
	
	
		
        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);


			




	88
	
	
		
        while (nedge[start]!=INVALID) {


			




	89
	
	
		
          euler.push_back(nedge[start]);


			




	90
	
	
		
          Node next=g.target(nedge[start]);


			




	91
	
	
		
          ++nedge[start];


			




	
	86
	
		
        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);


			




	
	87
	
		
        while (narc[start]!=INVALID) {


			




	
	88
	
		
          euler.push_back(narc[start]);


			




	
	89
	
		
          Node next=g.target(narc[start]);


			




	
	90
	
		
          ++narc[start];


			




	92
	91
	
		
          start=next;


			




	...
	...
	
		
@@ -96,5 +95,7 @@


			




	96
	95
	
		

			




	97
	
	
		
    ///Arc Conversion


			




	
	96
	
		
    ///Arc conversion


			




	98
	97
	
		
    operator Arc() { return euler.empty()?INVALID:euler.front(); }


			




	
	98
	
		
    ///Compare with \c INVALID


			




	99
	99
	
		
    bool operator==(Invalid) { return euler.empty(); }


			




	
	100
	
		
    ///Compare with \c INVALID


			




	100
	101
	
		
    bool operator!=(Invalid) { return !euler.empty(); }


			




	...
	...
	
		
@@ -102,2 +103,5 @@


			




	102
	103
	
		
    ///Next arc of the tour


			




	
	104
	
		

			




	
	105
	
		
    ///Next arc of the tour


			




	
	106
	
		
    ///


			




	103
	107
	
		
    DiEulerIt &operator++() {


			




	...
	...
	
		
@@ -105,9 +109,7 @@


			




	105
	109
	
		
      euler.pop_front();


			




	106
	
	
		
      //This produces a warning.Strange.


			




	107
	
	
		
      //std::list<Arc>::iterator next=euler.begin();


			




	108
	110
	
		
      typename std::list<Arc>::iterator next=euler.begin();


			




	109
	
	
		
      while(nedge[s]!=INVALID) {


			




	110
	
	
		
        euler.insert(next,nedge[s]);


			




	111
	
	
		
        Node n=g.target(nedge[s]);


			




	112
	
	
		
        ++nedge[s];


			




	
	111
	
		
      while(narc[s]!=INVALID) {


			




	
	112
	
		
        euler.insert(next,narc[s]);


			




	
	113
	
		
        Node n=g.target(narc[s]);


			




	
	114
	
		
        ++narc[s];


			




	113
	115
	
		
        s=n;


			




	...
	...
	
		
@@ -118,4 +120,6 @@


			




	118
	120
	
		

			




	
	121
	
		
    /// Postfix incrementation.


			




	
	122
	
		
    ///


			




	119
	123
	
		
    ///\warning This incrementation


			




	120
	
	
		
    ///returns an \c Arc, not an \ref DiEulerIt, as one may


			




	
	124
	
		
    ///returns an \c Arc, not a \ref DiEulerIt, as one may


			




	121
	125
	
		
    ///expect.


			




	...
	...
	
		
@@ -129,13 +133,11 @@


			




	129
	133
	
		

			




	130
	
	
		
  ///Euler iterator for graphs.


			




	
	134
	
		
  ///Euler tour iterator for graphs.


			




	131
	135
	
		

			




	132
	136
	
		
  /// \ingroup graph_properties


			




	133
	
	
		
  ///This iterator converts to the \c Arc (or \c Edge)


			




	134
	
	
		
  ///type of the digraph and using


			




	135
	
	
		
  ///operator ++, it provides an Euler tour of an undirected


			




	136
	
	
		
  ///digraph (if there exists).


			




	
	137
	
		
  ///This iterator provides an Euler tour (Eulerian circuit) of an


			




	
	138
	
		
  ///\e undirected graph (if there exists) and it converts to the \c Arc


			




	
	139
	
		
  ///and \c Edge types of the graph.


			




	137
	140
	
		
  ///


			




	138
	
	
		
  ///For example


			




	139
	
	
		
  ///if the given digraph if Euler (i.e it has only one nontrivial component


			




	140
	
	
		
  ///and the degree of each node is even),


			




	
	141
	
		
  ///For example, if the given graph has an Euler tour (i.e it has only one 


			




	
	142
	
		
  ///non-trivial component and the degree of each node is even),


			




	141
	143
	
		
  ///the following code will print the arc IDs according to an


			




	...
	...
	
		
@@ -143,3 +145,3 @@


			




	143
	145
	
		
  ///\code


			




	144
	
	
		
  ///  for(EulerIt<ListGraph> e(g),e!=INVALID;++e) {


			




	
	146
	
		
  ///  for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) {


			




	145
	147
	
		
  ///    std::cout << g.id(Edge(e)) << std::eol;


			




	...
	...
	
		
@@ -147,8 +149,8 @@


			




	147
	149
	
		
  ///\endcode


			




	148
	
	
		
  ///Although the iterator provides an Euler tour of an graph,


			




	149
	
	
		
  ///it still returns Arcs in order to indicate the direction of the tour.


			




	150
	
	
		
  ///(But Arc will convert to Edges, of course).


			




	
	150
	
		
  ///Although this iterator is for undirected graphs, it still returns 


			




	
	151
	
		
  ///arcs in order to indicate the direction of the tour.


			




	
	152
	
		
  ///(But arcs convert to edges, of course.)


			




	151
	153
	
		
  ///


			




	152
	
	
		
  ///If \c g is not Euler then the resulted tour will not be full or closed.


			




	153
	
	
		
  ///\sa EulerIt


			




	
	154
	
		
  ///If \c g has no Euler tour, then the resulted walk will not be closed


			




	
	155
	
		
  ///or not contain all edges.


			




	154
	156
	
		
  template<typename GR>


			




	...
	...
	
		
@@ -165,3 +167,3 @@


			




	165
	167
	
		
    const GR &g;


			




	166
	
	
		
    typename GR::template NodeMap<OutArcIt> nedge;


			




	
	168
	
		
    typename GR::template NodeMap<OutArcIt> narc;


			




	167
	169
	
		
    typename GR::template EdgeMap<bool> visited;


			




	...
	...
	
		
@@ -173,7 +175,8 @@


			




	173
	175
	
		

			




	174
	
	
		
    ///\param gr An graph.


			




	175
	
	
		
    ///\param start The starting point of the tour. If it is not given


			




	176
	
	
		
    ///       the tour will start from the first node.


			




	
	176
	
		
    ///Constructor.


			




	
	177
	
		
    ///\param gr A graph.


			




	
	178
	
		
    ///\param start The starting point of the tour. If it is not given,


			




	
	179
	
		
    ///the tour will start from the first node that has an incident edge.


			




	177
	180
	
		
    EulerIt(const GR &gr, typename GR::Node start = INVALID)


			




	178
	
	
		
      : g(gr), nedge(g), visited(g, false)


			




	
	181
	
		
      : g(gr), narc(g), visited(g, false)


			




	179
	182
	
		
    {


			




	...
	...
	
		
@@ -185,10 +188,10 @@


			




	185
	188
	
		
      if (start!=INVALID) {


			




	186
	
	
		
        for (NodeIt n(g); n!=INVALID; ++n) nedge[n]=OutArcIt(g,n);


			




	187
	
	
		
        while(nedge[start]!=INVALID) {


			




	188
	
	
		
          euler.push_back(nedge[start]);


			




	189
	
	
		
          visited[nedge[start]]=true;


			




	190
	
	
		
          Node next=g.target(nedge[start]);


			




	191
	
	
		
          ++nedge[start];


			




	
	189
	
		
        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);


			




	
	190
	
		
        while(narc[start]!=INVALID) {


			




	
	191
	
		
          euler.push_back(narc[start]);


			




	
	192
	
		
          visited[narc[start]]=true;


			




	
	193
	
		
          Node next=g.target(narc[start]);


			




	
	194
	
		
          ++narc[start];


			




	192
	195
	
		
          start=next;


			




	193
	
	
		
          while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];


			




	
	196
	
		
          while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start];


			




	194
	197
	
		
        }


			




	...
	...
	
		
@@ -197,9 +200,9 @@


			




	197
	200
	
		

			




	198
	
	
		
    ///Arc Conversion


			




	
	201
	
		
    ///Arc conversion


			




	199
	202
	
		
    operator Arc() const { return euler.empty()?INVALID:euler.front(); }


			




	200
	
	
		
    ///Arc Conversion


			




	
	203
	
		
    ///Edge conversion


			




	201
	204
	
		
    operator Edge() const { return euler.empty()?INVALID:euler.front(); }


			




	202
	
	
		
    ///\e


			




	
	205
	
		
    ///Compare with \c INVALID


			




	203
	206
	
		
    bool operator==(Invalid) const { return euler.empty(); }


			




	204
	
	
		
    ///\e


			




	
	207
	
		
    ///Compare with \c INVALID


			




	205
	208
	
		
    bool operator!=(Invalid) const { return !euler.empty(); }


			




	...
	...
	
		
@@ -207,2 +210,5 @@


			




	207
	210
	
		
    ///Next arc of the tour


			




	
	211
	
		

			




	
	212
	
		
    ///Next arc of the tour


			




	
	213
	
		
    ///


			




	208
	214
	
		
    EulerIt &operator++() {


			




	...
	...
	
		
@@ -211,11 +217,10 @@


			




	211
	217
	
		
      typename std::list<Arc>::iterator next=euler.begin();


			




	212
	
	
		

			




	213
	
	
		
      while(nedge[s]!=INVALID) {


			




	214
	
	
		
        while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];


			




	215
	
	
		
        if(nedge[s]==INVALID) break;


			




	
	218
	
		
      while(narc[s]!=INVALID) {


			




	
	219
	
		
        while(narc[s]!=INVALID && visited[narc[s]]) ++narc[s];


			




	
	220
	
		
        if(narc[s]==INVALID) break;


			




	216
	221
	
		
        else {


			




	217
	
	
		
          euler.insert(next,nedge[s]);


			




	218
	
	
		
          visited[nedge[s]]=true;


			




	219
	
	
		
          Node n=g.target(nedge[s]);


			




	220
	
	
		
          ++nedge[s];


			




	
	222
	
		
          euler.insert(next,narc[s]);


			




	
	223
	
		
          visited[narc[s]]=true;


			




	
	224
	
		
          Node n=g.target(narc[s]);


			




	
	225
	
		
          ++narc[s];


			




	221
	226
	
		
          s=n;


			




	...
	...
	
		
@@ -228,5 +233,6 @@


			




	228
	233
	
		

			




	229
	
	
		
    ///\warning This incrementation


			




	230
	
	
		
    ///returns an \c Arc, not an \ref EulerIt, as one may


			




	231
	
	
		
    ///expect.


			




	
	234
	
		
    /// Postfix incrementation.


			




	
	235
	
		
    ///


			




	
	236
	
		
    ///\warning This incrementation returns an \c Arc (which converts to 


			




	
	237
	
		
    ///an \c Edge), not an \ref EulerIt, as one may expect.


			




	232
	238
	
		
    Arc operator++(int)


			




	...
	...
	
		
@@ -240,14 +246,19 @@


			




	240
	246
	
		

			




	241
	
	
		
  ///Checks if the graph is Eulerian


			




	
	247
	
		
  ///Check if the given graph is \e Eulerian


			




	242
	248
	
		

			




	243
	249
	
		
  /// \ingroup graph_properties


			




	244
	
	
		
  ///Checks if the graph is Eulerian. It works for both directed and undirected


			




	245
	
	
		
  ///graphs.


			




	246
	
	
		
  ///\note By definition, a digraph is called \e Eulerian if


			




	247
	
	
		
  ///and only if it is connected and the number of its incoming and outgoing


			




	
	250
	
		
  ///This function checks if the given graph is \e Eulerian.


			




	
	251
	
		
  ///It works for both directed and undirected graphs.


			




	
	252
	
		
  ///


			




	
	253
	
		
  ///By definition, a digraph is called \e Eulerian if


			




	
	254
	
		
  ///and only if it is connected and the number of incoming and outgoing


			




	248
	255
	
		
  ///arcs are the same for each node.


			




	249
	256
	
		
  ///Similarly, an undirected graph is called \e Eulerian if


			




	250
	
	
		
  ///and only if it is connected and the number of incident arcs is even


			




	251
	
	
		
  ///for each node. <em>Therefore, there are digraphs which are not Eulerian,


			




	252
	
	
		
  ///but still have an Euler tour</em>.


			




	
	257
	
		
  ///and only if it is connected and the number of incident edges is even


			




	
	258
	
		
  ///for each node.


			




	
	259
	
		
  ///


			




	
	260
	
		
  ///\note There are (di)graphs that are not Eulerian, but still have an


			




	
	261
	
		
  /// Euler tour, since they may contain isolated nodes.


			




	
	262
	
		
  ///


			




	
	263
	
		
  ///\sa DiEulerIt, EulerIt


			




	253
	264
	
		
  template<typename GR>


			




	...
	...
	
		
@@ -270,3 +281,3 @@


			




	270
	281
	
		
      if(countInArcs(g,n)!=countOutArcs(g,n)) return false;


			




	271
	
	
		
    return connected(Undirector<const GR>(g));


			




	
	282
	
		
    return connected(undirector(g));


			




	272
	283
	
		
  }

			




        

    

    

    

        

            

                

                    test/euler_test.cc
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -20,3 +20,4 @@


			




	20
	20
	
		
#include <lemon/list_graph.h>


			




	21
	
	
		
#include <test/test_tools.h>


			




	
	21
	
		
#include <lemon/adaptors.h>


			




	
	22
	
		
#include "test_tools.h"


			




	22
	23
	
		

			




	...
	...
	
		
@@ -25,3 +26,4 @@


			




	25
	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
	
		
{


			




	...
	...
	
		
@@ -29,12 +31,12 @@


			




	29
	31
	
		

			




	30
	
	
		
  DiEulerIt<Digraph> e(g);


			




	
	32
	
		
  DiEulerIt<Digraph> e(g, start);


			




	
	33
	
		
  if (e == INVALID) return;


			




	31
	34
	
		
  typename Digraph::Node firstNode = g.source(e);


			




	32
	35
	
		
  typename Digraph::Node lastNode = g.target(e);


			




	
	36
	
		
  if (start != INVALID) {


			




	
	37
	
		
    check(firstNode == start, "checkDiEulerIt: Wrong first node");


			




	
	38
	
		
  }


			




	33
	39
	
		

			




	34
	
	
		
  for (; e != INVALID; ++e)


			




	35
	
	
		
  {


			




	36
	
	
		
    if (e != INVALID)


			




	37
	
	
		
    {


			




	38
	
	
		
      lastNode = g.target(e);


			




	39
	
	
		
    }


			




	
	40
	
		
  for (; e != INVALID; ++e) {


			




	
	41
	
		
    if (e != INVALID) lastNode = g.target(e);


			




	40
	42
	
		
    ++visitationNumber[e];


			




	...
	...
	
		
@@ -43,3 +45,3 @@


			




	43
	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
	
		

			




	...
	...
	
		
@@ -48,3 +50,3 @@


			




	48
	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
	
		
  }


			




	...
	...
	
		
@@ -53,3 +55,4 @@


			




	53
	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
	
		
{


			




	...
	...
	
		
@@ -57,12 +60,12 @@


			




	57
	60
	
		

			




	58
	
	
		
  EulerIt<Graph> e(g);


			




	59
	
	
		
  typename Graph::Node firstNode = g.u(e);


			




	60
	
	
		
  typename Graph::Node lastNode = g.v(e);


			




	
	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
	
		
  }


			




	61
	68
	
		

			




	62
	
	
		
  for (; e != INVALID; ++e)


			




	63
	
	
		
  {


			




	64
	
	
		
    if (e != INVALID)


			




	65
	
	
		
    {


			




	66
	
	
		
      lastNode = g.v(e);


			




	67
	
	
		
    }


			




	
	69
	
		
  for (; e != INVALID; ++e) {


			




	
	70
	
		
    if (e != INVALID) lastNode = g.target(typename Graph::Arc(e));


			




	68
	71
	
		
    ++visitationNumber[e];


			




	...
	...
	
		
@@ -71,3 +74,3 @@


			




	71
	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
	
		

			




	...
	...
	
		
@@ -76,3 +79,3 @@


			




	76
	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
	
		
  }


			




	...
	...
	
		
@@ -83,70 +86,137 @@


			




	83
	86
	
		
  typedef ListDigraph Digraph;


			




	84
	
	
		
  typedef ListGraph Graph;


			




	
	87
	
		
  typedef Undirector<Digraph> Graph;


			




	
	88
	
		
  


			




	
	89
	
		
  {


			




	
	90
	
		
    Digraph d;


			




	
	91
	
		
    Graph g(d);


			




	
	92
	
		
    


			




	
	93
	
		
    checkDiEulerIt(d);


			




	
	94
	
		
    checkDiEulerIt(g);


			




	
	95
	
		
    checkEulerIt(g);


			




	85
	96
	
		

			




	86
	
	
		
  Digraph digraphWithEulerianCircuit;


			




	
	97
	
		
    check(eulerian(d), "This graph is Eulerian");


			




	
	98
	
		
    check(eulerian(g), "This graph is Eulerian");


			




	
	99
	
		
  }


			




	87
	100
	
		
  {


			




	88
	
	
		
    Digraph& g = digraphWithEulerianCircuit;


			




	
	101
	
		
    Digraph d;


			




	
	102
	
		
    Graph g(d);


			




	
	103
	
		
    Digraph::Node n = d.addNode();


			




	89
	104
	
		

			




	90
	
	
		
    Digraph::Node n0 = g.addNode();


			




	91
	
	
		
    Digraph::Node n1 = g.addNode();


			




	92
	
	
		
    Digraph::Node n2 = g.addNode();


			




	
	105
	
		
    checkDiEulerIt(d);


			




	
	106
	
		
    checkDiEulerIt(g);


			




	
	107
	
		
    checkEulerIt(g);


			




	93
	108
	
		

			




	94
	
	
		
    g.addArc(n0, n1);


			




	95
	
	
		
    g.addArc(n1, n0);


			




	96
	
	
		
    g.addArc(n1, n2);


			




	97
	
	
		
    g.addArc(n2, n1);


			




	
	109
	
		
    check(eulerian(d), "This graph is Eulerian");


			




	
	110
	
		
    check(eulerian(g), "This graph is Eulerian");


			




	98
	111
	
		
  }


			




	
	112
	
		
  {


			




	
	113
	
		
    Digraph d;


			




	
	114
	
		
    Graph g(d);


			




	
	115
	
		
    Digraph::Node n = d.addNode();


			




	
	116
	
		
    d.addArc(n, n);


			




	99
	117
	
		

			




	100
	
	
		
  Digraph digraphWithoutEulerianCircuit;


			




	
	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
	
		
  }


			




	101
	125
	
		
  {


			




	102
	
	
		
    Digraph& g = digraphWithoutEulerianCircuit;


			




	
	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);


			




	103
	136
	
		

			




	104
	
	
		
    Digraph::Node n0 = g.addNode();


			




	105
	
	
		
    Digraph::Node n1 = g.addNode();


			




	106
	
	
		
    Digraph::Node n2 = g.addNode();


			




	
	137
	
		
    checkDiEulerIt(d);


			




	
	138
	
		
    checkDiEulerIt(d, n2);


			




	
	139
	
		
    checkDiEulerIt(g);


			




	
	140
	
		
    checkDiEulerIt(g, n2);


			




	
	141
	
		
    checkEulerIt(g);


			




	
	142
	
		
    checkEulerIt(g, n2);


			




	107
	143
	
		

			




	108
	
	
		
    g.addArc(n0, n1);


			




	109
	
	
		
    g.addArc(n1, n0);


			




	110
	
	
		
    g.addArc(n1, n2);


			




	
	144
	
		
    check(eulerian(d), "This graph is Eulerian");


			




	
	145
	
		
    check(eulerian(g), "This graph is Eulerian");


			




	111
	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);


			




	112
	168
	
		

			




	113
	
	
		
  Graph graphWithEulerianCircuit;


			




	
	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
	
		
  }


			




	114
	183
	
		
  {


			




	115
	
	
		
    Graph& g = graphWithEulerianCircuit;


			




	
	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);


			




	116
	196
	
		

			




	117
	
	
		
    Graph::Node n0 = g.addNode();


			




	118
	
	
		
    Graph::Node n1 = g.addNode();


			




	119
	
	
		
    Graph::Node n2 = g.addNode();


			




	
	197
	
		
    checkDiEulerIt(d);


			




	
	198
	
		
    checkDiEulerIt(d, n2);


			




	120
	199
	
		

			




	121
	
	
		
    g.addEdge(n0, n1);


			




	122
	
	
		
    g.addEdge(n1, n2);


			




	123
	
	
		
    g.addEdge(n2, n0);


			




	
	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");


			




	124
	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);


			




	125
	217
	
		

			




	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);


			




	
	218
	
		
    check(!eulerian(d), "This graph is not Eulerian");


			




	
	219
	
		
    check(!eulerian(g), "This graph is not Eulerian");


			




	136
	220
	
		
  }


			




	137
	221
	
		

			




	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
	222
	
		
  return 0;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)