Changeset 639:2ebfdb89ec66 in lemon
 Timestamp:
 04/15/09 11:47:19 (11 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/euler.h
r638 r639 27 27 /// \ingroup graph_properties 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 35 35 namespace lemon { 36 36 37 ///Euler iterator for digraphs. 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). 43 /// 44 ///For example 45 ///if the given digraph is Euler (i.e it has only one nontrivial component 46 ///and the indegree is equal to the outdegree 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. 37 ///Euler tour iterator for digraphs. 38 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. 42 /// 43 ///For example, if the given digraph has an Euler tour (i.e it has only one 44 ///nontrivial component and the indegree is equal to the outdegree 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 57 55 template<typename GR> … … 66 64 67 65 const GR &g; 68 typename GR::template NodeMap<OutArcIt> n edge;66 typename GR::template NodeMap<OutArcIt> narc; 69 67 std::list<Arc> euler; 70 68 … … 73 71 ///Constructor 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), n edge(g)78 : g(gr), narc(g) 80 79 { 81 80 if (start==INVALID) { … … 85 84 } 86 85 if (start!=INVALID) { 87 for (NodeIt n(g); n!=INVALID; ++n) n edge[n]=OutArcIt(g,n);88 while (n edge[start]!=INVALID) {89 euler.push_back(n edge[start]);90 Node next=g.target(n edge[start]);91 ++n edge[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; 93 92 } … … 95 94 } 96 95 97 ///Arc Conversion96 ///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(); } 101 102 102 103 ///Next arc of the tour 104 105 ///Next arc of the tour 106 /// 103 107 DiEulerIt &operator++() { 104 108 Node s=g.target(euler.front()); 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(n edge[s]!=INVALID) {110 euler.insert(next,n edge[s]);111 Node n=g.target(n edge[s]);112 ++n edge[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; 114 116 } … … 117 119 ///Postfix incrementation 118 120 121 /// Postfix incrementation. 122 /// 119 123 ///\warning This incrementation 120 ///returns an \c Arc, not a n\ref DiEulerIt, as one may124 ///returns an \c Arc, not a \ref DiEulerIt, as one may 121 125 ///expect. 122 126 Arc operator++(int) … … 128 132 }; 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 /// 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), 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. 140 /// 141 ///For example, if the given graph has an Euler tour (i.e it has only one 142 ///nontrivial component and the degree of each node is even), 141 143 ///the following code will print the arc IDs according to an 142 144 ///Euler tour of \c g. 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; 146 148 /// } 147 149 ///\endcode 148 ///Although th e 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).151 /// 152 ///If \c g is not Euler then the resulted tour will not be full or closed.153 /// \sa EulerIt150 ///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.) 153 /// 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> 155 157 class EulerIt … … 164 166 165 167 const GR &g; 166 typename GR::template NodeMap<OutArcIt> n edge;168 typename GR::template NodeMap<OutArcIt> narc; 167 169 typename GR::template EdgeMap<bool> visited; 168 170 std::list<Arc> euler; … … 172 174 ///Constructor 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), n edge(g), visited(g, false)181 : g(gr), narc(g), visited(g, false) 179 182 { 180 183 if (start==INVALID) { … … 184 187 } 185 188 if (start!=INVALID) { 186 for (NodeIt n(g); n!=INVALID; ++n) n edge[n]=OutArcIt(g,n);187 while(n edge[start]!=INVALID) {188 euler.push_back(n edge[start]);189 visited[n edge[start]]=true;190 Node next=g.target(n edge[start]);191 ++n edge[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(n edge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];196 while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; 194 197 } 195 198 } 196 199 } 197 200 198 ///Arc Conversion201 ///Arc conversion 199 202 operator Arc() const { return euler.empty()?INVALID:euler.front(); } 200 /// Arc Conversion203 ///Edge conversion 201 204 operator Edge() const { return euler.empty()?INVALID:euler.front(); } 202 /// \e205 ///Compare with \c INVALID 203 206 bool operator==(Invalid) const { return euler.empty(); } 204 /// \e207 ///Compare with \c INVALID 205 208 bool operator!=(Invalid) const { return !euler.empty(); } 206 209 207 210 ///Next arc of the tour 211 212 ///Next arc of the tour 213 /// 208 214 EulerIt &operator++() { 209 215 Node s=g.target(euler.front()); 210 216 euler.pop_front(); 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,n edge[s]);218 visited[n edge[s]]=true;219 Node n=g.target(n edge[s]);220 ++n edge[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; 222 227 } … … 227 232 ///Postfix incrementation 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) 233 239 { … … 239 245 240 246 241 ///Check s if the graph isEulerian247 ///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> 254 265 #ifdef DOXYGEN … … 269 280 for(typename GR::NodeIt n(g);n!=INVALID;++n) 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 } 273 284 
test/euler_test.cc
r578 r639 19 19 #include <lemon/euler.h> 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 23 24 using namespace lemon; 24 25 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 { 28 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 34 typename Digraph::Node firstNode = g.source(e); 32 35 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); 40 42 ++visitationNumber[e]; 41 43 } 42 44 43 45 check(firstNode == lastNode, 44 "checkDiEulerIt: first and last nodeare not the same");46 "checkDiEulerIt: First and last nodes are not the same"); 45 47 46 48 for (typename Digraph::ArcIt a(g); a != INVALID; ++a) 47 49 { 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 } 51 53 } 52 54 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 { 56 59 typename Graph::template EdgeMap<int> visitationNumber(g, 0); 57 60 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)); 68 71 ++visitationNumber[e]; 69 72 } 70 73 71 74 check(firstNode == lastNode, 72 "checkEulerIt: first and last nodeare not the same");75 "checkEulerIt: First and last nodes are not the same"); 73 76 74 77 for (typename Graph::EdgeIt e(g); e != INVALID; ++e) 75 78 { 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 } 79 82 } … … 82 85 { 83 86 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 } 151 221 152 222 return 0;
Note: See TracChangeset
for help on using the changeset viewer.