r289:d91884dcd572
Mon, 29 Sep 2008 12:34:08
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -205,230 +205,230 @@ |
| 205 | 205 |
return Parent::arcFromId(ix); |
| 206 | 206 |
} |
| 207 | 207 |
|
| 208 | 208 |
int id(const Node &n) const {
|
| 209 | 209 |
return Parent::id(n); |
| 210 | 210 |
} |
| 211 | 211 |
|
| 212 | 212 |
int id(const Edge &e) const {
|
| 213 | 213 |
return Parent::id(e); |
| 214 | 214 |
} |
| 215 | 215 |
|
| 216 | 216 |
int id(const Arc &e) const {
|
| 217 | 217 |
return 2 * Parent::id(e) + int(e.forward); |
| 218 | 218 |
} |
| 219 | 219 |
|
| 220 | 220 |
int maxNodeId() const {
|
| 221 | 221 |
return Parent::maxNodeId(); |
| 222 | 222 |
} |
| 223 | 223 |
|
| 224 | 224 |
int maxArcId() const {
|
| 225 | 225 |
return 2 * Parent::maxArcId() + 1; |
| 226 | 226 |
} |
| 227 | 227 |
|
| 228 | 228 |
int maxEdgeId() const {
|
| 229 | 229 |
return Parent::maxArcId(); |
| 230 | 230 |
} |
| 231 | 231 |
|
| 232 | 232 |
int arcNum() const {
|
| 233 | 233 |
return 2 * Parent::arcNum(); |
| 234 | 234 |
} |
| 235 | 235 |
|
| 236 | 236 |
int edgeNum() const {
|
| 237 | 237 |
return Parent::arcNum(); |
| 238 | 238 |
} |
| 239 | 239 |
|
| 240 | 240 |
Arc findArc(Node s, Node t, Arc p = INVALID) const {
|
| 241 | 241 |
if (p == INVALID) {
|
| 242 | 242 |
Edge arc = Parent::findArc(s, t); |
| 243 | 243 |
if (arc != INVALID) return direct(arc, true); |
| 244 | 244 |
arc = Parent::findArc(t, s); |
| 245 | 245 |
if (arc != INVALID) return direct(arc, false); |
| 246 | 246 |
} else if (direction(p)) {
|
| 247 | 247 |
Edge arc = Parent::findArc(s, t, p); |
| 248 | 248 |
if (arc != INVALID) return direct(arc, true); |
| 249 | 249 |
arc = Parent::findArc(t, s); |
| 250 | 250 |
if (arc != INVALID) return direct(arc, false); |
| 251 | 251 |
} else {
|
| 252 | 252 |
Edge arc = Parent::findArc(t, s, p); |
| 253 | 253 |
if (arc != INVALID) return direct(arc, false); |
| 254 | 254 |
} |
| 255 | 255 |
return INVALID; |
| 256 | 256 |
} |
| 257 | 257 |
|
| 258 | 258 |
Edge findEdge(Node s, Node t, Edge p = INVALID) const {
|
| 259 | 259 |
if (s != t) {
|
| 260 | 260 |
if (p == INVALID) {
|
| 261 | 261 |
Edge arc = Parent::findArc(s, t); |
| 262 | 262 |
if (arc != INVALID) return arc; |
| 263 | 263 |
arc = Parent::findArc(t, s); |
| 264 | 264 |
if (arc != INVALID) return arc; |
| 265 | 265 |
} else if (Parent::s(p) == s) {
|
| 266 | 266 |
Edge arc = Parent::findArc(s, t, p); |
| 267 | 267 |
if (arc != INVALID) return arc; |
| 268 | 268 |
arc = Parent::findArc(t, s); |
| 269 | 269 |
if (arc != INVALID) return arc; |
| 270 | 270 |
} else {
|
| 271 | 271 |
Edge arc = Parent::findArc(t, s, p); |
| 272 | 272 |
if (arc != INVALID) return arc; |
| 273 | 273 |
} |
| 274 | 274 |
} else {
|
| 275 | 275 |
return Parent::findArc(s, t, p); |
| 276 | 276 |
} |
| 277 | 277 |
return INVALID; |
| 278 | 278 |
} |
| 279 | 279 |
}; |
| 280 | 280 |
|
| 281 | 281 |
template <typename Base> |
| 282 | 282 |
class BidirBpGraphExtender : public Base {
|
| 283 | 283 |
public: |
| 284 | 284 |
typedef Base Parent; |
| 285 | 285 |
typedef BidirBpGraphExtender Digraph; |
| 286 | 286 |
|
| 287 | 287 |
typedef typename Parent::Node Node; |
| 288 | 288 |
typedef typename Parent::Edge Edge; |
| 289 | 289 |
|
| 290 | 290 |
|
| 291 | 291 |
using Parent::first; |
| 292 | 292 |
using Parent::next; |
| 293 | 293 |
|
| 294 | 294 |
using Parent::id; |
| 295 | 295 |
|
| 296 | 296 |
class Red : public Node {
|
| 297 | 297 |
friend class BidirBpGraphExtender; |
| 298 | 298 |
public: |
| 299 | 299 |
Red() {}
|
| 300 | 300 |
Red(const Node& node) : Node(node) {
|
| 301 |
LEMON_ASSERT(Parent::red(node) || node == INVALID, |
|
| 302 |
typename Parent::NodeSetError()); |
|
| 301 |
LEMON_DEBUG(Parent::red(node) || node == INVALID, |
|
| 302 |
typename Parent::NodeSetError()); |
|
| 303 | 303 |
} |
| 304 | 304 |
Red& operator=(const Node& node) {
|
| 305 |
LEMON_ASSERT(Parent::red(node) || node == INVALID, |
|
| 306 |
typename Parent::NodeSetError()); |
|
| 305 |
LEMON_DEBUG(Parent::red(node) || node == INVALID, |
|
| 306 |
typename Parent::NodeSetError()); |
|
| 307 | 307 |
Node::operator=(node); |
| 308 | 308 |
return *this; |
| 309 | 309 |
} |
| 310 | 310 |
Red(Invalid) : Node(INVALID) {}
|
| 311 | 311 |
Red& operator=(Invalid) {
|
| 312 | 312 |
Node::operator=(INVALID); |
| 313 | 313 |
return *this; |
| 314 | 314 |
} |
| 315 | 315 |
}; |
| 316 | 316 |
|
| 317 | 317 |
void first(Red& node) const {
|
| 318 | 318 |
Parent::firstRed(static_cast<Node&>(node)); |
| 319 | 319 |
} |
| 320 | 320 |
void next(Red& node) const {
|
| 321 | 321 |
Parent::nextRed(static_cast<Node&>(node)); |
| 322 | 322 |
} |
| 323 | 323 |
|
| 324 | 324 |
int id(const Red& node) const {
|
| 325 | 325 |
return Parent::redId(node); |
| 326 | 326 |
} |
| 327 | 327 |
|
| 328 | 328 |
class Blue : public Node {
|
| 329 | 329 |
friend class BidirBpGraphExtender; |
| 330 | 330 |
public: |
| 331 | 331 |
Blue() {}
|
| 332 | 332 |
Blue(const Node& node) : Node(node) {
|
| 333 |
LEMON_ASSERT(Parent::blue(node) || node == INVALID, |
|
| 334 |
typename Parent::NodeSetError()); |
|
| 333 |
LEMON_DEBUG(Parent::blue(node) || node == INVALID, |
|
| 334 |
typename Parent::NodeSetError()); |
|
| 335 | 335 |
} |
| 336 | 336 |
Blue& operator=(const Node& node) {
|
| 337 |
LEMON_ASSERT(Parent::blue(node) || node == INVALID, |
|
| 338 |
typename Parent::NodeSetError()); |
|
| 337 |
LEMON_DEBUG(Parent::blue(node) || node == INVALID, |
|
| 338 |
typename Parent::NodeSetError()); |
|
| 339 | 339 |
Node::operator=(node); |
| 340 | 340 |
return *this; |
| 341 | 341 |
} |
| 342 | 342 |
Blue(Invalid) : Node(INVALID) {}
|
| 343 | 343 |
Blue& operator=(Invalid) {
|
| 344 | 344 |
Node::operator=(INVALID); |
| 345 | 345 |
return *this; |
| 346 | 346 |
} |
| 347 | 347 |
}; |
| 348 | 348 |
|
| 349 | 349 |
void first(Blue& node) const {
|
| 350 | 350 |
Parent::firstBlue(static_cast<Node&>(node)); |
| 351 | 351 |
} |
| 352 | 352 |
void next(Blue& node) const {
|
| 353 | 353 |
Parent::nextBlue(static_cast<Node&>(node)); |
| 354 | 354 |
} |
| 355 | 355 |
|
| 356 | 356 |
int id(const Blue& node) const {
|
| 357 | 357 |
return Parent::redId(node); |
| 358 | 358 |
} |
| 359 | 359 |
|
| 360 | 360 |
Node source(const Edge& arc) const {
|
| 361 | 361 |
return red(arc); |
| 362 | 362 |
} |
| 363 | 363 |
Node target(const Edge& arc) const {
|
| 364 | 364 |
return blue(arc); |
| 365 | 365 |
} |
| 366 | 366 |
|
| 367 | 367 |
void firstInc(Edge& arc, bool& dir, const Node& node) const {
|
| 368 | 368 |
if (Parent::red(node)) {
|
| 369 | 369 |
Parent::firstFromRed(arc, node); |
| 370 | 370 |
dir = true; |
| 371 | 371 |
} else {
|
| 372 | 372 |
Parent::firstFromBlue(arc, node); |
| 373 | 373 |
dir = static_cast<Edge&>(arc) == INVALID; |
| 374 | 374 |
} |
| 375 | 375 |
} |
| 376 | 376 |
void nextInc(Edge& arc, bool& dir) const {
|
| 377 | 377 |
if (dir) {
|
| 378 | 378 |
Parent::nextFromRed(arc); |
| 379 | 379 |
} else {
|
| 380 | 380 |
Parent::nextFromBlue(arc); |
| 381 | 381 |
if (arc == INVALID) dir = true; |
| 382 | 382 |
} |
| 383 | 383 |
} |
| 384 | 384 |
|
| 385 | 385 |
class Arc : public Edge {
|
| 386 | 386 |
friend class BidirBpGraphExtender; |
| 387 | 387 |
protected: |
| 388 | 388 |
bool forward; |
| 389 | 389 |
|
| 390 | 390 |
Arc(const Edge& arc, bool _forward) |
| 391 | 391 |
: Edge(arc), forward(_forward) {}
|
| 392 | 392 |
|
| 393 | 393 |
public: |
| 394 | 394 |
Arc() {}
|
| 395 | 395 |
Arc (Invalid) : Edge(INVALID), forward(true) {}
|
| 396 | 396 |
bool operator==(const Arc& i) const {
|
| 397 | 397 |
return Edge::operator==(i) && forward == i.forward; |
| 398 | 398 |
} |
| 399 | 399 |
bool operator!=(const Arc& i) const {
|
| 400 | 400 |
return Edge::operator!=(i) || forward != i.forward; |
| 401 | 401 |
} |
| 402 | 402 |
bool operator<(const Arc& i) const {
|
| 403 | 403 |
return Edge::operator<(i) || |
| 404 | 404 |
(!(i.forward<forward) && Edge(*this)<Edge(i)); |
| 405 | 405 |
} |
| 406 | 406 |
}; |
| 407 | 407 |
|
| 408 | 408 |
void first(Arc& arc) const {
|
| 409 | 409 |
Parent::first(static_cast<Edge&>(arc)); |
| 410 | 410 |
arc.forward = true; |
| 411 | 411 |
} |
| 412 | 412 |
|
| 413 | 413 |
void next(Arc& arc) const {
|
| 414 | 414 |
if (!arc.forward) {
|
| 415 | 415 |
Parent::next(static_cast<Edge&>(arc)); |
| 416 | 416 |
} |
| 417 | 417 |
arc.forward = !arc.forward; |
| 418 | 418 |
} |
| 419 | 419 |
|
| 420 | 420 |
void firstOut(Arc& arc, const Node& node) const {
|
| 421 | 421 |
if (Parent::red(node)) {
|
| 422 | 422 |
Parent::firstFromRed(arc, node); |
| 423 | 423 |
arc.forward = true; |
| 424 | 424 |
} else {
|
| 425 | 425 |
Parent::firstFromBlue(arc, node); |
| 426 | 426 |
arc.forward = static_cast<Edge&>(arc) == INVALID; |
| 427 | 427 |
} |
| 428 | 428 |
} |
| 429 | 429 |
void nextOut(Arc& arc) const {
|
| 430 | 430 |
if (arc.forward) {
|
| 431 | 431 |
Parent::nextFromRed(arc); |
| 432 | 432 |
} else {
|
| 433 | 433 |
Parent::nextFromBlue(arc); |
| 434 | 434 |
arc.forward = static_cast<Edge&>(arc) == INVALID; |
0 comments (0 inline)