Changes in / [641:d657c71db7db:642:16d7255a6849] in lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/euler.h
r633 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), nedge(g) 80 { 81 if(start==INVALID) start=NodeIt(g); 82 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); 83 while(nedge[start]!=INVALID) { 84 euler.push_back(nedge[start]); 85 Node next=g.target(nedge[start]); 86 ++nedge[start]; 87 start=next; 88 } 89 } 90 91 ///Arc Conversion 78 : g(gr), narc(g) 79 { 80 if (start==INVALID) { 81 NodeIt n(g); 82 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; 83 start=n; 84 } 85 if (start!=INVALID) { 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]; 91 start=next; 92 } 93 } 94 } 95 96 ///Arc conversion 92 97 operator Arc() { return euler.empty()?INVALID:euler.front(); } 98 ///Compare with \c INVALID 93 99 bool operator==(Invalid) { return euler.empty(); } 100 ///Compare with \c INVALID 94 101 bool operator!=(Invalid) { return !euler.empty(); } 95 102 96 103 ///Next arc of the tour 104 105 ///Next arc of the tour 106 /// 97 107 DiEulerIt &operator++() { 98 108 Node s=g.target(euler.front()); 99 109 euler.pop_front(); 100 //This produces a warning.Strange.101 //std::list<Arc>::iterator next=euler.begin();102 110 typename std::list<Arc>::iterator next=euler.begin(); 103 while(n edge[s]!=INVALID) {104 euler.insert(next,n edge[s]);105 Node n=g.target(n edge[s]);106 ++n edge[s];111 while(narc[s]!=INVALID) { 112 euler.insert(next,narc[s]); 113 Node n=g.target(narc[s]); 114 ++narc[s]; 107 115 s=n; 108 116 } … … 111 119 ///Postfix incrementation 112 120 121 /// Postfix incrementation. 122 /// 113 123 ///\warning This incrementation 114 ///returns an \c Arc, not a n\ref DiEulerIt, as one may124 ///returns an \c Arc, not a \ref DiEulerIt, as one may 115 125 ///expect. 116 126 Arc operator++(int) … … 122 132 }; 123 133 124 ///Euler iterator for graphs.134 ///Euler tour iterator for graphs. 125 135 126 136 /// \ingroup graph_properties 127 ///This iterator converts to the \c Arc (or \c Edge) 128 ///type of the digraph and using 129 ///operator ++, it provides an Euler tour of an undirected 130 ///digraph (if there exists). 131 /// 132 ///For example 133 ///if the given digraph if Euler (i.e it has only one nontrivial component 134 ///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), 135 143 ///the following code will print the arc IDs according to an 136 144 ///Euler tour of \c g. 137 145 ///\code 138 /// for(EulerIt<ListGraph> e(g) ,e!=INVALID;++e) {146 /// for(EulerIt<ListGraph> e(g); e!=INVALID; ++e) { 139 147 /// std::cout << g.id(Edge(e)) << std::eol; 140 148 /// } 141 149 ///\endcode 142 ///Although th e iterator provides an Euler tour of an graph,143 /// it still returns Arcs in order to indicate the direction of the tour.144 ///(But Arc will convert to Edges, of course).145 /// 146 ///If \c g is not Euler then the resulted tour will not be full or closed.147 /// \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. 148 156 template<typename GR> 149 157 class EulerIt … … 158 166 159 167 const GR &g; 160 typename GR::template NodeMap<OutArcIt> n edge;168 typename GR::template NodeMap<OutArcIt> narc; 161 169 typename GR::template EdgeMap<bool> visited; 162 170 std::list<Arc> euler; … … 166 174 ///Constructor 167 175 168 ///\param gr An graph. 169 ///\param start The starting point of the tour. If it is not given 170 /// 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. 171 180 EulerIt(const GR &gr, typename GR::Node start = INVALID) 172 : g(gr), nedge(g), visited(g, false) 173 { 174 if(start==INVALID) start=NodeIt(g); 175 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n); 176 while(nedge[start]!=INVALID) { 177 euler.push_back(nedge[start]); 178 visited[nedge[start]]=true; 179 Node next=g.target(nedge[start]); 180 ++nedge[start]; 181 start=next; 182 while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; 183 } 184 } 185 186 ///Arc Conversion 181 : g(gr), narc(g), visited(g, false) 182 { 183 if (start==INVALID) { 184 NodeIt n(g); 185 while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; 186 start=n; 187 } 188 if (start!=INVALID) { 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]; 195 start=next; 196 while(narc[start]!=INVALID && visited[narc[start]]) ++narc[start]; 197 } 198 } 199 } 200 201 ///Arc conversion 187 202 operator Arc() const { return euler.empty()?INVALID:euler.front(); } 188 /// Arc Conversion203 ///Edge conversion 189 204 operator Edge() const { return euler.empty()?INVALID:euler.front(); } 190 /// \e205 ///Compare with \c INVALID 191 206 bool operator==(Invalid) const { return euler.empty(); } 192 /// \e207 ///Compare with \c INVALID 193 208 bool operator!=(Invalid) const { return !euler.empty(); } 194 209 195 210 ///Next arc of the tour 211 212 ///Next arc of the tour 213 /// 196 214 EulerIt &operator++() { 197 215 Node s=g.target(euler.front()); 198 216 euler.pop_front(); 199 217 typename std::list<Arc>::iterator next=euler.begin(); 200 201 while(nedge[s]!=INVALID) { 202 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; 203 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; 204 221 else { 205 euler.insert(next,n edge[s]);206 visited[n edge[s]]=true;207 Node n=g.target(n edge[s]);208 ++n edge[s];222 euler.insert(next,narc[s]); 223 visited[narc[s]]=true; 224 Node n=g.target(narc[s]); 225 ++narc[s]; 209 226 s=n; 210 227 } … … 215 232 ///Postfix incrementation 216 233 217 ///\warning This incrementation 218 ///returns an \c Arc, not an \ref EulerIt, as one may 219 ///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. 220 238 Arc operator++(int) 221 239 { … … 227 245 228 246 229 ///Check s if the graph isEulerian247 ///Check if the given graph is \e Eulerian 230 248 231 249 /// \ingroup graph_properties 232 ///Checks if the graph is Eulerian. It works for both directed and undirected 233 ///graphs. 234 ///\note By definition, a digraph is called \e Eulerian if 235 ///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 236 255 ///arcs are the same for each node. 237 256 ///Similarly, an undirected graph is called \e Eulerian if 238 ///and only if it is connected and the number of incident arcs is even 239 ///for each node. <em>Therefore, there are digraphs which are not Eulerian, 240 ///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 241 264 template<typename GR> 242 265 #ifdef DOXYGEN … … 257 280 for(typename GR::NodeIt n(g);n!=INVALID;++n) 258 281 if(countInArcs(g,n)!=countOutArcs(g,n)) return false; 259 return connected( Undirector<const GR>(g));282 return connected(undirector(g)); 260 283 } 261 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.