... | ... |
@@ -65,39 +65,45 @@ |
65 | 65 |
typedef typename GR::InArcIt InArcIt; |
66 | 66 |
|
67 | 67 |
const GR &g; |
68 | 68 |
typename GR::template NodeMap<OutArcIt> nedge; |
69 | 69 |
std::list<Arc> euler; |
70 | 70 |
|
71 | 71 |
public: |
72 | 72 |
|
73 | 73 |
///Constructor |
74 | 74 |
|
75 | 75 |
///\param gr A digraph. |
76 | 76 |
///\param start The starting point of the tour. If it is not given |
77 | 77 |
/// the tour will start from the first node. |
78 | 78 |
DiEulerIt(const GR &gr, typename GR::Node start = INVALID) |
79 | 79 |
: g(gr), nedge(g) |
80 | 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 |
|
|
81 |
if (start==INVALID) { |
|
82 |
NodeIt n(g); |
|
83 |
while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
|
84 |
start=n; |
|
85 |
} |
|
86 |
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]; |
|
92 |
start=next; |
|
93 |
} |
|
88 | 94 |
} |
89 | 95 |
} |
90 | 96 |
|
91 | 97 |
///Arc Conversion |
92 | 98 |
operator Arc() { return euler.empty()?INVALID:euler.front(); } |
93 | 99 |
bool operator==(Invalid) { return euler.empty(); } |
94 | 100 |
bool operator!=(Invalid) { return !euler.empty(); } |
95 | 101 |
|
96 | 102 |
///Next arc of the tour |
97 | 103 |
DiEulerIt &operator++() { |
98 | 104 |
Node s=g.target(euler.front()); |
99 | 105 |
euler.pop_front(); |
100 | 106 |
//This produces a warning.Strange. |
101 | 107 |
//std::list<Arc>::iterator next=euler.begin(); |
102 | 108 |
typename std::list<Arc>::iterator next=euler.begin(); |
103 | 109 |
while(nedge[s]!=INVALID) { |
... | ... |
@@ -158,41 +164,47 @@ |
158 | 164 |
|
159 | 165 |
const GR &g; |
160 | 166 |
typename GR::template NodeMap<OutArcIt> nedge; |
161 | 167 |
typename GR::template EdgeMap<bool> visited; |
162 | 168 |
std::list<Arc> euler; |
163 | 169 |
|
164 | 170 |
public: |
165 | 171 |
|
166 | 172 |
///Constructor |
167 | 173 |
|
168 | 174 |
///\param gr An graph. |
169 | 175 |
///\param start The starting point of the tour. If it is not given |
170 | 176 |
/// the tour will start from the first node. |
171 | 177 |
EulerIt(const GR &gr, typename GR::Node start = INVALID) |
172 | 178 |
: g(gr), nedge(g), visited(g, false) |
173 | 179 |
{ |
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 |
|
|
180 |
if (start==INVALID) { |
|
181 |
NodeIt n(g); |
|
182 |
while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n; |
|
183 |
start=n; |
|
184 |
} |
|
185 |
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]; |
|
192 |
start=next; |
|
193 |
while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start]; |
|
194 |
} |
|
183 | 195 |
} |
184 | 196 |
} |
185 | 197 |
|
186 | 198 |
///Arc Conversion |
187 | 199 |
operator Arc() const { return euler.empty()?INVALID:euler.front(); } |
188 | 200 |
///Arc Conversion |
189 | 201 |
operator Edge() const { return euler.empty()?INVALID:euler.front(); } |
190 | 202 |
///\e |
191 | 203 |
bool operator==(Invalid) const { return euler.empty(); } |
192 | 204 |
///\e |
193 | 205 |
bool operator!=(Invalid) const { return !euler.empty(); } |
194 | 206 |
|
195 | 207 |
///Next arc of the tour |
196 | 208 |
EulerIt &operator++() { |
197 | 209 |
Node s=g.target(euler.front()); |
198 | 210 |
euler.pop_front(); |
0 comments (0 inline)