lemon/bits/graph_extender.h
changeset 2089 fce8db723736
parent 2046 66d160810c0a
child 2098 12f67fa3df7d
equal deleted inserted replaced
15:890bd0acf611 16:f75729f7800a
   732   public:
   732   public:
   733     typedef Base Parent;
   733     typedef Base Parent;
   734     typedef BpUGraphExtender Graph;
   734     typedef BpUGraphExtender Graph;
   735 
   735 
   736     typedef typename Parent::Node Node;
   736     typedef typename Parent::Node Node;
   737     typedef typename Parent::BNode BNode;
       
   738     typedef typename Parent::ANode ANode;
       
   739     typedef typename Parent::Edge Edge;
       
   740     typedef typename Parent::UEdge UEdge;
   737     typedef typename Parent::UEdge UEdge;
       
   738 
       
   739 
       
   740     using Parent::first;
       
   741     using Parent::next;
       
   742 
       
   743     using Parent::id;
       
   744 
       
   745     class ANode : public Node {
       
   746       friend class BpUGraphExtender;
       
   747     public:
       
   748       ANode() {}
       
   749       ANode(const Node& node) : Node(node) {
       
   750 	LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 
       
   751 		     typename Parent::NodeSetError());
       
   752       }
       
   753       ANode(Invalid) : Node(INVALID) {}
       
   754     };
       
   755 
       
   756     void first(ANode& node) const {
       
   757       Parent::firstANode(static_cast<Node&>(node));
       
   758     }
       
   759     void next(ANode& node) const {
       
   760       Parent::nextANode(static_cast<Node&>(node));
       
   761     }
       
   762 
       
   763     int id(const ANode& node) const {
       
   764       return Parent::aNodeId(node);
       
   765     }
       
   766 
       
   767     class BNode : public Node {
       
   768       friend class BpUGraphExtender;
       
   769     public:
       
   770       BNode() {}
       
   771       BNode(const Node& node) : Node(node) {
       
   772 	LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
       
   773 		     typename Parent::NodeSetError());
       
   774       }
       
   775       BNode(Invalid) : Node(INVALID) {}
       
   776     };
       
   777 
       
   778     void first(BNode& node) const {
       
   779       Parent::firstBNode(static_cast<Node&>(node));
       
   780     }
       
   781     void next(BNode& node) const {
       
   782       Parent::nextBNode(static_cast<Node&>(node));
       
   783     }
       
   784   
       
   785     int id(const BNode& node) const {
       
   786       return Parent::aNodeId(node);
       
   787     }
       
   788 
       
   789     Node source(const UEdge& edge) const {
       
   790       return aNode(edge);
       
   791     }
       
   792     Node target(const UEdge& edge) const {
       
   793       return bNode(edge);
       
   794     }
       
   795 
       
   796     void firstInc(UEdge& edge, bool& direction, const Node& node) const {
       
   797       if (Parent::aNode(node)) {
       
   798 	Parent::firstFromANode(edge, node);
       
   799 	direction = true;
       
   800       } else {
       
   801 	Parent::firstFromBNode(edge, node);
       
   802 	direction = static_cast<UEdge&>(edge) == INVALID;
       
   803       }
       
   804     }
       
   805     void nextInc(UEdge& edge, bool& direction) const {
       
   806       if (direction) {
       
   807 	Parent::nextFromANode(edge);
       
   808       } else {
       
   809 	Parent::nextFromBNode(edge);
       
   810 	if (edge == INVALID) direction = true;
       
   811       }
       
   812     }
       
   813 
       
   814     class Edge : public UEdge {
       
   815       friend class BpUGraphExtender;
       
   816     protected:
       
   817       bool forward;
       
   818 
       
   819       Edge(const UEdge& edge, bool _forward)
       
   820 	: UEdge(edge), forward(_forward) {}
       
   821 
       
   822     public:
       
   823       Edge() {}
       
   824       Edge (Invalid) : UEdge(INVALID), forward(true) {}
       
   825       bool operator==(const Edge& i) const {
       
   826 	return UEdge::operator==(i) && forward == i.forward;
       
   827       }
       
   828       bool operator!=(const Edge& i) const {
       
   829 	return UEdge::operator!=(i) || forward != i.forward;
       
   830       }
       
   831       bool operator<(const Edge& i) const {
       
   832 	return UEdge::operator<(i) || 
       
   833 	  (!(i.forward<forward) && UEdge(*this)<UEdge(i));
       
   834       }
       
   835     };
       
   836 
       
   837     void first(Edge& edge) const {
       
   838       Parent::first(static_cast<UEdge&>(edge));
       
   839       edge.forward = true;
       
   840     }
       
   841 
       
   842     void next(Edge& edge) const {
       
   843       if (!edge.forward) {
       
   844 	Parent::next(static_cast<UEdge&>(edge));
       
   845       }
       
   846       edge.forward = !edge.forward;
       
   847     }
       
   848 
       
   849     void firstOut(Edge& edge, const Node& node) const {
       
   850       if (Parent::aNode(node)) {
       
   851 	Parent::firstFromANode(edge, node);
       
   852 	edge.forward = true;
       
   853       } else {
       
   854 	Parent::firstFromBNode(edge, node);
       
   855 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
       
   856       }
       
   857     }
       
   858     void nextOut(Edge& edge) const {
       
   859       if (edge.forward) {
       
   860 	Parent::nextFromANode(edge);
       
   861       } else {
       
   862 	Parent::nextFromBNode(edge);
       
   863         edge.forward = static_cast<UEdge&>(edge) == INVALID;
       
   864       }
       
   865     }
       
   866 
       
   867     void firstIn(Edge& edge, const Node& node) const {
       
   868       if (Parent::bNode(node)) {
       
   869 	Parent::firstFromBNode(edge, node);
       
   870 	edge.forward = true;	
       
   871       } else {
       
   872 	Parent::firstFromANode(edge, node);
       
   873 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
       
   874       }
       
   875     }
       
   876     void nextIn(Edge& edge) const {
       
   877       if (edge.forward) {
       
   878 	Parent::nextFromBNode(edge);
       
   879       } else {
       
   880 	Parent::nextFromANode(edge);
       
   881 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
       
   882       }
       
   883     }
       
   884 
       
   885     Node source(const Edge& edge) const {
       
   886       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
       
   887     }
       
   888     Node target(const Edge& edge) const {
       
   889       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
       
   890     }
       
   891 
       
   892     int id(const Edge& edge) const {
       
   893       return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 
       
   894         (edge.forward ? 0 : 1);
       
   895     }
       
   896     Edge edgeFromId(int id) const {
       
   897       return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
       
   898     }
       
   899     int maxEdgeId() const {
       
   900       return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
       
   901     }
       
   902 
       
   903     bool direction(const Edge& edge) const {
       
   904       return edge.forward;
       
   905     }
       
   906 
       
   907     Edge direct(const UEdge& edge, bool direction) const {
       
   908       return Edge(edge, direction);
       
   909     }
       
   910 
       
   911     int edgeNum() const {
       
   912       return 2 * Parent::uEdgeNum();
       
   913     }
       
   914 
       
   915     int uEdgeNum() const {
       
   916       return Parent::uEdgeNum();
       
   917     }
   741 
   918 
   742     Node oppositeNode(const UEdge& edge, const Node& node) const {
   919     Node oppositeNode(const UEdge& edge, const Node& node) const {
   743       return source(edge) == node ? 
   920       return source(edge) == node ? 
   744 	target(edge) : source(edge);
   921 	target(edge) : source(edge);
   745     }
   922     }
   746 
   923 
   747     using Parent::direct;
       
   748     Edge direct(const UEdge& edge, const Node& node) const {
   924     Edge direct(const UEdge& edge, const Node& node) const {
   749       return Edge(edge, node == Parent::source(edge));
   925       return Edge(edge, node == Parent::source(edge));
   750     }
   926     }
   751 
   927 
   752     Edge oppositeEdge(const Edge& edge) const {
   928     Edge oppositeEdge(const Edge& edge) const {
   762     }
   938     }
   763     int maxId(ANode) const {
   939     int maxId(ANode) const {
   764       return Parent::maxANodeId();
   940       return Parent::maxANodeId();
   765     }
   941     }
   766     int maxId(Edge) const {
   942     int maxId(Edge) const {
   767       return Parent::maxEdgeId();
   943       return maxEdgeId();
   768     }
   944     }
   769     int maxId(UEdge) const {
   945     int maxId(UEdge) const {
   770       return Parent::maxUEdgeId();
   946       return Parent::maxUEdgeId();
   771     }
   947     }
   772 
   948