433 bool operator==(const Edge i) const {return id==i.id;} |
433 bool operator==(const Edge i) const {return id==i.id;} |
434 bool operator!=(const Edge i) const {return id!=i.id;} |
434 bool operator!=(const Edge i) const {return id!=i.id;} |
435 bool operator<(const Edge i) const {return id<i.id;} |
435 bool operator<(const Edge i) const {return id<i.id;} |
436 }; |
436 }; |
437 |
437 |
438 void firstUpper(Node& node) const { |
438 void firstANode(Node& node) const { |
439 node.id = 2 * upperNodes.size() - 2; |
439 node.id = 2 * aNodes.size() - 2; |
440 if (node.id < 0) node.id = -1; |
440 if (node.id < 0) node.id = -1; |
441 } |
441 } |
442 void nextUpper(Node& node) const { |
442 void nextANode(Node& node) const { |
443 node.id -= 2; |
443 node.id -= 2; |
444 if (node.id < 0) node.id = -1; |
444 if (node.id < 0) node.id = -1; |
445 } |
445 } |
446 |
446 |
447 void firstLower(Node& node) const { |
447 void firstBNode(Node& node) const { |
448 node.id = 2 * lowerNodes.size() - 1; |
448 node.id = 2 * bNodes.size() - 1; |
449 } |
449 } |
450 void nextLower(Node& node) const { |
450 void nextBNode(Node& node) const { |
451 node.id -= 2; |
451 node.id -= 2; |
452 } |
452 } |
453 |
453 |
454 void first(Node& node) const { |
454 void first(Node& node) const { |
455 if (upperNodes.size() > 0) { |
455 if (aNodes.size() > 0) { |
456 node.id = 2 * upperNodes.size() - 2; |
456 node.id = 2 * aNodes.size() - 2; |
457 } else { |
457 } else { |
458 node.id = 2 * lowerNodes.size() - 1; |
458 node.id = 2 * bNodes.size() - 1; |
459 } |
459 } |
460 } |
460 } |
461 void next(Node& node) const { |
461 void next(Node& node) const { |
462 node.id -= 2; |
462 node.id -= 2; |
463 if (node.id == -2) { |
463 if (node.id == -2) { |
464 node.id = 2 * lowerNodes.size() - 1; |
464 node.id = 2 * bNodes.size() - 1; |
465 } |
465 } |
466 } |
466 } |
467 |
467 |
468 void first(Edge& edge) const { |
468 void first(Edge& edge) const { |
469 edge.id = edges.size() - 1; |
469 edge.id = edges.size() - 1; |
470 } |
470 } |
471 void next(Edge& edge) const { |
471 void next(Edge& edge) const { |
472 --edge.id; |
472 --edge.id; |
473 } |
473 } |
474 |
474 |
475 void firstDown(Edge& edge, const Node& node) const { |
475 void firstOut(Edge& edge, const Node& node) const { |
476 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
476 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
477 edge.id = upperNodes[node.id >> 1].first; |
477 edge.id = aNodes[node.id >> 1].first; |
478 } |
478 } |
479 void nextDown(Edge& edge) const { |
479 void nextOut(Edge& edge) const { |
480 edge.id = edges[edge.id].next_down; |
480 edge.id = edges[edge.id].next_out; |
481 } |
481 } |
482 |
482 |
483 void firstUp(Edge& edge, const Node& node) const { |
483 void firstIn(Edge& edge, const Node& node) const { |
484 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
484 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
485 edge.id = lowerNodes[node.id >> 1].first; |
485 edge.id = bNodes[node.id >> 1].first; |
486 } |
486 } |
487 void nextUp(Edge& edge) const { |
487 void nextIn(Edge& edge) const { |
488 edge.id = edges[edge.id].next_up; |
488 edge.id = edges[edge.id].next_in; |
489 } |
489 } |
490 |
490 |
491 static int id(const Node& node) { |
491 static int id(const Node& node) { |
492 return node.id; |
492 return node.id; |
493 } |
493 } |
494 static Node nodeFromId(int id) { |
494 static Node nodeFromId(int id) { |
495 return Node(id); |
495 return Node(id); |
496 } |
496 } |
497 int maxNodeId() const { |
497 int maxNodeId() const { |
498 return upperNodes.size() > lowerNodes.size() ? |
498 return aNodes.size() > bNodes.size() ? |
499 upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1; |
499 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; |
500 } |
500 } |
501 |
501 |
502 static int id(const Edge& edge) { |
502 static int id(const Edge& edge) { |
503 return edge.id; |
503 return edge.id; |
504 } |
504 } |
507 } |
507 } |
508 int maxEdgeId() const { |
508 int maxEdgeId() const { |
509 return edges.size(); |
509 return edges.size(); |
510 } |
510 } |
511 |
511 |
512 static int upperId(const Node& node) { |
512 static int aNodeId(const Node& node) { |
513 return node.id >> 1; |
513 return node.id >> 1; |
514 } |
514 } |
515 static Node fromUpperId(int id, Node) { |
515 static Node fromANodeId(int id, Node) { |
516 return Node(id << 1); |
516 return Node(id << 1); |
517 } |
517 } |
518 int maxUpperId() const { |
518 int maxANodeId() const { |
519 return upperNodes.size(); |
519 return aNodes.size(); |
520 } |
520 } |
521 |
521 |
522 static int lowerId(const Node& node) { |
522 static int bNodeId(const Node& node) { |
523 return node.id >> 1; |
523 return node.id >> 1; |
524 } |
524 } |
525 static Node fromLowerId(int id) { |
525 static Node fromBNodeId(int id) { |
526 return Node((id << 1) + 1); |
526 return Node((id << 1) + 1); |
527 } |
527 } |
528 int maxLowerId() const { |
528 int maxBNodeId() const { |
529 return lowerNodes.size(); |
529 return bNodes.size(); |
530 } |
530 } |
531 |
531 |
532 Node upperNode(const Edge& edge) const { |
532 Node aNode(const Edge& edge) const { |
533 return Node(edges[edge.id].upper); |
533 return Node(edges[edge.id].aNode); |
534 } |
534 } |
535 Node lowerNode(const Edge& edge) const { |
535 Node bNode(const Edge& edge) const { |
536 return Node(edges[edge.id].lower); |
536 return Node(edges[edge.id].bNode); |
537 } |
537 } |
538 |
538 |
539 static bool upper(const Node& node) { |
539 static bool aNode(const Node& node) { |
540 return (node.id & 1) == 0; |
540 return (node.id & 1) == 0; |
541 } |
541 } |
542 |
542 |
543 static bool lower(const Node& node) { |
543 static bool bNode(const Node& node) { |
544 return (node.id & 1) == 1; |
544 return (node.id & 1) == 1; |
545 } |
545 } |
546 |
546 |
547 Node addUpperNode() { |
547 Node addANode() { |
548 NodeT nodeT; |
548 NodeT nodeT; |
549 nodeT.first = -1; |
549 nodeT.first = -1; |
550 upperNodes.push_back(nodeT); |
550 aNodes.push_back(nodeT); |
551 return Node(upperNodes.size() * 2 - 2); |
551 return Node(aNodes.size() * 2 - 2); |
552 } |
552 } |
553 |
553 |
554 Node addLowerNode() { |
554 Node addBNode() { |
555 NodeT nodeT; |
555 NodeT nodeT; |
556 nodeT.first = -1; |
556 nodeT.first = -1; |
557 lowerNodes.push_back(nodeT); |
557 bNodes.push_back(nodeT); |
558 return Node(lowerNodes.size() * 2 - 1); |
558 return Node(bNodes.size() * 2 - 1); |
559 } |
559 } |
560 |
560 |
561 Edge addEdge(const Node& source, const Node& target) { |
561 Edge addEdge(const Node& source, const Node& target) { |
562 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
562 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
563 EdgeT edgeT; |
563 EdgeT edgeT; |
564 if ((source.id & 1) == 0) { |
564 if ((source.id & 1) == 0) { |
565 edgeT.upper = source.id; |
565 edgeT.aNode = source.id; |
566 edgeT.lower = target.id; |
566 edgeT.bNode = target.id; |
567 } else { |
567 } else { |
568 edgeT.upper = target.id; |
568 edgeT.aNode = target.id; |
569 edgeT.lower = source.id; |
569 edgeT.bNode = source.id; |
570 } |
570 } |
571 edgeT.next_down = upperNodes[edgeT.upper >> 1].first; |
571 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; |
572 upperNodes[edgeT.upper >> 1].first = edges.size(); |
572 aNodes[edgeT.aNode >> 1].first = edges.size(); |
573 edgeT.next_up = lowerNodes[edgeT.lower >> 1].first; |
573 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; |
574 lowerNodes[edgeT.lower >> 1].first = edges.size(); |
574 bNodes[edgeT.bNode >> 1].first = edges.size(); |
575 edges.push_back(edgeT); |
575 edges.push_back(edgeT); |
576 return Edge(edges.size() - 1); |
576 return Edge(edges.size() - 1); |
577 } |
577 } |
578 |
578 |
579 void clear() { |
579 void clear() { |
580 upperNodes.clear(); |
580 aNodes.clear(); |
581 lowerNodes.clear(); |
581 bNodes.clear(); |
582 edges.clear(); |
582 edges.clear(); |
583 } |
583 } |
584 |
584 |
585 }; |
585 }; |
586 |
586 |
587 |
587 |
588 typedef ClearableUBipartiteGraphExtender< |
588 typedef ClearableBpUGraphExtender< |
589 ExtendableUBipartiteGraphExtender< |
589 ExtendableBpUGraphExtender< |
590 MappableUBipartiteGraphExtender< |
590 MappableBpUGraphExtender< |
591 IterableUBipartiteGraphExtender< |
591 IterableBpUGraphExtender< |
592 AlterableUBipartiteGraphExtender< |
592 AlterableBpUGraphExtender< |
593 UBipartiteGraphExtender < |
593 BpUGraphExtender < |
594 SmartUBipartiteGraphBase> > > > > > |
594 SmartBpUGraphBase> > > > > > |
595 ExtendedSmartUBipartiteGraphBase; |
595 ExtendedSmartBpUGraphBase; |
596 |
596 |
597 |
597 /// \ingroup graphs |
598 class SmartUBipartiteGraph : |
598 /// |
599 public ExtendedSmartUBipartiteGraphBase { |
599 /// \brief A smart bipartite undirected graph class. |
600 }; |
600 /// |
|
601 /// This is a simple and fast bipartite undirected graph implementation. |
|
602 /// It is also quite memory efficient, but at the price |
|
603 /// that <b> it does not support node and edge deletions</b>. |
|
604 /// Except from this it conforms to |
|
605 /// the \ref concept::BpUGraph "BpUGraph" concept. |
|
606 /// \sa concept::BpUGraph. |
|
607 /// |
|
608 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; |
601 |
609 |
602 |
610 |
603 /// @} |
611 /// @} |
604 } //namespace lemon |
612 } //namespace lemon |
605 |
613 |