1.1 --- a/lemon/bits/base_extender.h Tue Oct 03 11:24:41 2006 +0000
1.2 +++ b/lemon/bits/base_extender.h Tue Oct 03 11:46:39 2006 +0000
1.3 @@ -279,6 +279,209 @@
1.4 }
1.5 };
1.6
1.7 + template <typename Base>
1.8 + class BidirBpUGraphExtender : public Base {
1.9 + public:
1.10 + typedef Base Parent;
1.11 + typedef BidirBpUGraphExtender Graph;
1.12 +
1.13 + typedef typename Parent::Node Node;
1.14 + typedef typename Parent::UEdge UEdge;
1.15 +
1.16 +
1.17 + using Parent::first;
1.18 + using Parent::next;
1.19 +
1.20 + using Parent::id;
1.21 +
1.22 + class ANode : public Node {
1.23 + friend class BidirBpUGraphExtender;
1.24 + public:
1.25 + ANode() {}
1.26 + ANode(const Node& node) : Node(node) {
1.27 + LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
1.28 + typename Parent::NodeSetError());
1.29 + }
1.30 + ANode& operator=(const Node& node) {
1.31 + LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
1.32 + typename Parent::NodeSetError());
1.33 + Node::operator=(node);
1.34 + return *this;
1.35 + }
1.36 + ANode(Invalid) : Node(INVALID) {}
1.37 + };
1.38 +
1.39 + void first(ANode& node) const {
1.40 + Parent::firstANode(static_cast<Node&>(node));
1.41 + }
1.42 + void next(ANode& node) const {
1.43 + Parent::nextANode(static_cast<Node&>(node));
1.44 + }
1.45 +
1.46 + int id(const ANode& node) const {
1.47 + return Parent::aNodeId(node);
1.48 + }
1.49 +
1.50 + class BNode : public Node {
1.51 + friend class BidirBpUGraphExtender;
1.52 + public:
1.53 + BNode() {}
1.54 + BNode(const Node& node) : Node(node) {
1.55 + LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
1.56 + typename Parent::NodeSetError());
1.57 + }
1.58 + BNode& operator=(const Node& node) {
1.59 + LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
1.60 + typename Parent::NodeSetError());
1.61 + Node::operator=(node);
1.62 + return *this;
1.63 + }
1.64 + BNode(Invalid) : Node(INVALID) {}
1.65 + };
1.66 +
1.67 + void first(BNode& node) const {
1.68 + Parent::firstBNode(static_cast<Node&>(node));
1.69 + }
1.70 + void next(BNode& node) const {
1.71 + Parent::nextBNode(static_cast<Node&>(node));
1.72 + }
1.73 +
1.74 + int id(const BNode& node) const {
1.75 + return Parent::aNodeId(node);
1.76 + }
1.77 +
1.78 + Node source(const UEdge& edge) const {
1.79 + return aNode(edge);
1.80 + }
1.81 + Node target(const UEdge& edge) const {
1.82 + return bNode(edge);
1.83 + }
1.84 +
1.85 + void firstInc(UEdge& edge, bool& direction, const Node& node) const {
1.86 + if (Parent::aNode(node)) {
1.87 + Parent::firstFromANode(edge, node);
1.88 + direction = true;
1.89 + } else {
1.90 + Parent::firstFromBNode(edge, node);
1.91 + direction = static_cast<UEdge&>(edge) == INVALID;
1.92 + }
1.93 + }
1.94 + void nextInc(UEdge& edge, bool& direction) const {
1.95 + if (direction) {
1.96 + Parent::nextFromANode(edge);
1.97 + } else {
1.98 + Parent::nextFromBNode(edge);
1.99 + if (edge == INVALID) direction = true;
1.100 + }
1.101 + }
1.102 +
1.103 + class Edge : public UEdge {
1.104 + friend class BidirBpUGraphExtender;
1.105 + protected:
1.106 + bool forward;
1.107 +
1.108 + Edge(const UEdge& edge, bool _forward)
1.109 + : UEdge(edge), forward(_forward) {}
1.110 +
1.111 + public:
1.112 + Edge() {}
1.113 + Edge (Invalid) : UEdge(INVALID), forward(true) {}
1.114 + bool operator==(const Edge& i) const {
1.115 + return UEdge::operator==(i) && forward == i.forward;
1.116 + }
1.117 + bool operator!=(const Edge& i) const {
1.118 + return UEdge::operator!=(i) || forward != i.forward;
1.119 + }
1.120 + bool operator<(const Edge& i) const {
1.121 + return UEdge::operator<(i) ||
1.122 + (!(i.forward<forward) && UEdge(*this)<UEdge(i));
1.123 + }
1.124 + };
1.125 +
1.126 + void first(Edge& edge) const {
1.127 + Parent::first(static_cast<UEdge&>(edge));
1.128 + edge.forward = true;
1.129 + }
1.130 +
1.131 + void next(Edge& edge) const {
1.132 + if (!edge.forward) {
1.133 + Parent::next(static_cast<UEdge&>(edge));
1.134 + }
1.135 + edge.forward = !edge.forward;
1.136 + }
1.137 +
1.138 + void firstOut(Edge& edge, const Node& node) const {
1.139 + if (Parent::aNode(node)) {
1.140 + Parent::firstFromANode(edge, node);
1.141 + edge.forward = true;
1.142 + } else {
1.143 + Parent::firstFromBNode(edge, node);
1.144 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.145 + }
1.146 + }
1.147 + void nextOut(Edge& edge) const {
1.148 + if (edge.forward) {
1.149 + Parent::nextFromANode(edge);
1.150 + } else {
1.151 + Parent::nextFromBNode(edge);
1.152 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.153 + }
1.154 + }
1.155 +
1.156 + void firstIn(Edge& edge, const Node& node) const {
1.157 + if (Parent::bNode(node)) {
1.158 + Parent::firstFromBNode(edge, node);
1.159 + edge.forward = true;
1.160 + } else {
1.161 + Parent::firstFromANode(edge, node);
1.162 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.163 + }
1.164 + }
1.165 + void nextIn(Edge& edge) const {
1.166 + if (edge.forward) {
1.167 + Parent::nextFromBNode(edge);
1.168 + } else {
1.169 + Parent::nextFromANode(edge);
1.170 + edge.forward = static_cast<UEdge&>(edge) == INVALID;
1.171 + }
1.172 + }
1.173 +
1.174 + Node source(const Edge& edge) const {
1.175 + return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
1.176 + }
1.177 + Node target(const Edge& edge) const {
1.178 + return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
1.179 + }
1.180 +
1.181 + int id(const Edge& edge) const {
1.182 + return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
1.183 + (edge.forward ? 0 : 1);
1.184 + }
1.185 + Edge edgeFromId(int id) const {
1.186 + return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
1.187 + }
1.188 + int maxEdgeId() const {
1.189 + return (Parent::maxUEdgeId() << 1) + 1;
1.190 + }
1.191 +
1.192 + bool direction(const Edge& edge) const {
1.193 + return edge.forward;
1.194 + }
1.195 +
1.196 + Edge direct(const UEdge& edge, bool direction) const {
1.197 + return Edge(edge, direction);
1.198 + }
1.199 +
1.200 + int edgeNum() const {
1.201 + return 2 * Parent::uEdgeNum();
1.202 + }
1.203 +
1.204 + int uEdgeNum() const {
1.205 + return Parent::uEdgeNum();
1.206 + }
1.207 +
1.208 +
1.209 + };
1.210 }
1.211
1.212 #endif