1.1 --- a/lemon/bits/base_extender.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/bits/base_extender.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -63,14 +63,14 @@
1.13 Arc(Invalid i) : Edge(i), forward(true) {}
1.14
1.15 bool operator==(const Arc &that) const {
1.16 - return forward==that.forward && Edge(*this)==Edge(that);
1.17 + return forward==that.forward && Edge(*this)==Edge(that);
1.18 }
1.19 bool operator!=(const Arc &that) const {
1.20 - return forward!=that.forward || Edge(*this)!=Edge(that);
1.21 + return forward!=that.forward || Edge(*this)!=Edge(that);
1.22 }
1.23 bool operator<(const Arc &that) const {
1.24 - return forward<that.forward ||
1.25 - (!(that.forward<forward) && Edge(*this)<Edge(that));
1.26 + return forward<that.forward ||
1.27 + (!(that.forward<forward) && Edge(*this)<Edge(that));
1.28 }
1.29 };
1.30
1.31 @@ -117,59 +117,59 @@
1.32
1.33 void next(Arc &e) const {
1.34 if( e.forward ) {
1.35 - e.forward = false;
1.36 + e.forward = false;
1.37 }
1.38 else {
1.39 - Parent::next(e);
1.40 - e.forward = true;
1.41 + Parent::next(e);
1.42 + e.forward = true;
1.43 }
1.44 }
1.45
1.46 void firstOut(Arc &e, const Node &n) const {
1.47 Parent::firstIn(e,n);
1.48 if( Edge(e) != INVALID ) {
1.49 - e.forward = false;
1.50 + e.forward = false;
1.51 }
1.52 else {
1.53 - Parent::firstOut(e,n);
1.54 - e.forward = true;
1.55 + Parent::firstOut(e,n);
1.56 + e.forward = true;
1.57 }
1.58 }
1.59 void nextOut(Arc &e) const {
1.60 if( ! e.forward ) {
1.61 - Node n = Parent::target(e);
1.62 - Parent::nextIn(e);
1.63 - if( Edge(e) == INVALID ) {
1.64 - Parent::firstOut(e, n);
1.65 - e.forward = true;
1.66 - }
1.67 + Node n = Parent::target(e);
1.68 + Parent::nextIn(e);
1.69 + if( Edge(e) == INVALID ) {
1.70 + Parent::firstOut(e, n);
1.71 + e.forward = true;
1.72 + }
1.73 }
1.74 else {
1.75 - Parent::nextOut(e);
1.76 + Parent::nextOut(e);
1.77 }
1.78 }
1.79
1.80 void firstIn(Arc &e, const Node &n) const {
1.81 Parent::firstOut(e,n);
1.82 if( Edge(e) != INVALID ) {
1.83 - e.forward = false;
1.84 + e.forward = false;
1.85 }
1.86 else {
1.87 - Parent::firstIn(e,n);
1.88 - e.forward = true;
1.89 + Parent::firstIn(e,n);
1.90 + e.forward = true;
1.91 }
1.92 }
1.93 void nextIn(Arc &e) const {
1.94 if( ! e.forward ) {
1.95 - Node n = Parent::source(e);
1.96 - Parent::nextOut(e);
1.97 - if( Edge(e) == INVALID ) {
1.98 - Parent::firstIn(e, n);
1.99 - e.forward = true;
1.100 - }
1.101 + Node n = Parent::source(e);
1.102 + Parent::nextOut(e);
1.103 + if( Edge(e) == INVALID ) {
1.104 + Parent::firstIn(e, n);
1.105 + e.forward = true;
1.106 + }
1.107 }
1.108 else {
1.109 - Parent::nextIn(e);
1.110 + Parent::nextIn(e);
1.111 }
1.112 }
1.113
1.114 @@ -183,13 +183,13 @@
1.115
1.116 void nextInc(Edge &e, bool &d) const {
1.117 if (d) {
1.118 - Node s = Parent::source(e);
1.119 - Parent::nextOut(e);
1.120 - if (e != INVALID) return;
1.121 - d = false;
1.122 - Parent::firstIn(e, s);
1.123 + Node s = Parent::source(e);
1.124 + Parent::nextOut(e);
1.125 + if (e != INVALID) return;
1.126 + d = false;
1.127 + Parent::firstIn(e, s);
1.128 } else {
1.129 - Parent::nextIn(e);
1.130 + Parent::nextIn(e);
1.131 }
1.132 }
1.133
1.134 @@ -240,18 +240,18 @@
1.135
1.136 Arc findArc(Node s, Node t, Arc p = INVALID) const {
1.137 if (p == INVALID) {
1.138 - Edge arc = Parent::findArc(s, t);
1.139 - if (arc != INVALID) return direct(arc, true);
1.140 - arc = Parent::findArc(t, s);
1.141 - if (arc != INVALID) return direct(arc, false);
1.142 + Edge arc = Parent::findArc(s, t);
1.143 + if (arc != INVALID) return direct(arc, true);
1.144 + arc = Parent::findArc(t, s);
1.145 + if (arc != INVALID) return direct(arc, false);
1.146 } else if (direction(p)) {
1.147 - Edge arc = Parent::findArc(s, t, p);
1.148 - if (arc != INVALID) return direct(arc, true);
1.149 - arc = Parent::findArc(t, s);
1.150 - if (arc != INVALID) return direct(arc, false);
1.151 + Edge arc = Parent::findArc(s, t, p);
1.152 + if (arc != INVALID) return direct(arc, true);
1.153 + arc = Parent::findArc(t, s);
1.154 + if (arc != INVALID) return direct(arc, false);
1.155 } else {
1.156 - Edge arc = Parent::findArc(t, s, p);
1.157 - if (arc != INVALID) return direct(arc, false);
1.158 + Edge arc = Parent::findArc(t, s, p);
1.159 + if (arc != INVALID) return direct(arc, false);
1.160 }
1.161 return INVALID;
1.162 }
1.163 @@ -267,10 +267,10 @@
1.164 Edge arc = Parent::findArc(s, t, p);
1.165 if (arc != INVALID) return arc;
1.166 arc = Parent::findArc(t, s);
1.167 - if (arc != INVALID) return arc;
1.168 + if (arc != INVALID) return arc;
1.169 } else {
1.170 Edge arc = Parent::findArc(t, s, p);
1.171 - if (arc != INVALID) return arc;
1.172 + if (arc != INVALID) return arc;
1.173 }
1.174 } else {
1.175 return Parent::findArc(s, t, p);
1.176 @@ -299,12 +299,12 @@
1.177 public:
1.178 Red() {}
1.179 Red(const Node& node) : Node(node) {
1.180 - LEMON_ASSERT(Parent::red(node) || node == INVALID,
1.181 - typename Parent::NodeSetError());
1.182 + LEMON_ASSERT(Parent::red(node) || node == INVALID,
1.183 + typename Parent::NodeSetError());
1.184 }
1.185 Red& operator=(const Node& node) {
1.186 - LEMON_ASSERT(Parent::red(node) || node == INVALID,
1.187 - typename Parent::NodeSetError());
1.188 + LEMON_ASSERT(Parent::red(node) || node == INVALID,
1.189 + typename Parent::NodeSetError());
1.190 Node::operator=(node);
1.191 return *this;
1.192 }
1.193 @@ -331,12 +331,12 @@
1.194 public:
1.195 Blue() {}
1.196 Blue(const Node& node) : Node(node) {
1.197 - LEMON_ASSERT(Parent::blue(node) || node == INVALID,
1.198 - typename Parent::NodeSetError());
1.199 + LEMON_ASSERT(Parent::blue(node) || node == INVALID,
1.200 + typename Parent::NodeSetError());
1.201 }
1.202 Blue& operator=(const Node& node) {
1.203 - LEMON_ASSERT(Parent::blue(node) || node == INVALID,
1.204 - typename Parent::NodeSetError());
1.205 + LEMON_ASSERT(Parent::blue(node) || node == INVALID,
1.206 + typename Parent::NodeSetError());
1.207 Node::operator=(node);
1.208 return *this;
1.209 }
1.210 @@ -353,7 +353,7 @@
1.211 void next(Blue& node) const {
1.212 Parent::nextBlue(static_cast<Node&>(node));
1.213 }
1.214 -
1.215 +
1.216 int id(const Blue& node) const {
1.217 return Parent::redId(node);
1.218 }
1.219 @@ -367,19 +367,19 @@
1.220
1.221 void firstInc(Edge& arc, bool& dir, const Node& node) const {
1.222 if (Parent::red(node)) {
1.223 - Parent::firstFromRed(arc, node);
1.224 - dir = true;
1.225 + Parent::firstFromRed(arc, node);
1.226 + dir = true;
1.227 } else {
1.228 - Parent::firstFromBlue(arc, node);
1.229 - dir = static_cast<Edge&>(arc) == INVALID;
1.230 + Parent::firstFromBlue(arc, node);
1.231 + dir = static_cast<Edge&>(arc) == INVALID;
1.232 }
1.233 }
1.234 void nextInc(Edge& arc, bool& dir) const {
1.235 if (dir) {
1.236 - Parent::nextFromRed(arc);
1.237 + Parent::nextFromRed(arc);
1.238 } else {
1.239 - Parent::nextFromBlue(arc);
1.240 - if (arc == INVALID) dir = true;
1.241 + Parent::nextFromBlue(arc);
1.242 + if (arc == INVALID) dir = true;
1.243 }
1.244 }
1.245
1.246 @@ -389,20 +389,20 @@
1.247 bool forward;
1.248
1.249 Arc(const Edge& arc, bool _forward)
1.250 - : Edge(arc), forward(_forward) {}
1.251 + : Edge(arc), forward(_forward) {}
1.252
1.253 public:
1.254 Arc() {}
1.255 Arc (Invalid) : Edge(INVALID), forward(true) {}
1.256 bool operator==(const Arc& i) const {
1.257 - return Edge::operator==(i) && forward == i.forward;
1.258 + return Edge::operator==(i) && forward == i.forward;
1.259 }
1.260 bool operator!=(const Arc& i) const {
1.261 - return Edge::operator!=(i) || forward != i.forward;
1.262 + return Edge::operator!=(i) || forward != i.forward;
1.263 }
1.264 bool operator<(const Arc& i) const {
1.265 - return Edge::operator<(i) ||
1.266 - (!(i.forward<forward) && Edge(*this)<Edge(i));
1.267 + return Edge::operator<(i) ||
1.268 + (!(i.forward<forward) && Edge(*this)<Edge(i));
1.269 }
1.270 };
1.271
1.272 @@ -413,44 +413,44 @@
1.273
1.274 void next(Arc& arc) const {
1.275 if (!arc.forward) {
1.276 - Parent::next(static_cast<Edge&>(arc));
1.277 + Parent::next(static_cast<Edge&>(arc));
1.278 }
1.279 arc.forward = !arc.forward;
1.280 }
1.281
1.282 void firstOut(Arc& arc, const Node& node) const {
1.283 if (Parent::red(node)) {
1.284 - Parent::firstFromRed(arc, node);
1.285 - arc.forward = true;
1.286 + Parent::firstFromRed(arc, node);
1.287 + arc.forward = true;
1.288 } else {
1.289 - Parent::firstFromBlue(arc, node);
1.290 - arc.forward = static_cast<Edge&>(arc) == INVALID;
1.291 + Parent::firstFromBlue(arc, node);
1.292 + arc.forward = static_cast<Edge&>(arc) == INVALID;
1.293 }
1.294 }
1.295 void nextOut(Arc& arc) const {
1.296 if (arc.forward) {
1.297 - Parent::nextFromRed(arc);
1.298 + Parent::nextFromRed(arc);
1.299 } else {
1.300 - Parent::nextFromBlue(arc);
1.301 + Parent::nextFromBlue(arc);
1.302 arc.forward = static_cast<Edge&>(arc) == INVALID;
1.303 }
1.304 }
1.305
1.306 void firstIn(Arc& arc, const Node& node) const {
1.307 if (Parent::blue(node)) {
1.308 - Parent::firstFromBlue(arc, node);
1.309 - arc.forward = true;
1.310 + Parent::firstFromBlue(arc, node);
1.311 + arc.forward = true;
1.312 } else {
1.313 - Parent::firstFromRed(arc, node);
1.314 - arc.forward = static_cast<Edge&>(arc) == INVALID;
1.315 + Parent::firstFromRed(arc, node);
1.316 + arc.forward = static_cast<Edge&>(arc) == INVALID;
1.317 }
1.318 }
1.319 void nextIn(Arc& arc) const {
1.320 if (arc.forward) {
1.321 - Parent::nextFromBlue(arc);
1.322 + Parent::nextFromBlue(arc);
1.323 } else {
1.324 - Parent::nextFromRed(arc);
1.325 - arc.forward = static_cast<Edge&>(arc) == INVALID;
1.326 + Parent::nextFromRed(arc);
1.327 + arc.forward = static_cast<Edge&>(arc) == INVALID;
1.328 }
1.329 }
1.330
1.331 @@ -462,7 +462,7 @@
1.332 }
1.333
1.334 int id(const Arc& arc) const {
1.335 - return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
1.336 + return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
1.337 (arc.forward ? 0 : 1);
1.338 }
1.339 Arc arcFromId(int ix) const {