r638:493533ead9df
Wed, 15 Apr 2009 11:41:25
[Not Reviewed]
0 comments (0 inline)
0
1
0
28
16
| ... | ... |
@@ -57,55 +57,61 @@ |
| 57 | 57 |
template<typename GR> |
| 58 | 58 |
class DiEulerIt |
| 59 | 59 |
{
|
| 60 | 60 |
typedef typename GR::Node Node; |
| 61 | 61 |
typedef typename GR::NodeIt NodeIt; |
| 62 | 62 |
typedef typename GR::Arc Arc; |
| 63 | 63 |
typedef typename GR::ArcIt ArcIt; |
| 64 | 64 |
typedef typename GR::OutArcIt OutArcIt; |
| 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) {
|
| 104 | 110 |
euler.insert(next,nedge[s]); |
| 105 | 111 |
Node n=g.target(nedge[s]); |
| 106 | 112 |
++nedge[s]; |
| 107 | 113 |
s=n; |
| 108 | 114 |
} |
| 109 | 115 |
return *this; |
| 110 | 116 |
} |
| 111 | 117 |
///Postfix incrementation |
| ... | ... |
@@ -150,57 +156,63 @@ |
| 150 | 156 |
{
|
| 151 | 157 |
typedef typename GR::Node Node; |
| 152 | 158 |
typedef typename GR::NodeIt NodeIt; |
| 153 | 159 |
typedef typename GR::Arc Arc; |
| 154 | 160 |
typedef typename GR::Edge Edge; |
| 155 | 161 |
typedef typename GR::ArcIt ArcIt; |
| 156 | 162 |
typedef typename GR::OutArcIt OutArcIt; |
| 157 | 163 |
typedef typename GR::InArcIt InArcIt; |
| 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(); |
| 199 | 211 |
typename std::list<Arc>::iterator next=euler.begin(); |
| 200 | 212 |
|
| 201 | 213 |
while(nedge[s]!=INVALID) {
|
| 202 | 214 |
while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s]; |
| 203 | 215 |
if(nedge[s]==INVALID) break; |
| 204 | 216 |
else {
|
| 205 | 217 |
euler.insert(next,nedge[s]); |
| 206 | 218 |
visited[nedge[s]]=true; |
0 comments (0 inline)