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
2.1 --- a/lemon/bits/graph_adaptor_extender.h Tue Oct 03 11:24:41 2006 +0000
2.2 +++ b/lemon/bits/graph_adaptor_extender.h Tue Oct 03 11:46:39 2006 +0000
2.3 @@ -475,10 +475,10 @@
2.4 return Parent::nodeFromId(id);
2.5 }
2.6 ANode fromId(int id, ANode) const {
2.7 - return Parent::fromANodeId(id);
2.8 + return Parent::nodeFromANodeId(id);
2.9 }
2.10 BNode fromId(int id, BNode) const {
2.11 - return Parent::fromBNodeId(id);
2.12 + return Parent::nodeFromBNodeId(id);
2.13 }
2.14 Edge fromId(int id, Edge) const {
2.15 return Parent::edgeFromId(id);
3.1 --- a/lemon/bits/graph_extender.h Tue Oct 03 11:24:41 2006 +0000
3.2 +++ b/lemon/bits/graph_extender.h Tue Oct 03 11:46:39 2006 +0000
3.3 @@ -730,206 +730,31 @@
3.4 template <typename Base>
3.5 class BpUGraphExtender : public Base {
3.6 public:
3.7 +
3.8 typedef Base Parent;
3.9 typedef BpUGraphExtender Graph;
3.10
3.11 typedef typename Parent::Node Node;
3.12 + typedef typename Parent::ANode ANode;
3.13 + typedef typename Parent::BNode BNode;
3.14 + typedef typename Parent::Edge Edge;
3.15 typedef typename Parent::UEdge UEdge;
3.16
3.17
3.18 - using Parent::first;
3.19 - using Parent::next;
3.20 -
3.21 - using Parent::id;
3.22 -
3.23 - class ANode : public Node {
3.24 - friend class BpUGraphExtender;
3.25 - public:
3.26 - ANode() {}
3.27 - ANode(const Node& node) : Node(node) {
3.28 - LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
3.29 - typename Parent::NodeSetError());
3.30 - }
3.31 - ANode(Invalid) : Node(INVALID) {}
3.32 - };
3.33 -
3.34 - void first(ANode& node) const {
3.35 - Parent::firstANode(static_cast<Node&>(node));
3.36 - }
3.37 - void next(ANode& node) const {
3.38 - Parent::nextANode(static_cast<Node&>(node));
3.39 + Node oppositeNode(const Node& node, const UEdge& edge) const {
3.40 + return Parent::aNode(edge) == node ?
3.41 + Parent::bNode(edge) : Parent::aNode(edge);
3.42 }
3.43
3.44 - int id(const ANode& node) const {
3.45 - return Parent::aNodeId(node);
3.46 - }
3.47 -
3.48 - class BNode : public Node {
3.49 - friend class BpUGraphExtender;
3.50 - public:
3.51 - BNode() {}
3.52 - BNode(const Node& node) : Node(node) {
3.53 - LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
3.54 - typename Parent::NodeSetError());
3.55 - }
3.56 - BNode(Invalid) : Node(INVALID) {}
3.57 - };
3.58 -
3.59 - void first(BNode& node) const {
3.60 - Parent::firstBNode(static_cast<Node&>(node));
3.61 - }
3.62 - void next(BNode& node) const {
3.63 - Parent::nextBNode(static_cast<Node&>(node));
3.64 - }
3.65 -
3.66 - int id(const BNode& node) const {
3.67 - return Parent::aNodeId(node);
3.68 - }
3.69 -
3.70 - Node source(const UEdge& edge) const {
3.71 - return aNode(edge);
3.72 - }
3.73 - Node target(const UEdge& edge) const {
3.74 - return bNode(edge);
3.75 - }
3.76 -
3.77 - void firstInc(UEdge& edge, bool& direction, const Node& node) const {
3.78 - if (Parent::aNode(node)) {
3.79 - Parent::firstFromANode(edge, node);
3.80 - direction = true;
3.81 - } else {
3.82 - Parent::firstFromBNode(edge, node);
3.83 - direction = static_cast<UEdge&>(edge) == INVALID;
3.84 - }
3.85 - }
3.86 - void nextInc(UEdge& edge, bool& direction) const {
3.87 - if (direction) {
3.88 - Parent::nextFromANode(edge);
3.89 - } else {
3.90 - Parent::nextFromBNode(edge);
3.91 - if (edge == INVALID) direction = true;
3.92 - }
3.93 - }
3.94 -
3.95 - class Edge : public UEdge {
3.96 - friend class BpUGraphExtender;
3.97 - protected:
3.98 - bool forward;
3.99 -
3.100 - Edge(const UEdge& edge, bool _forward)
3.101 - : UEdge(edge), forward(_forward) {}
3.102 -
3.103 - public:
3.104 - Edge() {}
3.105 - Edge (Invalid) : UEdge(INVALID), forward(true) {}
3.106 - bool operator==(const Edge& i) const {
3.107 - return UEdge::operator==(i) && forward == i.forward;
3.108 - }
3.109 - bool operator!=(const Edge& i) const {
3.110 - return UEdge::operator!=(i) || forward != i.forward;
3.111 - }
3.112 - bool operator<(const Edge& i) const {
3.113 - return UEdge::operator<(i) ||
3.114 - (!(i.forward<forward) && UEdge(*this)<UEdge(i));
3.115 - }
3.116 - };
3.117 -
3.118 - void first(Edge& edge) const {
3.119 - Parent::first(static_cast<UEdge&>(edge));
3.120 - edge.forward = true;
3.121 - }
3.122 -
3.123 - void next(Edge& edge) const {
3.124 - if (!edge.forward) {
3.125 - Parent::next(static_cast<UEdge&>(edge));
3.126 - }
3.127 - edge.forward = !edge.forward;
3.128 - }
3.129 -
3.130 - void firstOut(Edge& edge, const Node& node) const {
3.131 - if (Parent::aNode(node)) {
3.132 - Parent::firstFromANode(edge, node);
3.133 - edge.forward = true;
3.134 - } else {
3.135 - Parent::firstFromBNode(edge, node);
3.136 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.137 - }
3.138 - }
3.139 - void nextOut(Edge& edge) const {
3.140 - if (edge.forward) {
3.141 - Parent::nextFromANode(edge);
3.142 - } else {
3.143 - Parent::nextFromBNode(edge);
3.144 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.145 - }
3.146 - }
3.147 -
3.148 - void firstIn(Edge& edge, const Node& node) const {
3.149 - if (Parent::bNode(node)) {
3.150 - Parent::firstFromBNode(edge, node);
3.151 - edge.forward = true;
3.152 - } else {
3.153 - Parent::firstFromANode(edge, node);
3.154 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.155 - }
3.156 - }
3.157 - void nextIn(Edge& edge) const {
3.158 - if (edge.forward) {
3.159 - Parent::nextFromBNode(edge);
3.160 - } else {
3.161 - Parent::nextFromANode(edge);
3.162 - edge.forward = static_cast<UEdge&>(edge) == INVALID;
3.163 - }
3.164 - }
3.165 -
3.166 - Node source(const Edge& edge) const {
3.167 - return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
3.168 - }
3.169 - Node target(const Edge& edge) const {
3.170 - return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
3.171 - }
3.172 -
3.173 - int id(const Edge& edge) const {
3.174 - return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
3.175 - (edge.forward ? 0 : 1);
3.176 - }
3.177 - Edge edgeFromId(int id) const {
3.178 - return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
3.179 - }
3.180 - int maxEdgeId() const {
3.181 - return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
3.182 - }
3.183 -
3.184 - bool direction(const Edge& edge) const {
3.185 - return edge.forward;
3.186 - }
3.187 -
3.188 - Edge direct(const UEdge& edge, bool direction) const {
3.189 - return Edge(edge, direction);
3.190 - }
3.191 -
3.192 - int edgeNum() const {
3.193 - return 2 * Parent::uEdgeNum();
3.194 - }
3.195 -
3.196 - int uEdgeNum() const {
3.197 - return Parent::uEdgeNum();
3.198 - }
3.199 -
3.200 - Node oppositeNode(const UEdge& edge, const Node& node) const {
3.201 - return source(edge) == node ?
3.202 - target(edge) : source(edge);
3.203 - }
3.204 -
3.205 + using Parent::direct;
3.206 Edge direct(const UEdge& edge, const Node& node) const {
3.207 - return Edge(edge, node == Parent::source(edge));
3.208 + return Parent::direct(edge, node == Parent::source(edge));
3.209 }
3.210
3.211 Edge oppositeEdge(const Edge& edge) const {
3.212 - return Parent::direct(edge, !Parent::direction(edge));
3.213 + return direct(edge, !Parent::direction(edge));
3.214 }
3.215 -
3.216 -
3.217 +
3.218 int maxId(Node) const {
3.219 return Parent::maxNodeId();
3.220 }
3.221 @@ -940,7 +765,7 @@
3.222 return Parent::maxANodeId();
3.223 }
3.224 int maxId(Edge) const {
3.225 - return maxEdgeId();
3.226 + return Parent::maxEdgeId();
3.227 }
3.228 int maxId(UEdge) const {
3.229 return Parent::maxUEdgeId();
3.230 @@ -951,10 +776,10 @@
3.231 return Parent::nodeFromId(id);
3.232 }
3.233 ANode fromId(int id, ANode) const {
3.234 - return Parent::fromANodeId(id);
3.235 + return Parent::nodeFromANodeId(id);
3.236 }
3.237 BNode fromId(int id, BNode) const {
3.238 - return Parent::fromBNodeId(id);
3.239 + return Parent::nodeFromBNodeId(id);
3.240 }
3.241 Edge fromId(int id, Edge) const {
3.242 return Parent::edgeFromId(id);
3.243 @@ -1304,12 +1129,9 @@
3.244 template <typename CMap>
3.245 NodeMap& operator=(const CMap& cmap) {
3.246 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
3.247 - const typename Parent::Notifier* notifier = Parent::getNotifier();
3.248 - Edge it;
3.249 - for (graph.first(it); it != INVALID; graph.next(it)) {
3.250 - Parent::set(it, cmap[it]);
3.251 - }
3.252 - return *this;
3.253 + aNodeMap = cmap;
3.254 + bNodeMap = cmap;
3.255 + return *this;
3.256 }
3.257
3.258 ConstReference operator[](const Key& node) const {
3.259 @@ -1459,8 +1281,8 @@
3.260 getNotifier(UEdge()).add(uedge);
3.261
3.262 std::vector<Edge> edges;
3.263 - edges.push_back(direct(uedge, true));
3.264 - edges.push_back(direct(uedge, false));
3.265 + edges.push_back(Parent::direct(uedge, true));
3.266 + edges.push_back(Parent::direct(uedge, false));
3.267 getNotifier(Edge()).add(edges);
3.268
3.269 return uedge;
3.270 @@ -1499,8 +1321,8 @@
3.271
3.272 void erase(const UEdge& uedge) {
3.273 std::vector<Edge> edges;
3.274 - edges.push_back(direct(uedge, true));
3.275 - edges.push_back(direct(uedge, false));
3.276 + edges.push_back(Parent::direct(uedge, true));
3.277 + edges.push_back(Parent::direct(uedge, false));
3.278 getNotifier(Edge()).erase(edges);
3.279 getNotifier(UEdge()).erase(uedge);
3.280 Parent::erase(uedge);
3.281 @@ -1526,7 +1348,7 @@
3.282 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
3.283 UEdge uedge = Parent::findUEdge(u, v, prev);
3.284 if (uedge != INVALID) {
3.285 - return direct(uedge, Parent::aNode(u));
3.286 + return Parent::direct(uedge, Parent::aNode(u));
3.287 } else {
3.288 return INVALID;
3.289 }
4.1 --- a/lemon/bpugraph_adaptor.h Tue Oct 03 11:24:41 2006 +0000
4.2 +++ b/lemon/bpugraph_adaptor.h Tue Oct 03 11:46:39 2006 +0000
4.3 @@ -87,6 +87,12 @@
4.4 void firstInc(UEdge &i, bool &d, const Node &n) const {
4.5 graph->firstInc(i, d, n);
4.6 }
4.7 + void firstFromANode(UEdge& i, const Node& n) const {
4.8 + graph->firstFromANode(i, n);
4.9 + }
4.10 + void firstFromBNode(UEdge& i, const Node& n) const {
4.11 + graph->firstFromBNode(i, n);
4.12 + }
4.13
4.14 void next(Node& i) const { graph->next(i); }
4.15 void nextANode(Node& i) const { graph->nextANode(i); }
4.16 @@ -96,6 +102,8 @@
4.17 void nextIn(Edge& i) const { graph->nextIn(i); }
4.18 void nextOut(Edge& i) const { graph->nextOut(i); }
4.19 void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
4.20 + void nextFromANode(UEdge& i) const { graph->nextFromANode(i); }
4.21 + void nextFromBNode(UEdge& i) const { graph->nextFromBNode(i); }
4.22
4.23 Node source(const UEdge& e) const { return graph->source(e); }
4.24 Node target(const UEdge& e) const { return graph->target(e); }
4.25 @@ -149,8 +157,8 @@
4.26 int id(const UEdge& e) const { return graph->id(e); }
4.27
4.28 Node fromNodeId(int id) const { return graph->fromNodeId(id); }
4.29 - ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
4.30 - BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
4.31 + ANode nodeFromANodeId(int id) const { return graph->nodeFromANodeId(id); }
4.32 + BNode nodeFromBNodeId(int id) const { return graph->nodeFromBNodeId(id); }
4.33 Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
4.34 UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
4.35
4.36 @@ -340,11 +348,21 @@
4.37 void nextANode(Node& i) const { Parent::nextBNode(i); }
4.38 void nextBNode(Node& i) const { Parent::nextANode(i); }
4.39
4.40 + void firstFromANode(UEdge& i, const Node& n) const {
4.41 + Parent::firstFromBNode(i, n);
4.42 + }
4.43 + void firstFromBNode(UEdge& i, const Node& n) const {
4.44 + Parent::firstFromANode(i, n);
4.45 + }
4.46 +
4.47 + void nextFromANode(UEdge& i) const { Parent::nextFromBNode(i); }
4.48 + void nextFromBNode(UEdge& i) const { Parent::nextFromANode(i); }
4.49 +
4.50 int id(const ANode& v) const { return Parent::id(v); }
4.51 int id(const BNode& v) const { return Parent::id(v); }
4.52
4.53 - ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
4.54 - BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
4.55 + ANode nodeFromANodeId(int id) const { return Parent::nodeFromBNodeId(id); }
4.56 + BNode nodeFromBNodeId(int id) const { return Parent::nodeFromANodeId(id); }
4.57
4.58 int maxANodeId() const { return Parent::maxBNodeId(); }
4.59 int maxBNodeId() const { return Parent::maxANodeId(); }
4.60 @@ -549,7 +567,10 @@
4.61 /// Bipartite graph adaptor to implement matchings. It implements
4.62 /// the residual graph of the matching.
4.63 template <typename _BpUGraph,
4.64 - typename _ANMatchingMap, typename _BNMatchingMap>
4.65 + typename _ANMatchingMap =
4.66 + typename _BpUGraph::template ANodeMap<typename _BpUGraph::UEdge>,
4.67 + typename _BNMatchingMap =
4.68 + typename _BpUGraph::template BNodeMap<typename _BpUGraph::UEdge> >
4.69 class MatchingBpUGraphAdaptor
4.70 : public BpUGraphAdaptorExtender<
4.71 MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> >
5.1 --- a/lemon/concept/bpugraph.h Tue Oct 03 11:24:41 2006 +0000
5.2 +++ b/lemon/concept/bpugraph.h Tue Oct 03 11:46:39 2006 +0000
5.3 @@ -132,25 +132,31 @@
5.4 /// This class is just a helper class for ANodes, it is not
5.5 /// suggested to use it directly. It can be converted easily to
5.6 /// node and vice versa. The usage of this class is limited
5.7 - /// two use just as template parameters for special map types.
5.8 - class ANode {
5.9 + /// to use just as template parameters for special map types.
5.10 + class ANode : public Node {
5.11 public:
5.12 /// Default constructor
5.13
5.14 /// @warning The default constructor sets the iterator
5.15 /// to an undefined value.
5.16 - ANode() { }
5.17 + ANode() : Node() { }
5.18 /// Copy constructor.
5.19
5.20 /// Copy constructor.
5.21 ///
5.22 - ANode(const ANode&) { }
5.23 + ANode(const ANode&) : Node() { }
5.24
5.25 /// Construct the same node as ANode.
5.26
5.27 /// Construct the same node as ANode. It may throws assertion
5.28 /// when the given node is from the BNode set.
5.29 - ANode(const Node&) { }
5.30 + ANode(const Node&) : Node() { }
5.31 +
5.32 + /// Assign node to A-node.
5.33 +
5.34 + /// Besides the core graph item functionality each node should
5.35 + /// be convertible to the represented A-node if it is it possible.
5.36 + ANode& operator=(const Node&) { return *this; }
5.37
5.38 /// Invalid constructor \& conversion.
5.39
5.40 @@ -186,25 +192,31 @@
5.41 /// This class is just a helper class for BNodes, it is not
5.42 /// suggested to use it directly. It can be converted easily to
5.43 /// node and vice versa. The usage of this class is limited
5.44 - /// two use just as template parameters for special map types.
5.45 - class BNode {
5.46 + /// to use just as template parameters for special map types.
5.47 + class BNode : public Node {
5.48 public:
5.49 /// Default constructor
5.50
5.51 /// @warning The default constructor sets the iterator
5.52 /// to an undefined value.
5.53 - BNode() { }
5.54 + BNode() : Node() { }
5.55 /// Copy constructor.
5.56
5.57 /// Copy constructor.
5.58 ///
5.59 - BNode(const BNode&) { }
5.60 + BNode(const BNode&) : Node() { }
5.61
5.62 /// Construct the same node as BNode.
5.63
5.64 /// Construct the same node as BNode. It may throws assertion
5.65 /// when the given node is from the ANode set.
5.66 - BNode(const Node&) { }
5.67 + BNode(const Node&) : Node() { }
5.68 +
5.69 + /// Assign node to B-node.
5.70 +
5.71 + /// Besides the core graph item functionality each node should
5.72 + /// be convertible to the represented B-node if it is it possible.
5.73 + BNode& operator=(const Node&) { return *this; }
5.74
5.75 /// Invalid constructor \& conversion.
5.76
5.77 @@ -717,7 +729,12 @@
5.78 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
5.79 ///Assignment operator
5.80 NodeMap& operator=(const NodeMap&) { return *this; }
5.81 - // \todo fix this concept
5.82 + ///Assignment operator
5.83 + template <typename CMap>
5.84 + NodeMap& operator=(const CMap&) {
5.85 + checkConcept<ReadMap<Node, T>, CMap>();
5.86 + return *this;
5.87 + }
5.88 };
5.89
5.90 /// \brief Read write map of the ANodes to type \c T.
5.91 @@ -738,10 +755,15 @@
5.92 ANodeMap(const BpUGraph&, T) { }
5.93
5.94 ///Copy constructor
5.95 - ANodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
5.96 + ANodeMap(const ANodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
5.97 ///Assignment operator
5.98 - ANodeMap& operator=(const NodeMap&) { return *this; }
5.99 - // \todo fix this concept
5.100 + ANodeMap& operator=(const ANodeMap&) { return *this; }
5.101 + ///Assignment operator
5.102 + template <typename CMap>
5.103 + ANodeMap& operator=(const CMap&) {
5.104 + checkConcept<ReadMap<Node, T>, CMap>();
5.105 + return *this;
5.106 + }
5.107 };
5.108
5.109 /// \brief Read write map of the BNodes to type \c T.
5.110 @@ -762,10 +784,15 @@
5.111 BNodeMap(const BpUGraph&, T) { }
5.112
5.113 ///Copy constructor
5.114 - BNodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
5.115 + BNodeMap(const BNodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
5.116 ///Assignment operator
5.117 - BNodeMap& operator=(const NodeMap&) { return *this; }
5.118 - // \todo fix this concept
5.119 + BNodeMap& operator=(const BNodeMap&) { return *this; }
5.120 + ///Assignment operator
5.121 + template <typename CMap>
5.122 + BNodeMap& operator=(const CMap&) {
5.123 + checkConcept<ReadMap<Node, T>, CMap>();
5.124 + return *this;
5.125 + }
5.126 };
5.127
5.128 /// \brief Read write map of the directed edges to type \c T.
5.129 @@ -788,7 +815,12 @@
5.130 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
5.131 ///Assignment operator
5.132 EdgeMap& operator=(const EdgeMap&) { return *this; }
5.133 - // \todo fix this concept
5.134 + ///Assignment operator
5.135 + template <typename CMap>
5.136 + EdgeMap& operator=(const CMap&) {
5.137 + checkConcept<ReadMap<Edge, T>, CMap>();
5.138 + return *this;
5.139 + }
5.140 };
5.141
5.142 /// Read write map of the undirected edges to type \c T.
5.143 @@ -811,7 +843,12 @@
5.144 UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {}
5.145 ///Assignment operator
5.146 UEdgeMap &operator=(const UEdgeMap&) { return *this; }
5.147 - // \todo fix this concept
5.148 + ///Assignment operator
5.149 + template <typename CMap>
5.150 + UEdgeMap& operator=(const CMap&) {
5.151 + checkConcept<ReadMap<UEdge, T>, CMap>();
5.152 + return *this;
5.153 + }
5.154 };
5.155
5.156 /// \brief Direct the given undirected edge.
5.157 @@ -933,9 +970,41 @@
5.158 return INVALID;
5.159 }
5.160
5.161 + void first(Node&) const {}
5.162 + void next(Node&) const {}
5.163 +
5.164 + void first(Edge&) const {}
5.165 + void next(Edge&) const {}
5.166 +
5.167 + void first(UEdge&) const {}
5.168 + void next(UEdge&) const {}
5.169 +
5.170 + void firstANode(Node&) const {}
5.171 + void nextANode(Node&) const {}
5.172 +
5.173 + void firstBNode(Node&) const {}
5.174 + void nextBNode(Node&) const {}
5.175 +
5.176 + void firstIn(Edge&, const Node&) const {}
5.177 + void nextIn(Edge&) const {}
5.178 +
5.179 + void firstOut(Edge&, const Node&) const {}
5.180 + void nextOut(Edge&) const {}
5.181 +
5.182 + void firstInc(UEdge &, bool &, const Node &) const {}
5.183 + void nextInc(UEdge &, bool &) const {}
5.184 +
5.185 + void firstFromANode(UEdge&, const Node&) const {}
5.186 + void nextFromANode(UEdge&) const {}
5.187 +
5.188 + void firstFromBNode(UEdge&, const Node&) const {}
5.189 + void nextFromBNode(UEdge&) const {}
5.190 +
5.191 template <typename Graph>
5.192 struct Constraints {
5.193 void constraints() {
5.194 + checkConcept<IterableBpUGraphComponent<>, Graph>();
5.195 + checkConcept<MappableBpUGraphComponent<>, Graph>();
5.196 }
5.197 };
5.198
6.1 --- a/lemon/concept/graph.h Tue Oct 03 11:24:41 2006 +0000
6.2 +++ b/lemon/concept/graph.h Tue Oct 03 11:46:39 2006 +0000
6.3 @@ -439,7 +439,6 @@
6.4 template <typename RGraph>
6.5 struct Constraints {
6.6 void constraints() {
6.7 - checkConcept<BaseIterableGraphComponent<>, Graph>();
6.8 checkConcept<IterableGraphComponent<>, Graph>();
6.9 checkConcept<MappableGraphComponent<>, Graph>();
6.10 }
7.1 --- a/lemon/concept/graph_components.h Tue Oct 03 11:24:41 2006 +0000
7.2 +++ b/lemon/concept/graph_components.h Tue Oct 03 11:46:39 2006 +0000
7.3 @@ -218,6 +218,11 @@
7.4 /// Besides the core graph item functionality each edge should
7.5 /// be convertible to the represented undirected edge.
7.6 UEdge(const Edge&) {}
7.7 + /// \brief Assign edge to undirected edge.
7.8 + ///
7.9 + /// Besides the core graph item functionality each edge should
7.10 + /// be convertible to the represented undirected edge.
7.11 + UEdge& operator=(const Edge&) { return *this; }
7.12 };
7.13
7.14 /// \brief Returns the direction of the edge.
7.15 @@ -290,173 +295,149 @@
7.16
7.17 };
7.18
7.19 - /// \brief An empty iterable base graph class.
7.20 + /// \brief An empty base bipartite undirected graph class.
7.21 ///
7.22 - /// This class provides beside the core graph features
7.23 - /// core iterable interface for the graph structure.
7.24 - /// Most of the base graphs should be conform to this concept.
7.25 - template <typename _Base = BaseGraphComponent>
7.26 - class BaseIterableGraphComponent : public _Base {
7.27 + /// This class provides the minimal set of features needed for an
7.28 + /// bipartite undirected graph structure. All bipartite undirected
7.29 + /// graph concepts have to be conform to this base graph. It just
7.30 + /// provides types for nodes, A-nodes, B-nodes, edges and
7.31 + /// undirected edges and functions to get the source and the
7.32 + /// target of the edges and undirected edges, conversion from
7.33 + /// edges to undirected edges and function to get both direction
7.34 + /// of the undirected edges.
7.35 + class BaseBpUGraphComponent : public BaseUGraphComponent {
7.36 public:
7.37 + typedef BaseUGraphComponent::Node Node;
7.38 + typedef BaseUGraphComponent::Edge Edge;
7.39 + typedef BaseUGraphComponent::UEdge UEdge;
7.40
7.41 - typedef _Base Base;
7.42 - typedef typename Base::Node Node;
7.43 - typedef typename Base::Edge Edge;
7.44 + /// \brief Helper class for A-nodes.
7.45 + ///
7.46 + /// This class is just a helper class for A-nodes, it is not
7.47 + /// suggested to use it directly. It can be converted easily to
7.48 + /// node and vice versa. The usage of this class is limited
7.49 + /// to use just as template parameters for special map types.
7.50 + class ANode : public Node {
7.51 + public:
7.52 + typedef Node Parent;
7.53
7.54 - /// \brief Gives back the first node in the iterating order.
7.55 - ///
7.56 - /// Gives back the first node in the iterating order.
7.57 - ///
7.58 - void first(Node&) const {}
7.59 + /// \brief Default constructor.
7.60 + ///
7.61 + /// \warning The default constructor is not required to set
7.62 + /// the item to some well-defined value. So you should consider it
7.63 + /// as uninitialized.
7.64 + ANode() {}
7.65 + /// \brief Copy constructor.
7.66 + ///
7.67 + /// Copy constructor.
7.68 + ///
7.69 + ANode(const ANode &) : Parent() {}
7.70 + /// \brief Invalid constructor \& conversion.
7.71 + ///
7.72 + /// This constructor initializes the item to be invalid.
7.73 + /// \sa Invalid for more details.
7.74 + ANode(Invalid) {}
7.75 + /// \brief Converter from node to A-node.
7.76 + ///
7.77 + /// Besides the core graph item functionality each node should
7.78 + /// be convertible to the represented A-node if it is it possible.
7.79 + ANode(const Node&) {}
7.80 + /// \brief Assign node to A-node.
7.81 + ///
7.82 + /// Besides the core graph item functionality each node should
7.83 + /// be convertible to the represented A-node if it is it possible.
7.84 + ANode& operator=(const Node&) { return *this; }
7.85 + };
7.86
7.87 - /// \brief Gives back the next node in the iterating order.
7.88 + /// \brief Helper class for B-nodes.
7.89 ///
7.90 - /// Gives back the next node in the iterating order.
7.91 - ///
7.92 - void next(Node&) const {}
7.93 + /// This class is just a helper class for B-nodes, it is not
7.94 + /// suggested to use it directly. It can be converted easily to
7.95 + /// node and vice versa. The usage of this class is limited
7.96 + /// to use just as template parameters for special map types.
7.97 + class BNode : public Node {
7.98 + public:
7.99 + typedef Node Parent;
7.100
7.101 - /// \brief Gives back the first edge in the iterating order.
7.102 + /// \brief Default constructor.
7.103 + ///
7.104 + /// \warning The default constructor is not required to set
7.105 + /// the item to some well-defined value. So you should consider it
7.106 + /// as uninitialized.
7.107 + BNode() {}
7.108 + /// \brief Copy constructor.
7.109 + ///
7.110 + /// Copy constructor.
7.111 + ///
7.112 + BNode(const BNode &) : Parent() {}
7.113 + /// \brief Invalid constructor \& conversion.
7.114 + ///
7.115 + /// This constructor initializes the item to be invalid.
7.116 + /// \sa Invalid for more details.
7.117 + BNode(Invalid) {}
7.118 + /// \brief Converter from node to B-node.
7.119 + ///
7.120 + /// Besides the core graph item functionality each node should
7.121 + /// be convertible to the represented B-node if it is it possible.
7.122 + BNode(const Node&) {}
7.123 + /// \brief Assign node to B-node.
7.124 + ///
7.125 + /// Besides the core graph item functionality each node should
7.126 + /// be convertible to the represented B-node if it is it possible.
7.127 + BNode& operator=(const Node&) { return *this; }
7.128 + };
7.129 +
7.130 + /// \brief Gives back %true when the node is A-node.
7.131 ///
7.132 - /// Gives back the first edge in the iterating order.
7.133 - ///
7.134 - void first(Edge&) const {}
7.135 + /// Gives back %true when the node is A-node.
7.136 + bool aNode(const Node&) const { return false; }
7.137
7.138 - /// \brief Gives back the next edge in the iterating order.
7.139 + /// \brief Gives back %true when the node is B-node.
7.140 ///
7.141 - /// Gives back the next edge in the iterating order.
7.142 - ///
7.143 - void next(Edge&) const {}
7.144 + /// Gives back %true when the node is B-node.
7.145 + bool bNode(const Node&) const { return false; }
7.146
7.147 + /// \brief Gives back the A-node of the undirected edge.
7.148 + ///
7.149 + /// Gives back the A-node of the undirected edge.
7.150 + Node aNode(const UEdge&) const { return INVALID; }
7.151
7.152 - /// \brief Gives back the first of the edges point to the given
7.153 - /// node.
7.154 + /// \brief Gives back the B-node of the undirected edge.
7.155 ///
7.156 - /// Gives back the first of the edges point to the given node.
7.157 - ///
7.158 - void firstIn(Edge&, const Node&) const {}
7.159 -
7.160 - /// \brief Gives back the next of the edges points to the given
7.161 - /// node.
7.162 - ///
7.163 - /// Gives back the next of the edges points to the given node.
7.164 - ///
7.165 - void nextIn(Edge&) const {}
7.166 -
7.167 - /// \brief Gives back the first of the edges start from the
7.168 - /// given node.
7.169 - ///
7.170 - /// Gives back the first of the edges start from the given node.
7.171 - ///
7.172 - void firstOut(Edge&, const Node&) const {}
7.173 -
7.174 - /// \brief Gives back the next of the edges start from the given
7.175 - /// node.
7.176 - ///
7.177 - /// Gives back the next of the edges start from the given node.
7.178 - ///
7.179 - void nextOut(Edge&) const {}
7.180 -
7.181 -
7.182 + /// Gives back the B-node of the undirected edge.
7.183 + Node bNode(const UEdge&) const { return INVALID; }
7.184 +
7.185 template <typename _Graph>
7.186 struct Constraints {
7.187 + typedef typename _Graph::Node Node;
7.188 + typedef typename _Graph::ANode ANode;
7.189 + typedef typename _Graph::BNode BNode;
7.190 + typedef typename _Graph::Edge Edge;
7.191 + typedef typename _Graph::UEdge UEdge;
7.192
7.193 void constraints() {
7.194 - checkConcept< BaseGraphComponent, _Graph >();
7.195 - typename _Graph::Node node(INVALID);
7.196 - typename _Graph::Edge edge(INVALID);
7.197 + checkConcept<BaseUGraphComponent, _Graph>();
7.198 + checkConcept<GraphItem<'a'>, ANode>();
7.199 + checkConcept<GraphItem<'b'>, BNode>();
7.200 {
7.201 - graph.first(node);
7.202 - graph.next(node);
7.203 - }
7.204 - {
7.205 - graph.first(edge);
7.206 - graph.next(edge);
7.207 - }
7.208 - {
7.209 - graph.firstIn(edge, node);
7.210 - graph.nextIn(edge);
7.211 - }
7.212 - {
7.213 - graph.firstOut(edge, node);
7.214 - graph.nextOut(edge);
7.215 - }
7.216 + Node n;
7.217 + UEdge ue(INVALID);
7.218 + bool b;
7.219 + n = graph.aNode(ue);
7.220 + n = graph.bNode(ue);
7.221 + b = graph.aNode(n);
7.222 + b = graph.bNode(n);
7.223 + ANode an;
7.224 + an = n; n = an;
7.225 + BNode bn;
7.226 + bn = n; n = bn;
7.227 + ignore_unused_variable_warning(b);
7.228 + }
7.229 }
7.230 -
7.231 +
7.232 const _Graph& graph;
7.233 };
7.234 - };
7.235
7.236 - /// \brief An empty iterable base undirected graph class.
7.237 - ///
7.238 - /// This class provides beside the core undirceted graph features
7.239 - /// core iterable interface for the undirected graph structure.
7.240 - /// Most of the base undirected graphs should be conform to this
7.241 - /// concept.
7.242 - template <typename _Base = BaseUGraphComponent>
7.243 - class BaseIterableUGraphComponent
7.244 - : public BaseIterableGraphComponent<_Base> {
7.245 - public:
7.246 -
7.247 - typedef _Base Base;
7.248 - typedef typename Base::UEdge UEdge;
7.249 - typedef typename Base::Node Node;
7.250 -
7.251 - using BaseIterableGraphComponent<_Base>::first;
7.252 - using BaseIterableGraphComponent<_Base>::next;
7.253 -
7.254 - /// \brief Gives back the first undirected edge in the iterating
7.255 - /// order.
7.256 - ///
7.257 - /// Gives back the first undirected edge in the iterating order.
7.258 - ///
7.259 - void first(UEdge&) const {}
7.260 -
7.261 - /// \brief Gives back the next undirected edge in the iterating
7.262 - /// order.
7.263 - ///
7.264 - /// Gives back the next undirected edge in the iterating order.
7.265 - ///
7.266 - void next(UEdge&) const {}
7.267 -
7.268 -
7.269 - /// \brief Gives back the first of the undirected edges from the
7.270 - /// given node.
7.271 - ///
7.272 - /// Gives back the first of the undirected edges from the given
7.273 - /// node. The bool parameter gives back that direction which
7.274 - /// gives a good direction of the uedge so the source of the
7.275 - /// directed edge is the given node.
7.276 - void firstInc(UEdge&, bool&, const Node&) const {}
7.277 -
7.278 - /// \brief Gives back the next of the undirected edges from the
7.279 - /// given node.
7.280 - ///
7.281 - /// Gives back the next of the undirected edges from the given
7.282 - /// node. The bool parameter should be used as the \c firstInc()
7.283 - /// use it.
7.284 - void nextInc(UEdge&, bool&) const {}
7.285 -
7.286 - template <typename _Graph>
7.287 - struct Constraints {
7.288 -
7.289 - void constraints() {
7.290 - checkConcept<Base, _Graph >();
7.291 - checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
7.292 - typename _Graph::Node node(INVALID);
7.293 - typename _Graph::UEdge uedge(INVALID);
7.294 - bool dir;
7.295 - {
7.296 - graph.first(uedge);
7.297 - graph.next(uedge);
7.298 - }
7.299 - {
7.300 - graph.firstInc(uedge, dir, node);
7.301 - graph.nextInc(uedge, dir);
7.302 - }
7.303 - }
7.304 -
7.305 - const _Graph& graph;
7.306 - };
7.307 };
7.308
7.309 /// \brief An empty idable base graph class.
7.310 @@ -517,7 +498,7 @@
7.311 struct Constraints {
7.312
7.313 void constraints() {
7.314 - checkConcept< BaseGraphComponent, _Graph >();
7.315 + checkConcept<Base, _Graph >();
7.316 typename _Graph::Node node;
7.317 int nid = graph.id(node);
7.318 nid = graph.id(node);
7.319 @@ -590,214 +571,81 @@
7.320 };
7.321 };
7.322
7.323 - /// \brief An empty extendable base graph class.
7.324 - ///
7.325 - /// This class provides beside the core graph features
7.326 - /// core graph extend interface for the graph structure.
7.327 - /// The most of the base graphs should be conform to this concept.
7.328 - template <typename _Base = BaseGraphComponent>
7.329 - class BaseExtendableGraphComponent : public _Base {
7.330 - public:
7.331 -
7.332 - typedef typename _Base::Node Node;
7.333 - typedef typename _Base::Edge Edge;
7.334 -
7.335 - /// \brief Adds a new node to the graph.
7.336 - ///
7.337 - /// Adds a new node to the graph.
7.338 - ///
7.339 - Node addNode() {
7.340 - return INVALID;
7.341 - }
7.342 -
7.343 - /// \brief Adds a new edge connects the given two nodes.
7.344 - ///
7.345 - /// Adds a new edge connects the the given two nodes.
7.346 - Edge addEdge(const Node&, const Node&) {
7.347 - return INVALID;
7.348 - }
7.349 -
7.350 - template <typename _Graph>
7.351 - struct Constraints {
7.352 - void constraints() {
7.353 - typename _Graph::Node node_a, node_b;
7.354 - node_a = graph.addNode();
7.355 - node_b = graph.addNode();
7.356 - typename _Graph::Edge edge;
7.357 - edge = graph.addEdge(node_a, node_b);
7.358 - }
7.359 -
7.360 - _Graph& graph;
7.361 - };
7.362 - };
7.363 -
7.364 - /// \brief An empty extendable base undirected graph class.
7.365 - ///
7.366 - /// This class provides beside the core undirected graph features
7.367 - /// core undircted graph extend interface for the graph structure.
7.368 - /// The most of the base graphs should be conform to this concept.
7.369 - template <typename _Base = BaseUGraphComponent>
7.370 - class BaseExtendableUGraphComponent : public _Base {
7.371 - public:
7.372 -
7.373 - typedef typename _Base::Node Node;
7.374 - typedef typename _Base::UEdge UEdge;
7.375 -
7.376 - /// \brief Adds a new node to the graph.
7.377 - ///
7.378 - /// Adds a new node to the graph.
7.379 - ///
7.380 - Node addNode() {
7.381 - return INVALID;
7.382 - }
7.383 -
7.384 - /// \brief Adds a new edge connects the given two nodes.
7.385 - ///
7.386 - /// Adds a new edge connects the the given two nodes.
7.387 - UEdge addEdge(const Node&, const Node&) {
7.388 - return INVALID;
7.389 - }
7.390 -
7.391 - template <typename _Graph>
7.392 - struct Constraints {
7.393 - void constraints() {
7.394 - typename _Graph::Node node_a, node_b;
7.395 - node_a = graph.addNode();
7.396 - node_b = graph.addNode();
7.397 - typename _Graph::UEdge uedge;
7.398 - uedge = graph.addUEdge(node_a, node_b);
7.399 - }
7.400 -
7.401 - _Graph& graph;
7.402 - };
7.403 - };
7.404 -
7.405 - /// \brief An empty erasable base graph class.
7.406 + /// \brief An empty idable base bipartite undirected graph class.
7.407 ///
7.408 - /// This class provides beside the core graph features
7.409 - /// core erase functions for the graph structure.
7.410 - /// The most of the base graphs should be conform to this concept.
7.411 - template <typename _Base = BaseGraphComponent>
7.412 - class BaseErasableGraphComponent : public _Base {
7.413 + /// This class provides beside the core bipartite undirected graph
7.414 + /// features core id functions for the bipartite undirected graph
7.415 + /// structure. The most of the base undirected graphs should be
7.416 + /// conform to this concept.
7.417 + template <typename _Base = BaseBpUGraphComponent>
7.418 + class IDableBpUGraphComponent : public IDableUGraphComponent<_Base> {
7.419 public:
7.420
7.421 typedef _Base Base;
7.422 typedef typename Base::Node Node;
7.423 - typedef typename Base::Edge Edge;
7.424
7.425 - /// \brief Erase a node from the graph.
7.426 + using IDableUGraphComponent<_Base>::id;
7.427 +
7.428 + /// \brief Gives back an unique integer id for the ANode.
7.429 ///
7.430 - /// Erase a node from the graph. This function should not
7.431 - /// erase edges connecting to the Node.
7.432 - void erase(const Node&) {}
7.433 + /// Gives back an unique integer id for the ANode.
7.434 + ///
7.435 + int aNodeId(const Node&) const { return -1;}
7.436
7.437 - /// \brief Erase an edge from the graph.
7.438 + /// \brief Gives back the undirected edge by the unique id.
7.439 ///
7.440 - /// Erase an edge from the graph.
7.441 + /// Gives back the undirected edge by the unique id. If the
7.442 + /// graph does not contain edge with the given id then the
7.443 + /// result of the function is undetermined.
7.444 + Node nodeFromANodeId(int) const { return INVALID;}
7.445 +
7.446 + /// \brief Gives back an integer greater or equal to the maximum
7.447 + /// ANode id.
7.448 ///
7.449 - void erase(const Edge&) {}
7.450 + /// Gives back an integer greater or equal to the maximum ANode
7.451 + /// id.
7.452 + int maxANodeId() const { return -1;}
7.453 +
7.454 + /// \brief Gives back an unique integer id for the BNode.
7.455 + ///
7.456 + /// Gives back an unique integer id for the BNode.
7.457 + ///
7.458 + int bNodeId(const Node&) const { return -1;}
7.459 +
7.460 + /// \brief Gives back the undirected edge by the unique id.
7.461 + ///
7.462 + /// Gives back the undirected edge by the unique id. If the
7.463 + /// graph does not contain edge with the given id then the
7.464 + /// result of the function is undetermined.
7.465 + Node nodeFromBNodeId(int) const { return INVALID;}
7.466 +
7.467 + /// \brief Gives back an integer greater or equal to the maximum
7.468 + /// BNode id.
7.469 + ///
7.470 + /// Gives back an integer greater or equal to the maximum BNode
7.471 + /// id.
7.472 + int maxBNodeId() const { return -1;}
7.473
7.474 template <typename _Graph>
7.475 struct Constraints {
7.476 +
7.477 void constraints() {
7.478 - typename _Graph::Node node;
7.479 - graph.erase(node);
7.480 - typename _Graph::Edge edge;
7.481 - graph.erase(edge);
7.482 + checkConcept<Base, _Graph >();
7.483 + checkConcept<IDableGraphComponent<Base>, _Graph >();
7.484 + typename _Graph::Node node(INVALID);
7.485 + int id;
7.486 + id = graph.aNodeId(node);
7.487 + id = graph.bNodeId(node);
7.488 + node = graph.nodeFromANodeId(id);
7.489 + node = graph.nodeFromBNodeId(id);
7.490 + id = graph.maxANodeId();
7.491 + id = graph.maxBNodeId();
7.492 }
7.493
7.494 - _Graph& graph;
7.495 + const _Graph& graph;
7.496 };
7.497 };
7.498
7.499 - /// \brief An empty erasable base undirected graph class.
7.500 - ///
7.501 - /// This class provides beside the core undirected graph features
7.502 - /// core erase functions for the undirceted graph structure.
7.503 - template <typename _Base = BaseUGraphComponent>
7.504 - class BaseErasableUGraphComponent : public _Base {
7.505 - public:
7.506 -
7.507 - typedef _Base Base;
7.508 - typedef typename Base::Node Node;
7.509 - typedef typename Base::UEdge UEdge;
7.510 -
7.511 - /// \brief Erase a node from the graph.
7.512 - ///
7.513 - /// Erase a node from the graph. This function should not
7.514 - /// erase edges connecting to the Node.
7.515 - void erase(const Node&) {}
7.516 -
7.517 - /// \brief Erase an edge from the graph.
7.518 - ///
7.519 - /// Erase an edge from the graph.
7.520 - ///
7.521 - void erase(const UEdge&) {}
7.522 -
7.523 - template <typename _Graph>
7.524 - struct Constraints {
7.525 - void constraints() {
7.526 - typename _Graph::Node node;
7.527 - graph.erase(node);
7.528 - typename _Graph::Edge edge;
7.529 - graph.erase(edge);
7.530 - }
7.531 -
7.532 - _Graph& graph;
7.533 - };
7.534 - };
7.535 -
7.536 - /// \brief An empty clearable base graph class.
7.537 - ///
7.538 - /// This class provides beside the core graph features
7.539 - /// core clear functions for the graph structure.
7.540 - /// The most of the base graphs should be conform to this concept.
7.541 - template <typename _Base = BaseGraphComponent>
7.542 - class BaseClearableGraphComponent : public _Base {
7.543 - public:
7.544 -
7.545 - /// \brief Erase all the nodes and edges from the graph.
7.546 - ///
7.547 - /// Erase all the nodes and edges from the graph.
7.548 - ///
7.549 - void clear() {}
7.550 -
7.551 - template <typename _Graph>
7.552 - struct Constraints {
7.553 - void constraints() {
7.554 - graph.clear();
7.555 - }
7.556 -
7.557 - _Graph graph;
7.558 - };
7.559 - };
7.560 -
7.561 - /// \brief An empty clearable base undirected graph class.
7.562 - ///
7.563 - /// This class provides beside the core undirected graph features
7.564 - /// core clear functions for the undirected graph structure.
7.565 - /// The most of the base graphs should be conform to this concept.
7.566 - template <typename _Base = BaseUGraphComponent>
7.567 - class BaseClearableUGraphComponent : public _Base {
7.568 - public:
7.569 -
7.570 - /// \brief Erase all the nodes and undirected edges from the graph.
7.571 - ///
7.572 - /// Erase all the nodes and undirected edges from the graph.
7.573 - ///
7.574 - void clear() {}
7.575 -
7.576 - template <typename _Graph>
7.577 - struct Constraints {
7.578 - void constraints() {
7.579 - graph.clear();
7.580 - }
7.581 -
7.582 - _Graph graph;
7.583 - };
7.584 - };
7.585 -
7.586 -
7.587 /// \brief Skeleton class for graph NodeIt and EdgeIt
7.588 ///
7.589 /// Skeleton class for graph NodeIt and EdgeIt.
7.590 @@ -947,7 +795,7 @@
7.591 ///
7.592 /// This class provides beside the core graph features
7.593 /// iterator based iterable interface for the graph structure.
7.594 - /// This concept is part of the GraphConcept.
7.595 + /// This concept is part of the Graph concept.
7.596 template <typename _Base = BaseGraphComponent>
7.597 class IterableGraphComponent : public _Base {
7.598
7.599 @@ -959,6 +807,72 @@
7.600
7.601 typedef IterableGraphComponent Graph;
7.602
7.603 + /// \name Base iteration
7.604 + ///
7.605 + /// This interface provides functions for iteration on graph items
7.606 + ///
7.607 + /// @{
7.608 +
7.609 + /// \brief Gives back the first node in the iterating order.
7.610 + ///
7.611 + /// Gives back the first node in the iterating order.
7.612 + ///
7.613 + void first(Node&) const {}
7.614 +
7.615 + /// \brief Gives back the next node in the iterating order.
7.616 + ///
7.617 + /// Gives back the next node in the iterating order.
7.618 + ///
7.619 + void next(Node&) const {}
7.620 +
7.621 + /// \brief Gives back the first edge in the iterating order.
7.622 + ///
7.623 + /// Gives back the first edge in the iterating order.
7.624 + ///
7.625 + void first(Edge&) const {}
7.626 +
7.627 + /// \brief Gives back the next edge in the iterating order.
7.628 + ///
7.629 + /// Gives back the next edge in the iterating order.
7.630 + ///
7.631 + void next(Edge&) const {}
7.632 +
7.633 +
7.634 + /// \brief Gives back the first of the edges point to the given
7.635 + /// node.
7.636 + ///
7.637 + /// Gives back the first of the edges point to the given node.
7.638 + ///
7.639 + void firstIn(Edge&, const Node&) const {}
7.640 +
7.641 + /// \brief Gives back the next of the edges points to the given
7.642 + /// node.
7.643 + ///
7.644 + /// Gives back the next of the edges points to the given node.
7.645 + ///
7.646 + void nextIn(Edge&) const {}
7.647 +
7.648 + /// \brief Gives back the first of the edges start from the
7.649 + /// given node.
7.650 + ///
7.651 + /// Gives back the first of the edges start from the given node.
7.652 + ///
7.653 + void firstOut(Edge&, const Node&) const {}
7.654 +
7.655 + /// \brief Gives back the next of the edges start from the given
7.656 + /// node.
7.657 + ///
7.658 + /// Gives back the next of the edges start from the given node.
7.659 + ///
7.660 + void nextOut(Edge&) const {}
7.661 +
7.662 + /// @}
7.663 +
7.664 + /// \name Class based iteration
7.665 + ///
7.666 + /// This interface provides functions for iteration on graph items
7.667 + ///
7.668 + /// @{
7.669
7.670 /// \brief This iterator goes through each node.
7.671 ///
7.672 @@ -1008,35 +922,53 @@
7.673 /// It is always the target of the pointed edge.
7.674 Node runningNode(const OutEdgeIt&) const { return INVALID; }
7.675
7.676 - /// \brief The opposite node on the given edge.
7.677 - ///
7.678 - /// Gives back the opposite on the given edge.
7.679 - /// \todo It should not be here.
7.680 - Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
7.681 + /// @}
7.682
7.683 -
7.684 template <typename _Graph>
7.685 struct Constraints {
7.686 void constraints() {
7.687 checkConcept<Base, _Graph>();
7.688 -
7.689 - checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
7.690 - typename _Graph::EdgeIt >();
7.691 - checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
7.692 - typename _Graph::NodeIt >();
7.693 - checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
7.694 - typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
7.695 - checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
7.696 - typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
7.697
7.698 - typename _Graph::Node n;
7.699 - typename _Graph::InEdgeIt ieit(INVALID);
7.700 - typename _Graph::OutEdgeIt oeit(INVALID);
7.701 - n = graph.baseNode(ieit);
7.702 - n = graph.runningNode(ieit);
7.703 - n = graph.baseNode(oeit);
7.704 - n = graph.runningNode(oeit);
7.705 - ignore_unused_variable_warning(n);
7.706 + {
7.707 + typename _Graph::Node node(INVALID);
7.708 + typename _Graph::Edge edge(INVALID);
7.709 + {
7.710 + graph.first(node);
7.711 + graph.next(node);
7.712 + }
7.713 + {
7.714 + graph.first(edge);
7.715 + graph.next(edge);
7.716 + }
7.717 + {
7.718 + graph.firstIn(edge, node);
7.719 + graph.nextIn(edge);
7.720 + }
7.721 + {
7.722 + graph.firstOut(edge, node);
7.723 + graph.nextOut(edge);
7.724 + }
7.725 + }
7.726 +
7.727 + {
7.728 + checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
7.729 + typename _Graph::EdgeIt >();
7.730 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
7.731 + typename _Graph::NodeIt >();
7.732 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
7.733 + typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
7.734 + checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
7.735 + typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
7.736 +
7.737 + typename _Graph::Node n;
7.738 + typename _Graph::InEdgeIt ieit(INVALID);
7.739 + typename _Graph::OutEdgeIt oeit(INVALID);
7.740 + n = graph.baseNode(ieit);
7.741 + n = graph.runningNode(ieit);
7.742 + n = graph.baseNode(oeit);
7.743 + n = graph.runningNode(oeit);
7.744 + ignore_unused_variable_warning(n);
7.745 + }
7.746 }
7.747
7.748 const _Graph& graph;
7.749 @@ -1048,7 +980,7 @@
7.750 ///
7.751 /// This class provides beside the core graph features iterator
7.752 /// based iterable interface for the undirected graph structure.
7.753 - /// This concept is part of the GraphConcept.
7.754 + /// This concept is part of the UGraph concept.
7.755 template <typename _Base = BaseUGraphComponent>
7.756 class IterableUGraphComponent : public IterableGraphComponent<_Base> {
7.757 public:
7.758 @@ -1060,9 +992,57 @@
7.759
7.760
7.761 typedef IterableUGraphComponent Graph;
7.762 +
7.763 + /// \name Base iteration
7.764 + ///
7.765 + /// This interface provides functions for iteration on graph items
7.766 + /// @{
7.767 +
7.768 + using IterableGraphComponent<_Base>::first;
7.769 + using IterableGraphComponent<_Base>::next;
7.770 +
7.771 + /// \brief Gives back the first undirected edge in the iterating
7.772 + /// order.
7.773 + ///
7.774 + /// Gives back the first undirected edge in the iterating order.
7.775 + ///
7.776 + void first(UEdge&) const {}
7.777 +
7.778 + /// \brief Gives back the next undirected edge in the iterating
7.779 + /// order.
7.780 + ///
7.781 + /// Gives back the next undirected edge in the iterating order.
7.782 + ///
7.783 + void next(UEdge&) const {}
7.784 +
7.785 +
7.786 + /// \brief Gives back the first of the undirected edges from the
7.787 + /// given node.
7.788 + ///
7.789 + /// Gives back the first of the undirected edges from the given
7.790 + /// node. The bool parameter gives back that direction which
7.791 + /// gives a good direction of the uedge so the source of the
7.792 + /// directed edge is the given node.
7.793 + void firstInc(UEdge&, bool&, const Node&) const {}
7.794 +
7.795 + /// \brief Gives back the next of the undirected edges from the
7.796 + /// given node.
7.797 + ///
7.798 + /// Gives back the next of the undirected edges from the given
7.799 + /// node. The bool parameter should be used as the \c firstInc()
7.800 + /// use it.
7.801 + void nextInc(UEdge&, bool&) const {}
7.802 +
7.803 using IterableGraphComponent<_Base>::baseNode;
7.804 using IterableGraphComponent<_Base>::runningNode;
7.805
7.806 + /// @}
7.807 +
7.808 + /// \name Class based iteration
7.809 + ///
7.810 + /// This interface provides functions for iteration on graph items
7.811 + ///
7.812 + /// @{
7.813
7.814 /// \brief This iterator goes through each node.
7.815 ///
7.816 @@ -1084,21 +1064,170 @@
7.817 /// Gives back the running node of the iterator.
7.818 Node runningNode(const IncEdgeIt&) const { return INVALID; }
7.819
7.820 + /// @}
7.821 +
7.822 template <typename _Graph>
7.823 struct Constraints {
7.824 void constraints() {
7.825 - checkConcept<Base, _Graph>();
7.826 checkConcept<IterableGraphComponent<Base>, _Graph>();
7.827 -
7.828 - checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
7.829 - typename _Graph::UEdgeIt >();
7.830 - checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
7.831 - typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
7.832
7.833 - typename _Graph::Node n;
7.834 - typename _Graph::IncEdgeIt ueit(INVALID);
7.835 - n = graph.baseNode(ueit);
7.836 - n = graph.runningNode(ueit);
7.837 + {
7.838 + typename _Graph::Node node(INVALID);
7.839 + typename _Graph::UEdge uedge(INVALID);
7.840 + bool dir;
7.841 + {
7.842 + graph.first(uedge);
7.843 + graph.next(uedge);
7.844 + }
7.845 + {
7.846 + graph.firstInc(uedge, dir, node);
7.847 + graph.nextInc(uedge, dir);
7.848 + }
7.849 +
7.850 + }
7.851 +
7.852 + {
7.853 + checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
7.854 + typename _Graph::UEdgeIt >();
7.855 + checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
7.856 + typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
7.857 +
7.858 + typename _Graph::Node n;
7.859 + typename _Graph::IncEdgeIt ueit(INVALID);
7.860 + n = graph.baseNode(ueit);
7.861 + n = graph.runningNode(ueit);
7.862 + }
7.863 + }
7.864 +
7.865 + const _Graph& graph;
7.866 +
7.867 + };
7.868 + };
7.869 +
7.870 + /// \brief An empty iterable bipartite undirected graph class.
7.871 + ///
7.872 + /// This class provides beside the core graph features iterator
7.873 + /// based iterable interface for the bipartite undirected graph
7.874 + /// structure. This concept is part of the BpUGraph concept.
7.875 + template <typename _Base = BaseUGraphComponent>
7.876 + class IterableBpUGraphComponent : public IterableUGraphComponent<_Base> {
7.877 + public:
7.878 +
7.879 + typedef _Base Base;
7.880 + typedef typename Base::Node Node;
7.881 + typedef typename Base::UEdge UEdge;
7.882 +
7.883 + typedef IterableBpUGraphComponent Graph;
7.884 +
7.885 + /// \name Base iteration
7.886 + ///
7.887 + /// This interface provides functions for iteration on graph items
7.888 + /// @{
7.889 +
7.890 + using IterableUGraphComponent<_Base>::first;
7.891 + using IterableUGraphComponent<_Base>::next;
7.892 +
7.893 + /// \brief Gives back the first A-node in the iterating order.
7.894 + ///
7.895 + /// Gives back the first undirected A-node in the iterating
7.896 + /// order.
7.897 + ///
7.898 + void firstANode(Node&) const {}
7.899 +
7.900 + /// \brief Gives back the next A-node in the iterating order.
7.901 + ///
7.902 + /// Gives back the next A-node in the iterating order.
7.903 + ///
7.904 + void nextANode(Node&) const {}
7.905 +
7.906 + /// \brief Gives back the first B-node in the iterating order.
7.907 + ///
7.908 + /// Gives back the first undirected B-node in the iterating
7.909 + /// order.
7.910 + ///
7.911 + void firstBNode(Node&) const {}
7.912 +
7.913 + /// \brief Gives back the next B-node in the iterating order.
7.914 + ///
7.915 + /// Gives back the next B-node in the iterating order.
7.916 + ///
7.917 + void nextBNode(Node&) const {}
7.918 +
7.919 +
7.920 + /// \brief Gives back the first of the undirected edges start
7.921 + /// from the given A-node.
7.922 + ///
7.923 + /// Gives back the first of the undirected edges start from the
7.924 + /// given A-node.
7.925 + void firstFromANode(UEdge&, const Node&) const {}
7.926 +
7.927 + /// \brief Gives back the next of the undirected edges start
7.928 + /// from the given A-node.
7.929 + ///
7.930 + /// Gives back the next of the undirected edges start from the
7.931 + /// given A-node.
7.932 + void nextFromANode(UEdge&) const {}
7.933 +
7.934 + /// \brief Gives back the first of the undirected edges start
7.935 + /// from the given B-node.
7.936 + ///
7.937 + /// Gives back the first of the undirected edges start from the
7.938 + /// given B-node.
7.939 + void firstFromBNode(UEdge&, const Node&) const {}
7.940 +
7.941 + /// \brief Gives back the next of the undirected edges start
7.942 + /// from the given B-node.
7.943 + ///
7.944 + /// Gives back the next of the undirected edges start from the
7.945 + /// given B-node.
7.946 + void nextFromBNode(UEdge&) const {}
7.947 +
7.948 +
7.949 + /// @}
7.950 +
7.951 + /// \name Class based iteration
7.952 + ///
7.953 + /// This interface provides functions for iteration on graph items
7.954 + ///
7.955 + /// @{
7.956 +
7.957 + /// \brief This iterator goes through each A-node.
7.958 + ///
7.959 + /// This iterator goes through each A-node.
7.960 + typedef GraphItemIt<Graph, Node> ANodeIt;
7.961 +
7.962 + /// \brief This iterator goes through each B-node.
7.963 + ///
7.964 + /// This iterator goes through each B-node.
7.965 + typedef GraphItemIt<Graph, Node> BNodeIt;
7.966 +
7.967 + /// @}
7.968 +
7.969 + template <typename _Graph>
7.970 + struct Constraints {
7.971 + void constraints() {
7.972 + checkConcept<IterableUGraphComponent<Base>, _Graph>();
7.973 +
7.974 + {
7.975 + typename _Graph::Node node(INVALID);
7.976 + typename _Graph::UEdge uedge(INVALID);
7.977 + graph.firstANode(node);
7.978 + graph.nextANode(node);
7.979 + graph.firstBNode(node);
7.980 + graph.nextBNode(node);
7.981 +
7.982 + graph.firstFromANode(uedge, node);
7.983 + graph.nextFromANode(uedge);
7.984 + graph.firstFromBNode(uedge, node);
7.985 + graph.nextFromBNode(uedge);
7.986 + }
7.987 + {
7.988 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
7.989 + typename _Graph::ANodeIt >();
7.990 + checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
7.991 + typename _Graph::BNodeIt >();
7.992 + }
7.993 +
7.994 }
7.995
7.996 const _Graph& graph;
7.997 @@ -1194,8 +1323,7 @@
7.998 template <typename _Graph>
7.999 struct Constraints {
7.1000 void constraints() {
7.1001 - checkConcept<Base, _Graph>();
7.1002 - checkConcept<AlterableGraphComponent, _Graph>();
7.1003 + checkConcept<AlterableGraphComponent<Base>, _Graph>();
7.1004 typename _Graph::UEdgeNotifier& uen
7.1005 = graph.getNotifier(typename _Graph::UEdge());
7.1006 ignore_unused_variable_warning(uen);
7.1007 @@ -1207,6 +1335,64 @@
7.1008
7.1009 };
7.1010
7.1011 + /// \brief An empty alteration notifier bipartite undirected graph
7.1012 + /// class.
7.1013 + ///
7.1014 + /// This class provides beside the core graph features alteration
7.1015 + /// notifier interface for the graph structure. This implements
7.1016 + /// an observer-notifier pattern for each graph item. More
7.1017 + /// obsevers can be registered into the notifier and whenever an
7.1018 + /// alteration occured in the graph all the observers will
7.1019 + /// notified about it.
7.1020 + template <typename _Base = BaseUGraphComponent>
7.1021 + class AlterableBpUGraphComponent : public AlterableUGraphComponent<_Base> {
7.1022 + public:
7.1023 +
7.1024 + typedef _Base Base;
7.1025 + typedef typename Base::ANode ANode;
7.1026 + typedef typename Base::BNode BNode;
7.1027 +
7.1028 +
7.1029 + /// The A-node observer registry.
7.1030 + typedef AlterationNotifier<AlterableBpUGraphComponent, ANode>
7.1031 + ANodeNotifier;
7.1032 +
7.1033 + /// The B-node observer registry.
7.1034 + typedef AlterationNotifier<AlterableBpUGraphComponent, BNode>
7.1035 + BNodeNotifier;
7.1036 +
7.1037 + /// \brief Gives back the A-node alteration notifier.
7.1038 + ///
7.1039 + /// Gives back the A-node alteration notifier.
7.1040 + ANodeNotifier& getNotifier(ANode) const {
7.1041 + return ANodeNotifier();
7.1042 + }
7.1043 +
7.1044 + /// \brief Gives back the B-node alteration notifier.
7.1045 + ///
7.1046 + /// Gives back the B-node alteration notifier.
7.1047 + BNodeNotifier& getNotifier(BNode) const {
7.1048 + return BNodeNotifier();
7.1049 + }
7.1050 +
7.1051 + template <typename _Graph>
7.1052 + struct Constraints {
7.1053 + void constraints() {
7.1054 + checkConcept<AlterableUGraphComponent<Base>, _Graph>();
7.1055 + typename _Graph::ANodeNotifier& ann
7.1056 + = graph.getNotifier(typename _Graph::ANode());
7.1057 + typename _Graph::BNodeNotifier& bnn
7.1058 + = graph.getNotifier(typename _Graph::BNode());
7.1059 + ignore_unused_variable_warning(ann);
7.1060 + ignore_unused_variable_warning(bnn);
7.1061 + }
7.1062 +
7.1063 + const _Graph& graph;
7.1064 +
7.1065 + };
7.1066 +
7.1067 + };
7.1068 +
7.1069
7.1070 /// \brief Class describing the concept of graph maps
7.1071 ///
7.1072 @@ -1415,7 +1601,7 @@
7.1073 };
7.1074 };
7.1075
7.1076 - /// \brief An empty mappable base graph class.
7.1077 + /// \brief An empty mappable base bipartite undirected graph class.
7.1078 ///
7.1079 /// This class provides beside the core graph features
7.1080 /// map interface for the graph structure.
7.1081 @@ -1478,7 +1664,6 @@
7.1082 };
7.1083
7.1084 void constraints() {
7.1085 - checkConcept<Base, _Graph>();
7.1086 checkConcept<MappableGraphComponent<Base>, _Graph>();
7.1087
7.1088 { // int map test
7.1089 @@ -1500,6 +1685,129 @@
7.1090 };
7.1091 };
7.1092
7.1093 + /// \brief An empty mappable base bipartite undirected graph
7.1094 + /// class.
7.1095 + ///
7.1096 + /// This class provides beside the core graph features
7.1097 + /// map interface for the graph structure.
7.1098 + /// This concept is part of the BpUGraph concept.
7.1099 + template <typename _Base = BaseBpUGraphComponent>
7.1100 + class MappableBpUGraphComponent : public MappableUGraphComponent<_Base> {
7.1101 + public:
7.1102 +
7.1103 + typedef _Base Base;
7.1104 + typedef typename Base::Node Node;
7.1105 +
7.1106 + typedef MappableBpUGraphComponent Graph;
7.1107 +
7.1108 + /// \brief ReadWrite map of the A-nodes.
7.1109 + ///
7.1110 + /// ReadWrite map of the A-nodes.
7.1111 + ///
7.1112 + template <typename _Value>
7.1113 + class ANodeMap : public GraphMap<Graph, Node, _Value> {
7.1114 + public:
7.1115 + typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
7.1116 +
7.1117 + /// \brief Construct a new map.
7.1118 + ///
7.1119 + /// Construct a new map for the graph.
7.1120 + /// \todo call the right parent class constructor
7.1121 + explicit ANodeMap(const MappableBpUGraphComponent& graph)
7.1122 + : Parent(graph) {}
7.1123 +
7.1124 + /// \brief Construct a new map with default value.
7.1125 + ///
7.1126 + /// Construct a new map for the graph and initalise the values.
7.1127 + ANodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
7.1128 + : Parent(graph, value) {}
7.1129 +
7.1130 + /// \brief Copy constructor.
7.1131 + ///
7.1132 + /// Copy Constructor.
7.1133 + ANodeMap(const ANodeMap& nm) : Parent(nm) {}
7.1134 +
7.1135 + /// \brief Assign operator.
7.1136 + ///
7.1137 + /// Assign operator.
7.1138 + template <typename CMap>
7.1139 + ANodeMap& operator=(const CMap&) {
7.1140 + checkConcept<ReadMap<Node, _Value>, CMap>();
7.1141 + return *this;
7.1142 + }
7.1143 +
7.1144 + };
7.1145 +
7.1146 + /// \brief ReadWrite map of the B-nodes.
7.1147 + ///
7.1148 + /// ReadWrite map of the A-nodes.
7.1149 + ///
7.1150 + template <typename _Value>
7.1151 + class BNodeMap : public GraphMap<Graph, Node, _Value> {
7.1152 + public:
7.1153 + typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
7.1154 +
7.1155 + /// \brief Construct a new map.
7.1156 + ///
7.1157 + /// Construct a new map for the graph.
7.1158 + /// \todo call the right parent class constructor
7.1159 + explicit BNodeMap(const MappableBpUGraphComponent& graph)
7.1160 + : Parent(graph) {}
7.1161 +
7.1162 + /// \brief Construct a new map with default value.
7.1163 + ///
7.1164 + /// Construct a new map for the graph and initalise the values.
7.1165 + BNodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
7.1166 + : Parent(graph, value) {}
7.1167 +
7.1168 + /// \brief Copy constructor.
7.1169 + ///
7.1170 + /// Copy Constructor.
7.1171 + BNodeMap(const BNodeMap& nm) : Parent(nm) {}
7.1172 +
7.1173 + /// \brief Assign operator.
7.1174 + ///
7.1175 + /// Assign operator.
7.1176 + template <typename CMap>
7.1177 + BNodeMap& operator=(const CMap&) {
7.1178 + checkConcept<ReadMap<Node, _Value>, CMap>();
7.1179 + return *this;
7.1180 + }
7.1181 +
7.1182 + };
7.1183 +
7.1184 +
7.1185 + template <typename _Graph>
7.1186 + struct Constraints {
7.1187 +
7.1188 + struct Dummy {
7.1189 + int value;
7.1190 + Dummy() : value(0) {}
7.1191 + Dummy(int _v) : value(_v) {}
7.1192 + };
7.1193 +
7.1194 + void constraints() {
7.1195 + checkConcept<MappableUGraphComponent<Base>, _Graph>();
7.1196 +
7.1197 + { // int map test
7.1198 + typedef typename _Graph::template ANodeMap<int> IntANodeMap;
7.1199 + checkConcept<GraphMap<_Graph, typename _Graph::ANode, int>,
7.1200 + IntANodeMap >();
7.1201 + } { // bool map test
7.1202 + typedef typename _Graph::template ANodeMap<bool> BoolANodeMap;
7.1203 + checkConcept<GraphMap<_Graph, typename _Graph::ANode, bool>,
7.1204 + BoolANodeMap >();
7.1205 + } { // Dummy map test
7.1206 + typedef typename _Graph::template ANodeMap<Dummy> DummyANodeMap;
7.1207 + checkConcept<GraphMap<_Graph, typename _Graph::ANode, Dummy>,
7.1208 + DummyANodeMap >();
7.1209 + }
7.1210 + }
7.1211 +
7.1212 + _Graph& graph;
7.1213 + };
7.1214 + };
7.1215 +
7.1216
7.1217 /// \brief An empty extendable graph class.
7.1218 ///
7.1219 @@ -1510,6 +1818,7 @@
7.1220 template <typename _Base = BaseGraphComponent>
7.1221 class ExtendableGraphComponent : public _Base {
7.1222 public:
7.1223 + typedef _Base Base;
7.1224
7.1225 typedef typename _Base::Node Node;
7.1226 typedef typename _Base::Edge Edge;
7.1227 @@ -1532,6 +1841,7 @@
7.1228 template <typename _Graph>
7.1229 struct Constraints {
7.1230 void constraints() {
7.1231 + checkConcept<Base, _Graph>();
7.1232 typename _Graph::Node node_a, node_b;
7.1233 node_a = graph.addNode();
7.1234 node_b = graph.addNode();
7.1235 @@ -1554,6 +1864,7 @@
7.1236 class ExtendableUGraphComponent : public _Base {
7.1237 public:
7.1238
7.1239 + typedef _Base Base;
7.1240 typedef typename _Base::Node Node;
7.1241 typedef typename _Base::UEdge UEdge;
7.1242
7.1243 @@ -1575,6 +1886,7 @@
7.1244 template <typename _Graph>
7.1245 struct Constraints {
7.1246 void constraints() {
7.1247 + checkConcept<Base, _Graph>();
7.1248 typename _Graph::Node node_a, node_b;
7.1249 node_a = graph.addNode();
7.1250 node_b = graph.addNode();
7.1251 @@ -1586,6 +1898,27 @@
7.1252 };
7.1253 };
7.1254
7.1255 + /// \brief An empty extendable base undirected graph class.
7.1256 + ///
7.1257 + /// This class provides beside the core bipartite undirected graph
7.1258 + /// features core undircted graph extend interface for the graph
7.1259 + /// structure. The main difference between the base and this
7.1260 + /// interface is that the graph alterations should handled already
7.1261 + /// on this level.
7.1262 + template <typename _Base = BaseBpUGraphComponent>
7.1263 + class ExtendableBpUGraphComponent
7.1264 + : public ExtendableUGraphComponent<_Base> {
7.1265 +
7.1266 + typedef _Base Base;
7.1267 +
7.1268 + template <typename _Graph>
7.1269 + struct Constraints {
7.1270 + void constraints() {
7.1271 + checkConcept<ExtendableUGraphComponent<Base>, _Graph>();
7.1272 + }
7.1273 + };
7.1274 + };
7.1275 +
7.1276 /// \brief An empty erasable graph class.
7.1277 ///
7.1278 /// This class provides beside the core graph features core erase
7.1279 @@ -1615,6 +1948,7 @@
7.1280 template <typename _Graph>
7.1281 struct Constraints {
7.1282 void constraints() {
7.1283 + checkConcept<Base, _Graph>();
7.1284 typename _Graph::Node node;
7.1285 graph.erase(node);
7.1286 typename _Graph::Edge edge;
7.1287 @@ -1654,6 +1988,7 @@
7.1288 template <typename _Graph>
7.1289 struct Constraints {
7.1290 void constraints() {
7.1291 + checkConcept<Base, _Graph>();
7.1292 typename _Graph::Node node;
7.1293 graph.erase(node);
7.1294 typename _Graph::Edge edge;
7.1295 @@ -1664,6 +1999,27 @@
7.1296 };
7.1297 };
7.1298
7.1299 + /// \brief An empty erasable base bipartite undirected graph class.
7.1300 + ///
7.1301 + /// This class provides beside the core bipartite undirected graph
7.1302 + /// features core erase functions for the undirceted graph
7.1303 + /// structure. The main difference between the base and this
7.1304 + /// interface is that the graph alterations should handled already
7.1305 + /// on this level.
7.1306 + template <typename _Base = BaseBpUGraphComponent>
7.1307 + class ErasableBpUGraphComponent : public ErasableUGraphComponent<_Base> {
7.1308 + public:
7.1309 +
7.1310 + typedef _Base Base;
7.1311 +
7.1312 + template <typename _Graph>
7.1313 + struct Constraints {
7.1314 + void constraints() {
7.1315 + checkConcept<ErasableUGraphComponent<Base>, _Graph>();
7.1316 + }
7.1317 + };
7.1318 + };
7.1319 +
7.1320 /// \brief An empty clearable base graph class.
7.1321 ///
7.1322 /// This class provides beside the core graph features core clear
7.1323 @@ -1674,6 +2030,8 @@
7.1324 class ClearableGraphComponent : public _Base {
7.1325 public:
7.1326
7.1327 + typedef _Base Base;
7.1328 +
7.1329 /// \brief Erase all nodes and edges from the graph.
7.1330 ///
7.1331 /// Erase all nodes and edges from the graph.
7.1332 @@ -1683,6 +2041,7 @@
7.1333 template <typename _Graph>
7.1334 struct Constraints {
7.1335 void constraints() {
7.1336 + checkConcept<Base, _Graph>();
7.1337 graph.clear();
7.1338 }
7.1339
7.1340 @@ -1697,25 +2056,46 @@
7.1341 /// main difference between the base and this interface is that
7.1342 /// the graph alterations should handled already on this level.
7.1343 template <typename _Base = BaseUGraphComponent>
7.1344 - class ClearableUGraphComponent : public _Base {
7.1345 + class ClearableUGraphComponent : public ClearableUGraphComponent<_Base> {
7.1346 public:
7.1347
7.1348 - /// \brief Erase all nodes and undirected edges from the graph.
7.1349 - ///
7.1350 - /// Erase all nodes and undirected edges from the graph.
7.1351 - ///
7.1352 - void clear() {}
7.1353 + typedef _Base Base;
7.1354
7.1355 template <typename _Graph>
7.1356 struct Constraints {
7.1357 void constraints() {
7.1358 - graph.clear();
7.1359 + checkConcept<ClearableUGraphComponent<Base>, _Graph>();
7.1360 }
7.1361
7.1362 _Graph graph;
7.1363 };
7.1364 };
7.1365
7.1366 + /// \brief An empty clearable base bipartite undirected graph
7.1367 + /// class.
7.1368 + ///
7.1369 + /// This class provides beside the core bipartite undirected graph
7.1370 + /// features core clear functions for the undirected graph
7.1371 + /// structure. The main difference between the base and this
7.1372 + /// interface is that the graph alterations should handled already
7.1373 + /// on this level.
7.1374 + template <typename _Base = BaseUGraphComponent>
7.1375 + class ClearableBpUGraphComponent
7.1376 + : public ClearableBpUGraphComponent<_Base> {
7.1377 + public:
7.1378 +
7.1379 + typedef _Base Base;
7.1380 +
7.1381 + template <typename _Graph>
7.1382 + struct Constraints {
7.1383 + void constraints() {
7.1384 + checkConcept<ClearableBpUGraphComponent<Base>, _Graph>();
7.1385 + }
7.1386 +
7.1387 + };
7.1388 +
7.1389 + };
7.1390 +
7.1391 }
7.1392
7.1393 }
8.1 --- a/lemon/concept/ugraph.h Tue Oct 03 11:24:41 2006 +0000
8.2 +++ b/lemon/concept/ugraph.h Tue Oct 03 11:46:39 2006 +0000
8.3 @@ -697,7 +697,6 @@
8.4 template <typename Graph>
8.5 struct Constraints {
8.6 void constraints() {
8.7 - checkConcept<BaseIterableUGraphComponent<>, Graph>();
8.8 checkConcept<IterableUGraphComponent<>, Graph>();
8.9 checkConcept<MappableUGraphComponent<>, Graph>();
8.10 }
9.1 --- a/lemon/full_graph.h Tue Oct 03 11:24:41 2006 +0000
9.2 +++ b/lemon/full_graph.h Tue Oct 03 11:46:39 2006 +0000
9.3 @@ -609,7 +609,7 @@
9.4 static int aNodeId(const Node& node) {
9.5 return node.id >> 1;
9.6 }
9.7 - static Node fromANodeId(int id) {
9.8 + static Node nodeFromANodeId(int id) {
9.9 return Node(id << 1);
9.10 }
9.11 int maxANodeId() const {
9.12 @@ -619,7 +619,7 @@
9.13 static int bNodeId(const Node& node) {
9.14 return node.id >> 1;
9.15 }
9.16 - static Node fromBNodeId(int id) {
9.17 + static Node nodeFromBNodeId(int id) {
9.18 return Node((id << 1) + 1);
9.19 }
9.20 int maxBNodeId() const {
9.21 @@ -665,7 +665,8 @@
9.22 };
9.23
9.24
9.25 - typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
9.26 + typedef BpUGraphExtender<BidirBpUGraphExtender<FullBpUGraphBase> >
9.27 + ExtendedFullBpUGraphBase;
9.28
9.29
9.30 /// \ingroup graphs
10.1 --- a/lemon/list_graph.h Tue Oct 03 11:24:41 2006 +0000
10.2 +++ b/lemon/list_graph.h Tue Oct 03 11:46:39 2006 +0000
10.3 @@ -1270,7 +1270,7 @@
10.4 static int aNodeId(const Node& node) {
10.5 return node.id >> 1;
10.6 }
10.7 - static Node fromANodeId(int id) {
10.8 + static Node nodeFromANodeId(int id) {
10.9 return Node(id << 1);
10.10 }
10.11 int maxANodeId() const {
10.12 @@ -1280,7 +1280,7 @@
10.13 static int bNodeId(const Node& node) {
10.14 return node.id >> 1;
10.15 }
10.16 - static Node fromBNodeId(int id) {
10.17 + static Node nodeFromBNodeId(int id) {
10.18 return Node((id << 1) + 1);
10.19 }
10.20 int maxBNodeId() const {
10.21 @@ -1482,7 +1482,8 @@
10.22 };
10.23
10.24
10.25 - typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
10.26 + typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
10.27 + ExtendedListBpUGraphBase;
10.28
10.29 /// \ingroup graphs
10.30 ///
11.1 --- a/lemon/smart_graph.h Tue Oct 03 11:24:41 2006 +0000
11.2 +++ b/lemon/smart_graph.h Tue Oct 03 11:46:39 2006 +0000
11.3 @@ -662,7 +662,7 @@
11.4 static int aNodeId(const Node& node) {
11.5 return node.id >> 1;
11.6 }
11.7 - static Node fromANodeId(int id) {
11.8 + static Node nodeFromANodeId(int id) {
11.9 return Node(id << 1);
11.10 }
11.11 int maxANodeId() const {
11.12 @@ -672,7 +672,7 @@
11.13 static int bNodeId(const Node& node) {
11.14 return node.id >> 1;
11.15 }
11.16 - static Node fromBNodeId(int id) {
11.17 + static Node nodeFromBNodeId(int id) {
11.18 return Node((id << 1) + 1);
11.19 }
11.20 int maxBNodeId() const {
11.21 @@ -743,7 +743,8 @@
11.22 };
11.23
11.24
11.25 - typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
11.26 + typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> >
11.27 + ExtendedSmartBpUGraphBase;
11.28
11.29 /// \ingroup graphs
11.30 ///
11.31 @@ -829,13 +830,13 @@
11.32 edges.pop_back();
11.33 }
11.34 while(s.anode_num<aNodes.size()) {
11.35 - Node node = fromANodeId(aNodes.size() - 1);
11.36 + Node node = nodeFromANodeId(aNodes.size() - 1);
11.37 Parent::getNotifier(ANode()).erase(node);
11.38 Parent::getNotifier(Node()).erase(node);
11.39 aNodes.pop_back();
11.40 }
11.41 while(s.bnode_num<bNodes.size()) {
11.42 - Node node = fromBNodeId(bNodes.size() - 1);
11.43 + Node node = nodeFromBNodeId(bNodes.size() - 1);
11.44 Parent::getNotifier(BNode()).erase(node);
11.45 Parent::getNotifier(Node()).erase(node);
11.46 bNodes.pop_back();
12.1 --- a/test/Makefile.am Tue Oct 03 11:24:41 2006 +0000
12.2 +++ b/test/Makefile.am Tue Oct 03 11:46:39 2006 +0000
12.3 @@ -15,6 +15,7 @@
12.4 test/arborescence_test \
12.5 test/bfs_test \
12.6 test/bipartite_matching_test \
12.7 + test/bpugraph_test \
12.8 test/counter_test \
12.9 test/dfs_test \
12.10 test/dijkstra_test \
12.11 @@ -57,6 +58,7 @@
12.12 test_arborescence_test_SOURCES = test/arborescence_test.cc
12.13 test_bfs_test_SOURCES = test/bfs_test.cc
12.14 test_bipartite_matching_test_SOURCES = test/bipartite_matching_test.cc
12.15 +test_bpugraph_test_SOURCES = test/bpugraph_test.cc
12.16 test_counter_test_SOURCES = test/counter_test.cc
12.17 test_dfs_test_SOURCES = test/dfs_test.cc
12.18 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/test/bpugraph_test.cc Tue Oct 03 11:46:39 2006 +0000
13.3 @@ -0,0 +1,146 @@
13.4 +/* -*- C++ -*-
13.5 + *
13.6 + * This file is a part of LEMON, a generic C++ optimization library
13.7 + *
13.8 + * Copyright (C) 2003-2006
13.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
13.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
13.11 + *
13.12 + * Permission to use, modify and distribute this software is granted
13.13 + * provided that this copyright notice appears in all copies. For
13.14 + * precise terms see the accompanying LICENSE file.
13.15 + *
13.16 + * This software is provided "AS IS" with no warranty of any kind,
13.17 + * express or implied, and with no claim as to its suitability for any
13.18 + * purpose.
13.19 + *
13.20 + */
13.21 +
13.22 +#include <lemon/concept/bpugraph.h>
13.23 +#include <lemon/list_graph.h>
13.24 +#include <lemon/smart_graph.h>
13.25 +#include <lemon/full_graph.h>
13.26 +#include <lemon/grid_ugraph.h>
13.27 +
13.28 +#include <lemon/graph_utils.h>
13.29 +
13.30 +#include "test_tools.h"
13.31 +
13.32 +
13.33 +using namespace lemon;
13.34 +using namespace lemon::concept;
13.35 +
13.36 +void check_concepts() {
13.37 +
13.38 + { // checking graph components
13.39 + checkConcept<BaseBpUGraphComponent, BaseBpUGraphComponent >();
13.40 +
13.41 + checkConcept<IDableBpUGraphComponent<>,
13.42 + IDableBpUGraphComponent<> >();
13.43 +
13.44 + checkConcept<IterableBpUGraphComponent<>,
13.45 + IterableBpUGraphComponent<> >();
13.46 +
13.47 + checkConcept<MappableBpUGraphComponent<>,
13.48 + MappableBpUGraphComponent<> >();
13.49 +
13.50 + }
13.51 + {
13.52 + checkConcept<BpUGraph, ListBpUGraph>();
13.53 +
13.54 + checkConcept<BpUGraph, SmartBpUGraph>();
13.55 +
13.56 + checkConcept<BpUGraph, FullBpUGraph>();
13.57 +
13.58 + checkConcept<BpUGraph, BpUGraph>();
13.59 +
13.60 + }
13.61 +}
13.62 +
13.63 +template <typename Graph>
13.64 +void check_item_counts(Graph &g, int an, int bn, int e) {
13.65 + int nn = 0;
13.66 + for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
13.67 + ++nn;
13.68 + }
13.69 +
13.70 + check(nn == an + bn, "Wrong node number.");
13.71 + check(countNodes(g) == an + bn, "Wrong node number.");
13.72 +
13.73 + int ann = 0;
13.74 + for (typename Graph::ANodeIt it(g); it != INVALID; ++it) {
13.75 + ++ann;
13.76 + }
13.77 +
13.78 + check(ann == an, "Wrong node number.");
13.79 + check(countANodes(g) == an, "Wrong node number.");
13.80 +
13.81 + int bnn = 0;
13.82 + for (typename Graph::BNodeIt it(g); it != INVALID; ++it) {
13.83 + ++bnn;
13.84 + }
13.85 +
13.86 + check(bnn == bn, "Wrong node number.");
13.87 + check(countBNodes(g) == bn, "Wrong node number.");
13.88 +
13.89 + int ee = 0;
13.90 + for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
13.91 + ++ee;
13.92 + }
13.93 +
13.94 + check(ee == 2*e, "Wrong edge number.");
13.95 + check(countEdges(g) == 2*e, "Wrong edge number.");
13.96 +
13.97 + int uee = 0;
13.98 + for (typename Graph::UEdgeIt it(g); it != INVALID; ++it) {
13.99 + ++uee;
13.100 + }
13.101 +
13.102 + check(uee == e, "Wrong uedge number.");
13.103 + check(countUEdges(g) == e, "Wrong uedge number.");
13.104 +}
13.105 +
13.106 +template <typename Graph>
13.107 +void check_graph() {
13.108 +
13.109 + typedef typename Graph::Node Node;
13.110 + typedef typename Graph::UEdge UEdge;
13.111 + typedef typename Graph::Edge Edge;
13.112 + typedef typename Graph::NodeIt NodeIt;
13.113 + typedef typename Graph::UEdgeIt UEdgeIt;
13.114 + typedef typename Graph::EdgeIt EdgeIt;
13.115 +
13.116 + Graph g;
13.117 +
13.118 + check_item_counts(g, 0, 0, 0);
13.119 +
13.120 + Node
13.121 + an1 = g.addANode(),
13.122 + an2 = g.addANode(),
13.123 + an3 = g.addANode(),
13.124 + bn1 = g.addBNode(),
13.125 + bn2 = g.addBNode();
13.126 +
13.127 + UEdge
13.128 + e1 = g.addEdge(an1, bn1),
13.129 + e2 = g.addEdge(an2, bn1),
13.130 + e3 = g.addEdge(an3, bn2);
13.131 +
13.132 + check_item_counts(g, 3, 2, 3);
13.133 +}
13.134 +
13.135 +int main() {
13.136 + check_concepts();
13.137 +
13.138 + check_graph<ListBpUGraph>();
13.139 + check_graph<SmartBpUGraph>();
13.140 +
13.141 + {
13.142 + FullBpUGraph g(5, 10);
13.143 + check_item_counts(g, 5, 10, 50);
13.144 + }
13.145 +
13.146 + std::cout << __FILE__ ": All tests passed.\n";
13.147 +
13.148 + return 0;
13.149 +}
14.1 --- a/test/graph_adaptor_test.cc Tue Oct 03 11:24:41 2006 +0000
14.2 +++ b/test/graph_adaptor_test.cc Tue Oct 03 11:46:39 2006 +0000
14.3 @@ -22,11 +22,13 @@
14.4 #include<lemon/smart_graph.h>
14.5 #include<lemon/concept/graph.h>
14.6 #include<lemon/concept/ugraph.h>
14.7 +#include<lemon/concept/bpugraph.h>
14.8
14.9 #include<lemon/list_graph.h>
14.10 #include<lemon/full_graph.h>
14.11 #include<lemon/graph_adaptor.h>
14.12 #include<lemon/ugraph_adaptor.h>
14.13 +#include<lemon/bpugraph_adaptor.h>
14.14
14.15 #include"test/test_tools.h"
14.16 #include"test/graph_test.h"
14.17 @@ -75,6 +77,11 @@
14.18
14.19 checkConcept<Graph, DirUGraphAdaptor<UGraph,
14.20 UGraph::UEdgeMap<bool> > >();
14.21 +
14.22 + checkConcept<BpUGraph, BpUGraphAdaptor<BpUGraph> >();
14.23 +
14.24 + checkConcept<BpUGraph, SwapBpUGraphAdaptor<BpUGraph> >();
14.25 +
14.26 }
14.27 std::cout << __FILE__ ": All tests passed.\n";
14.28
15.1 --- a/test/graph_test.cc Tue Oct 03 11:24:41 2006 +0000
15.2 +++ b/test/graph_test.cc Tue Oct 03 11:46:39 2006 +0000
15.3 @@ -38,9 +38,6 @@
15.4 { // checking graph components
15.5 checkConcept<BaseGraphComponent, BaseGraphComponent >();
15.6
15.7 - checkConcept<BaseIterableGraphComponent<>,
15.8 - BaseIterableGraphComponent<> >();
15.9 -
15.10 checkConcept<IDableGraphComponent<>,
15.11 IDableGraphComponent<> >();
15.12
16.1 --- a/test/ugraph_test.cc Tue Oct 03 11:24:41 2006 +0000
16.2 +++ b/test/ugraph_test.cc Tue Oct 03 11:46:39 2006 +0000
16.3 @@ -36,9 +36,6 @@
16.4 { // checking graph components
16.5 checkConcept<BaseUGraphComponent, BaseUGraphComponent >();
16.6
16.7 - checkConcept<BaseIterableUGraphComponent<>,
16.8 - BaseIterableUGraphComponent<> >();
16.9 -
16.10 checkConcept<IDableUGraphComponent<>,
16.11 IDableUGraphComponent<> >();
16.12