273 } |
273 } |
274 return INVALID; |
274 return INVALID; |
275 } |
275 } |
276 }; |
276 }; |
277 |
277 |
278 |
|
279 /// \ingroup graphbits |
|
280 /// |
|
281 /// \brief BaseExtender for the BpUGraphs |
|
282 template <typename Base> |
|
283 class BpUGraphBaseExtender : public Base { |
|
284 public: |
|
285 typedef Base Parent; |
|
286 typedef BpUGraphBaseExtender Graph; |
|
287 |
|
288 typedef typename Parent::Node Node; |
|
289 typedef typename Parent::Edge UEdge; |
|
290 |
|
291 |
|
292 using Parent::first; |
|
293 using Parent::next; |
|
294 |
|
295 using Parent::id; |
|
296 |
|
297 class ANode : public Node { |
|
298 friend class BpUGraphBaseExtender; |
|
299 public: |
|
300 ANode() {} |
|
301 ANode(const Node& node) : Node(node) { |
|
302 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, |
|
303 typename Parent::NodeSetError()); |
|
304 } |
|
305 ANode(Invalid) : Node(INVALID) {} |
|
306 }; |
|
307 |
|
308 void first(ANode& node) const { |
|
309 Parent::firstANode(static_cast<Node&>(node)); |
|
310 } |
|
311 void next(ANode& node) const { |
|
312 Parent::nextANode(static_cast<Node&>(node)); |
|
313 } |
|
314 |
|
315 int id(const ANode& node) const { |
|
316 return Parent::aNodeId(node); |
|
317 } |
|
318 |
|
319 class BNode : public Node { |
|
320 friend class BpUGraphBaseExtender; |
|
321 public: |
|
322 BNode() {} |
|
323 BNode(const Node& node) : Node(node) { |
|
324 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, |
|
325 typename Parent::NodeSetError()); |
|
326 } |
|
327 BNode(Invalid) : Node(INVALID) {} |
|
328 }; |
|
329 |
|
330 void first(BNode& node) const { |
|
331 Parent::firstBNode(static_cast<Node&>(node)); |
|
332 } |
|
333 void next(BNode& node) const { |
|
334 Parent::nextBNode(static_cast<Node&>(node)); |
|
335 } |
|
336 |
|
337 int id(const BNode& node) const { |
|
338 return Parent::aNodeId(node); |
|
339 } |
|
340 |
|
341 Node source(const UEdge& edge) const { |
|
342 return aNode(edge); |
|
343 } |
|
344 Node target(const UEdge& edge) const { |
|
345 return bNode(edge); |
|
346 } |
|
347 |
|
348 void firstInc(UEdge& edge, bool& direction, const Node& node) const { |
|
349 if (Parent::aNode(node)) { |
|
350 Parent::firstOut(edge, node); |
|
351 direction = true; |
|
352 } else { |
|
353 Parent::firstIn(edge, node); |
|
354 direction = static_cast<UEdge&>(edge) == INVALID; |
|
355 } |
|
356 } |
|
357 void nextInc(UEdge& edge, bool& direction) const { |
|
358 if (direction) { |
|
359 Parent::nextOut(edge); |
|
360 } else { |
|
361 Parent::nextIn(edge); |
|
362 if (edge == INVALID) direction = true; |
|
363 } |
|
364 } |
|
365 |
|
366 int maxUEdgeId() const { |
|
367 return Parent::maxEdgeId(); |
|
368 } |
|
369 |
|
370 UEdge uEdgeFromId(int id) const { |
|
371 return Parent::edgeFromId(id); |
|
372 } |
|
373 |
|
374 class Edge : public UEdge { |
|
375 friend class BpUGraphBaseExtender; |
|
376 protected: |
|
377 bool forward; |
|
378 |
|
379 Edge(const UEdge& edge, bool _forward) |
|
380 : UEdge(edge), forward(_forward) {} |
|
381 |
|
382 public: |
|
383 Edge() {} |
|
384 Edge (Invalid) : UEdge(INVALID), forward(true) {} |
|
385 bool operator==(const Edge& i) const { |
|
386 return UEdge::operator==(i) && forward == i.forward; |
|
387 } |
|
388 bool operator!=(const Edge& i) const { |
|
389 return UEdge::operator!=(i) || forward != i.forward; |
|
390 } |
|
391 bool operator<(const Edge& i) const { |
|
392 return UEdge::operator<(i) || |
|
393 (!(i.forward<forward) && UEdge(*this)<UEdge(i)); |
|
394 } |
|
395 }; |
|
396 |
|
397 void first(Edge& edge) const { |
|
398 Parent::first(static_cast<UEdge&>(edge)); |
|
399 edge.forward = true; |
|
400 } |
|
401 |
|
402 void next(Edge& edge) const { |
|
403 if (!edge.forward) { |
|
404 Parent::next(static_cast<UEdge&>(edge)); |
|
405 } |
|
406 edge.forward = !edge.forward; |
|
407 } |
|
408 |
|
409 void firstOut(Edge& edge, const Node& node) const { |
|
410 if (Parent::aNode(node)) { |
|
411 Parent::firstOut(edge, node); |
|
412 edge.forward = true; |
|
413 } else { |
|
414 Parent::firstIn(edge, node); |
|
415 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
416 } |
|
417 } |
|
418 void nextOut(Edge& edge) const { |
|
419 if (edge.forward) { |
|
420 Parent::nextOut(edge); |
|
421 } else { |
|
422 Parent::nextIn(edge); |
|
423 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
424 } |
|
425 } |
|
426 |
|
427 void firstIn(Edge& edge, const Node& node) const { |
|
428 if (Parent::bNode(node)) { |
|
429 Parent::firstIn(edge, node); |
|
430 edge.forward = true; |
|
431 } else { |
|
432 Parent::firstOut(edge, node); |
|
433 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
434 } |
|
435 } |
|
436 void nextIn(Edge& edge) const { |
|
437 if (edge.forward) { |
|
438 Parent::nextIn(edge); |
|
439 } else { |
|
440 Parent::nextOut(edge); |
|
441 edge.forward = static_cast<UEdge&>(edge) == INVALID; |
|
442 } |
|
443 } |
|
444 |
|
445 Node source(const Edge& edge) const { |
|
446 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); |
|
447 } |
|
448 Node target(const Edge& edge) const { |
|
449 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); |
|
450 } |
|
451 |
|
452 int id(const Edge& edge) const { |
|
453 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); |
|
454 } |
|
455 Edge edgeFromId(int id) const { |
|
456 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0); |
|
457 } |
|
458 int maxEdgeId() const { |
|
459 return (Parent::maxId(UEdge()) << 1) + 1; |
|
460 } |
|
461 |
|
462 bool direction(const Edge& edge) const { |
|
463 return edge.forward; |
|
464 } |
|
465 |
|
466 Edge direct(const UEdge& edge, bool direction) const { |
|
467 return Edge(edge, direction); |
|
468 } |
|
469 |
|
470 int edgeNum() const { |
|
471 return 2 * Parent::edgeNum(); |
|
472 } |
|
473 |
|
474 int uEdgeNum() const { |
|
475 return Parent::edgeNum(); |
|
476 } |
|
477 |
|
478 }; |
|
479 |
|
480 } |
278 } |
481 |
279 |
482 #endif |
280 #endif |