400 class UndirFullGraph : public ExtendedUndirFullGraphBase { |
400 class UndirFullGraph : public ExtendedUndirFullGraphBase { |
401 public: |
401 public: |
402 UndirFullGraph(int n) { construct(n); } |
402 UndirFullGraph(int n) { construct(n); } |
403 }; |
403 }; |
404 |
404 |
|
405 |
|
406 class FullUndirBipartiteGraphBase { |
|
407 protected: |
|
408 |
|
409 int _upperNodeNum; |
|
410 int _lowerNodeNum; |
|
411 |
|
412 int _edgeNum; |
|
413 |
|
414 public: |
|
415 |
|
416 class NodeSetError : public LogicError { |
|
417 virtual const char* exceptionName() const { |
|
418 return "lemon::FullUndirBipartiteGraph::NodeSetError"; |
|
419 } |
|
420 }; |
|
421 |
|
422 class Node { |
|
423 friend class FullUndirBipartiteGraphBase; |
|
424 protected: |
|
425 int id; |
|
426 |
|
427 Node(int _id) : id(_id) {} |
|
428 public: |
|
429 Node() {} |
|
430 Node(Invalid) { id = -1; } |
|
431 bool operator==(const Node i) const {return id==i.id;} |
|
432 bool operator!=(const Node i) const {return id!=i.id;} |
|
433 bool operator<(const Node i) const {return id<i.id;} |
|
434 }; |
|
435 |
|
436 class Edge { |
|
437 friend class FullUndirBipartiteGraphBase; |
|
438 protected: |
|
439 int id; |
|
440 |
|
441 Edge(int _id) { id = _id;} |
|
442 public: |
|
443 Edge() {} |
|
444 Edge (Invalid) { id = -1; } |
|
445 bool operator==(const Edge i) const {return id==i.id;} |
|
446 bool operator!=(const Edge i) const {return id!=i.id;} |
|
447 bool operator<(const Edge i) const {return id<i.id;} |
|
448 }; |
|
449 |
|
450 void construct(int upperNodeNum, int lowerNodeNum) { |
|
451 _upperNodeNum = upperNodeNum; |
|
452 _lowerNodeNum = lowerNodeNum; |
|
453 _edgeNum = upperNodeNum * lowerNodeNum; |
|
454 } |
|
455 |
|
456 void firstUpper(Node& node) const { |
|
457 node.id = 2 * _upperNodeNum - 2; |
|
458 if (node.id < 0) node.id = -1; |
|
459 } |
|
460 void nextUpper(Node& node) const { |
|
461 node.id -= 2; |
|
462 if (node.id < 0) node.id = -1; |
|
463 } |
|
464 |
|
465 void firstLower(Node& node) const { |
|
466 node.id = 2 * _lowerNodeNum - 1; |
|
467 } |
|
468 void nextLower(Node& node) const { |
|
469 node.id -= 2; |
|
470 } |
|
471 |
|
472 void first(Node& node) const { |
|
473 if (_upperNodeNum > 0) { |
|
474 node.id = 2 * _upperNodeNum - 2; |
|
475 } else { |
|
476 node.id = 2 * _lowerNodeNum - 1; |
|
477 } |
|
478 } |
|
479 void next(Node& node) const { |
|
480 node.id -= 2; |
|
481 if (node.id == -2) { |
|
482 node.id = 2 * _lowerNodeNum - 1; |
|
483 } |
|
484 } |
|
485 |
|
486 void first(Edge& edge) const { |
|
487 edge.id = _edgeNum - 1; |
|
488 } |
|
489 void next(Edge& edge) const { |
|
490 --edge.id; |
|
491 } |
|
492 |
|
493 void firstDown(Edge& edge, const Node& node) const { |
|
494 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
|
495 edge.id = (node.id >> 1) * _lowerNodeNum; |
|
496 } |
|
497 void nextDown(Edge& edge) const { |
|
498 ++(edge.id); |
|
499 if (edge.id % _lowerNodeNum == 0) edge.id = -1; |
|
500 } |
|
501 |
|
502 void firstUp(Edge& edge, const Node& node) const { |
|
503 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
|
504 edge.id = (node.id >> 1); |
|
505 } |
|
506 void nextUp(Edge& edge) const { |
|
507 edge.id += _lowerNodeNum; |
|
508 if (edge.id >= _edgeNum) edge.id = -1; |
|
509 } |
|
510 |
|
511 static int id(const Node& node) { |
|
512 return node.id; |
|
513 } |
|
514 static Node nodeFromId(int id) { |
|
515 return Node(id); |
|
516 } |
|
517 int maxNodeId() const { |
|
518 return _upperNodeNum > _lowerNodeNum ? |
|
519 _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1; |
|
520 } |
|
521 |
|
522 static int id(const Edge& edge) { |
|
523 return edge.id; |
|
524 } |
|
525 static Edge edgeFromId(int id) { |
|
526 return Edge(id); |
|
527 } |
|
528 int maxEdgeId() const { |
|
529 return _edgeNum - 1; |
|
530 } |
|
531 |
|
532 static int upperId(const Node& node) { |
|
533 return node.id >> 1; |
|
534 } |
|
535 static Node fromUpperId(int id, Node) { |
|
536 return Node(id << 1); |
|
537 } |
|
538 int maxUpperId() const { |
|
539 return _upperNodeNum; |
|
540 } |
|
541 |
|
542 static int lowerId(const Node& node) { |
|
543 return node.id >> 1; |
|
544 } |
|
545 static Node fromLowerId(int id) { |
|
546 return Node((id << 1) + 1); |
|
547 } |
|
548 int maxLowerId() const { |
|
549 return _lowerNodeNum; |
|
550 } |
|
551 |
|
552 Node upperNode(const Edge& edge) const { |
|
553 return Node((edge.id / _lowerNodeNum) << 1); |
|
554 } |
|
555 Node lowerNode(const Edge& edge) const { |
|
556 return Node(((edge.id % _lowerNodeNum) << 1) + 1); |
|
557 } |
|
558 |
|
559 static bool upper(const Node& node) { |
|
560 return (node.id & 1) == 0; |
|
561 } |
|
562 |
|
563 static bool lower(const Node& node) { |
|
564 return (node.id & 1) == 1; |
|
565 } |
|
566 |
|
567 static Node upperNode(int index) { |
|
568 return Node(index << 1); |
|
569 } |
|
570 |
|
571 static Node lowerNode(int index) { |
|
572 return Node((index << 1) + 1); |
|
573 } |
|
574 |
|
575 }; |
|
576 |
|
577 |
|
578 typedef MappableUndirBipartiteGraphExtender< |
|
579 IterableUndirBipartiteGraphExtender< |
|
580 AlterableUndirBipartiteGraphExtender< |
|
581 UndirBipartiteGraphExtender < |
|
582 FullUndirBipartiteGraphBase> > > > |
|
583 ExtendedFullUndirBipartiteGraphBase; |
|
584 |
|
585 |
|
586 class FullUndirBipartiteGraph : |
|
587 public ExtendedFullUndirBipartiteGraphBase { |
|
588 public: |
|
589 typedef ExtendedFullUndirBipartiteGraphBase Parent; |
|
590 FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) { |
|
591 Parent::construct(upperNodeNum, lowerNodeNum); |
|
592 } |
|
593 }; |
|
594 |
405 } //namespace lemon |
595 } //namespace lemon |
406 |
596 |
407 |
597 |
408 #endif //LEMON_FULL_GRAPH_H |
598 #endif //LEMON_FULL_GRAPH_H |