117 /// |
117 /// |
118 /// The ID of the \ref INVALID edge is -1. |
118 /// The ID of the \ref INVALID edge is -1. |
119 ///\return The ID of the edge \c e. |
119 ///\return The ID of the edge \c e. |
120 static int id(Edge e) { return e.n; } |
120 static int id(Edge e) { return e.n; } |
121 |
121 |
|
122 /// \brief Returns the node from its \c id. |
|
123 /// |
|
124 /// Returns the node from its \c id. If there is not node |
|
125 /// with the given id the effect of the function is undefinied. |
122 static Node nodeFromId(int id) { return Node(id);} |
126 static Node nodeFromId(int id) { return Node(id);} |
123 |
127 |
|
128 /// \brief Returns the edge from its \c id. |
|
129 /// |
|
130 /// Returns the edge from its \c id. If there is not edge |
|
131 /// with the given id the effect of the function is undefinied. |
124 static Edge edgeFromId(int id) { return Edge(id);} |
132 static Edge edgeFromId(int id) { return Edge(id);} |
125 |
133 |
126 Node addNode() { |
134 Node addNode() { |
127 Node n; n.n=nodes.size(); |
135 Node n; n.n=nodes.size(); |
128 nodes.push_back(NodeT()); //FIXME: Hmmm... |
136 nodes.push_back(NodeT()); //FIXME: Hmmm... |
412 bool operator==(const Node i) const {return id==i.id;} |
420 bool operator==(const Node i) const {return id==i.id;} |
413 bool operator!=(const Node i) const {return id!=i.id;} |
421 bool operator!=(const Node i) const {return id!=i.id;} |
414 bool operator<(const Node i) const {return id<i.id;} |
422 bool operator<(const Node i) const {return id<i.id;} |
415 }; |
423 }; |
416 |
424 |
417 class Edge { |
425 class UEdge { |
418 friend class SmartBpUGraphBase; |
426 friend class SmartBpUGraphBase; |
419 protected: |
427 protected: |
420 int id; |
428 int id; |
421 |
429 |
422 Edge(int _id) { id = _id;} |
430 UEdge(int _id) { id = _id;} |
423 public: |
431 public: |
424 Edge() {} |
432 UEdge() {} |
425 Edge (Invalid) { id = -1; } |
433 UEdge (Invalid) { id = -1; } |
426 bool operator==(const Edge i) const {return id==i.id;} |
434 bool operator==(const UEdge i) const {return id==i.id;} |
427 bool operator!=(const Edge i) const {return id!=i.id;} |
435 bool operator!=(const UEdge i) const {return id!=i.id;} |
428 bool operator<(const Edge i) const {return id<i.id;} |
436 bool operator<(const UEdge i) const {return id<i.id;} |
429 }; |
437 }; |
430 |
438 |
431 void firstANode(Node& node) const { |
439 void firstANode(Node& node) const { |
432 node.id = 2 * aNodes.size() - 2; |
440 node.id = 2 * aNodes.size() - 2; |
433 if (node.id < 0) node.id = -1; |
441 if (node.id < 0) node.id = -1; |
456 if (node.id == -2) { |
464 if (node.id == -2) { |
457 node.id = 2 * bNodes.size() - 1; |
465 node.id = 2 * bNodes.size() - 1; |
458 } |
466 } |
459 } |
467 } |
460 |
468 |
461 void first(Edge& edge) const { |
469 void first(UEdge& edge) const { |
462 edge.id = edges.size() - 1; |
470 edge.id = edges.size() - 1; |
463 } |
471 } |
464 void next(Edge& edge) const { |
472 void next(UEdge& edge) const { |
465 --edge.id; |
473 --edge.id; |
466 } |
474 } |
467 |
475 |
468 void firstOut(Edge& edge, const Node& node) const { |
476 void firstFromANode(UEdge& edge, const Node& node) const { |
469 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
477 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
470 edge.id = aNodes[node.id >> 1].first; |
478 edge.id = aNodes[node.id >> 1].first; |
471 } |
479 } |
472 void nextOut(Edge& edge) const { |
480 void nextFromANode(UEdge& edge) const { |
473 edge.id = edges[edge.id].next_out; |
481 edge.id = edges[edge.id].next_out; |
474 } |
482 } |
475 |
483 |
476 void firstIn(Edge& edge, const Node& node) const { |
484 void firstFromBNode(UEdge& edge, const Node& node) const { |
477 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
485 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
478 edge.id = bNodes[node.id >> 1].first; |
486 edge.id = bNodes[node.id >> 1].first; |
479 } |
487 } |
480 void nextIn(Edge& edge) const { |
488 void nextFromBNode(UEdge& edge) const { |
481 edge.id = edges[edge.id].next_in; |
489 edge.id = edges[edge.id].next_in; |
482 } |
490 } |
483 |
491 |
484 static int id(const Node& node) { |
492 static int id(const Node& node) { |
485 return node.id; |
493 return node.id; |
490 int maxNodeId() const { |
498 int maxNodeId() const { |
491 return aNodes.size() > bNodes.size() ? |
499 return aNodes.size() > bNodes.size() ? |
492 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; |
500 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; |
493 } |
501 } |
494 |
502 |
495 static int id(const Edge& edge) { |
503 static int id(const UEdge& edge) { |
496 return edge.id; |
504 return edge.id; |
497 } |
505 } |
498 static Edge edgeFromId(int id) { |
506 static UEdge uEdgeFromId(int id) { |
499 return Edge(id); |
507 return UEdge(id); |
500 } |
508 } |
501 int maxEdgeId() const { |
509 int maxUEdgeId() const { |
502 return edges.size(); |
510 return edges.size(); |
503 } |
511 } |
504 |
512 |
505 static int aNodeId(const Node& node) { |
513 static int aNodeId(const Node& node) { |
506 return node.id >> 1; |
514 return node.id >> 1; |
520 } |
528 } |
521 int maxBNodeId() const { |
529 int maxBNodeId() const { |
522 return bNodes.size(); |
530 return bNodes.size(); |
523 } |
531 } |
524 |
532 |
525 Node aNode(const Edge& edge) const { |
533 Node aNode(const UEdge& edge) const { |
526 return Node(edges[edge.id].aNode); |
534 return Node(edges[edge.id].aNode); |
527 } |
535 } |
528 Node bNode(const Edge& edge) const { |
536 Node bNode(const UEdge& edge) const { |
529 return Node(edges[edge.id].bNode); |
537 return Node(edges[edge.id].bNode); |
530 } |
538 } |
531 |
539 |
532 static bool aNode(const Node& node) { |
540 static bool aNode(const Node& node) { |
533 return (node.id & 1) == 0; |
541 return (node.id & 1) == 0; |
549 nodeT.first = -1; |
557 nodeT.first = -1; |
550 bNodes.push_back(nodeT); |
558 bNodes.push_back(nodeT); |
551 return Node(bNodes.size() * 2 - 1); |
559 return Node(bNodes.size() * 2 - 1); |
552 } |
560 } |
553 |
561 |
554 Edge addEdge(const Node& source, const Node& target) { |
562 UEdge addEdge(const Node& source, const Node& target) { |
555 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
563 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
556 EdgeT edgeT; |
564 UEdgeT edgeT; |
557 if ((source.id & 1) == 0) { |
565 if ((source.id & 1) == 0) { |
558 edgeT.aNode = source.id; |
566 edgeT.aNode = source.id; |
559 edgeT.bNode = target.id; |
567 edgeT.bNode = target.id; |
560 } else { |
568 } else { |
561 edgeT.aNode = target.id; |
569 edgeT.aNode = target.id; |
564 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; |
572 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; |
565 aNodes[edgeT.aNode >> 1].first = edges.size(); |
573 aNodes[edgeT.aNode >> 1].first = edges.size(); |
566 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; |
574 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; |
567 bNodes[edgeT.bNode >> 1].first = edges.size(); |
575 bNodes[edgeT.bNode >> 1].first = edges.size(); |
568 edges.push_back(edgeT); |
576 edges.push_back(edgeT); |
569 return Edge(edges.size() - 1); |
577 return UEdge(edges.size() - 1); |
570 } |
578 } |
571 |
579 |
572 void clear() { |
580 void clear() { |
573 aNodes.clear(); |
581 aNodes.clear(); |
574 bNodes.clear(); |
582 bNodes.clear(); |
579 int nodeNum() const { return aNodes.size() + bNodes.size(); } |
587 int nodeNum() const { return aNodes.size() + bNodes.size(); } |
580 int aNodeNum() const { return aNodes.size(); } |
588 int aNodeNum() const { return aNodes.size(); } |
581 int bNodeNum() const { return bNodes.size(); } |
589 int bNodeNum() const { return bNodes.size(); } |
582 |
590 |
583 typedef True EdgeNumTag; |
591 typedef True EdgeNumTag; |
584 int edgeNum() const { return edges.size(); } |
592 int uEdgeNum() const { return edges.size(); } |
585 |
593 |
586 }; |
594 }; |
587 |
595 |
588 |
596 |
589 typedef BpUGraphExtender< BpUGraphBaseExtender< |
597 typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase; |
590 SmartBpUGraphBase> > ExtendedSmartBpUGraphBase; |
|
591 |
598 |
592 /// \ingroup graphs |
599 /// \ingroup graphs |
593 /// |
600 /// |
594 /// \brief A smart bipartite undirected graph class. |
601 /// \brief A smart bipartite undirected graph class. |
595 /// |
602 /// |