38 template <class _Graph2> |
38 template <class _Graph2> |
39 class P2 : public GraphWrapperBase<_Graph2> { |
39 class P2 : public GraphWrapperBase<_Graph2> { |
40 }; |
40 }; |
41 |
41 |
42 |
42 |
43 /*! A graph wrapper base class |
|
44 for merging the node-set of two node-disjoint graphs |
|
45 into the node-set of one graph. |
|
46 Generic implementation for unrelated _Graph1::Node and _Graph2::Node. |
|
47 */ |
|
48 template <typename _Graph1, typename _Graph2, typename Enable=void> |
43 template <typename _Graph1, typename _Graph2, typename Enable=void> |
49 class MergeNodeGraphWrapperBase : |
44 class MergeNodeGraphWrapperBaseBase : |
50 public P1<_Graph1>, public P2<_Graph2> { |
45 public P1<_Graph1>, public P2<_Graph2> { |
51 public: |
46 public: |
52 static void printNode() { std::cout << "node: generic" << std::endl; } |
47 static void printNode() { std::cout << "node: generic" << std::endl; } |
53 typedef _Graph1 Graph1; |
48 typedef _Graph1 Graph1; |
54 typedef _Graph2 Graph2; |
49 typedef _Graph2 Graph2; |
55 typedef P1<_Graph1> Parent1; |
50 typedef P1<_Graph1> Parent1; |
56 typedef P2<_Graph2> Parent2; |
51 typedef P2<_Graph2> Parent2; |
57 typedef typename Parent1::Node Graph1Node; |
52 typedef typename Parent1::Node Graph1Node; |
58 typedef typename Parent2::Node Graph2Node; |
53 typedef typename Parent2::Node Graph2Node; |
59 protected: |
54 protected: |
60 MergeNodeGraphWrapperBase() { } |
55 MergeNodeGraphWrapperBaseBase() { } |
61 public: |
56 public: |
62 template <typename _Value> class NodeMap; |
|
63 |
57 |
64 class Node : public Graph1Node, public Graph2Node { |
58 class Node : public Graph1Node, public Graph2Node { |
65 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>; |
59 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>; |
66 template <typename _Value> friend class NodeMap; |
|
67 protected: |
60 protected: |
68 bool backward; //true, iff backward |
61 bool backward; //true, iff backward |
69 public: |
62 public: |
70 Node() { } |
63 Node() { } |
71 /// \todo =false is needed, or causes problems? |
64 /// \todo =false is needed, or causes problems? |
86 bool operator!=(const Node& v) const { |
79 bool operator!=(const Node& v) const { |
87 return !(*this==v); |
80 return !(*this==v); |
88 } |
81 } |
89 }; |
82 }; |
90 |
83 |
91 //typedef void Edge; |
84 static bool forward(const Node& n) { return !n.backward; } |
92 class Edge { }; |
85 static bool backward(const Node& n) { return n.backward; } |
93 |
86 static void setForward(Node& n) { n.backward=false; } |
94 void first(Node& i) const { |
87 static void setBackward(Node& n) { n.backward=true; } |
95 Parent1::graph->first(*static_cast<Graph1Node*>(&i)); |
88 }; |
96 i.backward=false; |
89 |
97 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
90 |
98 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
|
99 i.backward=true; |
|
100 } |
|
101 } |
|
102 void next(Node& i) const { |
|
103 if (!(i.backward)) { |
|
104 Parent1::graph->next(*static_cast<Graph1Node*>(&i)); |
|
105 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
|
106 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
|
107 i.backward=true; |
|
108 } |
|
109 } else { |
|
110 Parent2::graph->next(*static_cast<Graph2Node*>(&i)); |
|
111 } |
|
112 } |
|
113 |
|
114 int id(const Node& n) const { |
|
115 if (!n.backward) |
|
116 return this->Parent1::graph->id(n); |
|
117 else |
|
118 return this->Parent2::graph->id(n); |
|
119 } |
|
120 |
|
121 template <typename _Value> |
|
122 class NodeMap { |
|
123 protected: |
|
124 typedef typename _Graph1::template NodeMap<_Value> ParentMap1; |
|
125 typedef typename _Graph2::template NodeMap<_Value> ParentMap2; |
|
126 ParentMap1 forward_map; |
|
127 ParentMap2 backward_map; |
|
128 public: |
|
129 typedef _Value Value; |
|
130 typedef Node Key; |
|
131 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : |
|
132 forward_map(*(gw.Parent1::graph)), |
|
133 backward_map(*(gw.Parent2::graph)) { } |
|
134 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, |
|
135 const _Value& value) : |
|
136 forward_map(*(gw.Parent1::graph), value), |
|
137 backward_map(*(gw.Parent2::graph), value) { } |
|
138 _Value operator[](const Node& n) const { |
|
139 if (!n.backward) |
|
140 return forward_map[n]; |
|
141 else |
|
142 return backward_map[n]; |
|
143 } |
|
144 void set(const Node& n, const _Value& value) { |
|
145 if (!n.backward) |
|
146 forward_map.set(n, value); |
|
147 else |
|
148 backward_map.set(n, value); |
|
149 } |
|
150 // using ParentMap1::operator[]; |
|
151 // using ParentMap2::operator[]; |
|
152 }; |
|
153 |
|
154 }; |
|
155 |
|
156 |
|
157 /*! A graph wrapper base class |
|
158 for merging the node-set of two node-disjoint graphs |
|
159 into the node-set of one graph. |
|
160 Specialization for the case when _Graph1::Node are the same _Graph2::Node. |
|
161 */ |
|
162 template <typename _Graph1, typename _Graph2> |
91 template <typename _Graph1, typename _Graph2> |
163 class MergeNodeGraphWrapperBase< |
92 class MergeNodeGraphWrapperBaseBase< |
164 _Graph1, _Graph2, typename boost::enable_if< |
93 _Graph1, _Graph2, typename boost::enable_if< |
165 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : |
94 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : |
166 public P1<_Graph1>, public P2<_Graph2> { |
95 public P1<_Graph1>, public P2<_Graph2> { |
167 public: |
96 public: |
168 static void printNode() { std::cout << "node: same" << std::endl; } |
97 static void printNode() { std::cout << "node: same" << std::endl; } |
171 typedef P1<_Graph1> Parent1; |
100 typedef P1<_Graph1> Parent1; |
172 typedef P2<_Graph2> Parent2; |
101 typedef P2<_Graph2> Parent2; |
173 typedef typename Parent1::Node Graph1Node; |
102 typedef typename Parent1::Node Graph1Node; |
174 typedef typename Parent2::Node Graph2Node; |
103 typedef typename Parent2::Node Graph2Node; |
175 protected: |
104 protected: |
176 MergeNodeGraphWrapperBase() { } |
105 MergeNodeGraphWrapperBaseBase() { } |
177 public: |
106 public: |
178 template <typename _Value> class NodeMap; |
|
179 |
107 |
180 class Node : public Graph1Node { |
108 class Node : public Graph1Node { |
181 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>; |
109 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>; |
182 template <typename _Value> friend class NodeMap; |
|
183 protected: |
110 protected: |
184 bool backward; //true, iff backward |
111 bool backward; //true, iff backward |
185 public: |
112 public: |
186 Node() { } |
113 Node() { } |
187 /// \todo =false is needed, or causes problems? |
114 /// \todo =false is needed, or causes problems? |
188 /// If \c _backward is false, then we get an edge corresponding to the |
115 /// If \c _backward is false, then we get an edge corresponding to the |
189 /// original one, otherwise its oppositely directed pair is obtained. |
116 /// original one, otherwise its oppositely directed pair is obtained. |
190 Node(const Graph1Node& n1, |
117 Node(const Graph1Node& n1, |
191 const Graph2Node& n2, bool _backward) : |
118 const Graph2Node& n2, bool _backward) : |
192 Graph1Node(!backward ? n1 : n2), backward(_backward) { } |
119 Graph1Node(!_backward ? n1 : n2), backward(_backward) { } |
193 Node(Invalid i) : Graph1Node(i), backward(true) { } |
120 Node(Invalid i) : Graph1Node(i), backward(true) { } |
194 bool operator==(const Node& v) const { |
121 bool operator==(const Node& v) const { |
195 return (backward==v.backward && |
122 return (backward==v.backward && |
196 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); |
123 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); |
197 } |
124 } |
198 bool operator!=(const Node& v) const { |
125 bool operator!=(const Node& v) const { |
199 return !(*this==v); |
126 return !(*this==v); |
200 } |
127 } |
201 }; |
128 }; |
202 |
129 |
203 //typedef void Edge; |
130 static bool forward(const Node& n) { return !n.backward; } |
204 class Edge { }; |
131 static bool backward(const Node& n) { return n.backward; } |
205 |
132 static void setForward(Node& n) { n.backward=false; } |
206 void first(Node& i) const { |
133 static void setBackward(Node& n) { n.backward=true; } |
207 Parent1::graph->first(*static_cast<Graph1Node*>(&i)); |
134 }; |
208 i.backward=false; |
135 |
209 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
136 |
210 Parent2::graph->first(*static_cast<Graph1Node*>(&i)); |
|
211 i.backward=true; |
|
212 } |
|
213 } |
|
214 void next(Node& i) const { |
|
215 if (!(i.backward)) { |
|
216 Parent1::graph->next(*static_cast<Graph1Node*>(&i)); |
|
217 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
|
218 Parent2::graph->first(*static_cast<Graph1Node*>(&i)); |
|
219 i.backward=true; |
|
220 } |
|
221 } else { |
|
222 Parent2::graph->next(*static_cast<Graph1Node*>(&i)); |
|
223 } |
|
224 } |
|
225 |
|
226 int id(const Node& n) const { |
|
227 if (!n.backward) |
|
228 return this->Parent1::graph->id(n); |
|
229 else |
|
230 return this->Parent2::graph->id(n); |
|
231 } |
|
232 |
|
233 template <typename _Value> |
|
234 class NodeMap { |
|
235 protected: |
|
236 typedef typename _Graph1::template NodeMap<_Value> ParentMap1; |
|
237 typedef typename _Graph2::template NodeMap<_Value> ParentMap2; |
|
238 ParentMap1 forward_map; |
|
239 ParentMap2 backward_map; |
|
240 public: |
|
241 typedef _Value Value; |
|
242 typedef Node Key; |
|
243 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : |
|
244 forward_map(*(gw.Parent1::graph)), |
|
245 backward_map(*(gw.Parent2::graph)) { } |
|
246 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, |
|
247 const _Value& value) : |
|
248 forward_map(*(gw.Parent1::graph), value), |
|
249 backward_map(*(gw.Parent2::graph), value) { } |
|
250 _Value operator[](const Node& n) const { |
|
251 if (!n.backward) |
|
252 return forward_map[n]; |
|
253 else |
|
254 return backward_map[n]; |
|
255 } |
|
256 void set(const Node& n, const _Value& value) { |
|
257 if (!n.backward) |
|
258 forward_map.set(n, value); |
|
259 else |
|
260 backward_map.set(n, value); |
|
261 } |
|
262 // using ParentMap1::operator[]; |
|
263 // using ParentMap2::operator[]; |
|
264 }; |
|
265 |
|
266 }; |
|
267 |
|
268 |
|
269 /*! A graph wrapper base class |
|
270 for merging the node-set of two node-disjoint graphs |
|
271 into the node-set of one graph. |
|
272 Specialization for the case when |
|
273 _Graph1::Node is a base class and _Graph2::Node is derived from it. |
|
274 */ |
|
275 template <typename _Graph1, typename _Graph2> |
137 template <typename _Graph1, typename _Graph2> |
276 class MergeNodeGraphWrapperBase< |
138 class MergeNodeGraphWrapperBaseBase< |
277 _Graph1, _Graph2, typename boost::enable_if< |
139 _Graph1, _Graph2, typename boost::enable_if< |
278 boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> : |
140 boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> : |
279 public P1<_Graph1>, public P2<_Graph2> { |
141 public P1<_Graph1>, public P2<_Graph2> { |
280 public : |
142 public : |
281 static void printNode() { std::cout << "node: 2nd is derived" << std::endl; } |
143 static void printNode() { std::cout << "node: 2nd is derived" << std::endl; } |
284 typedef P1<_Graph1> Parent1; |
146 typedef P1<_Graph1> Parent1; |
285 typedef P2<_Graph2> Parent2; |
147 typedef P2<_Graph2> Parent2; |
286 typedef typename Parent1::Node Graph1Node; |
148 typedef typename Parent1::Node Graph1Node; |
287 typedef typename Parent2::Node Graph2Node; |
149 typedef typename Parent2::Node Graph2Node; |
288 protected: |
150 protected: |
289 MergeNodeGraphWrapperBase() { } |
151 MergeNodeGraphWrapperBaseBase() { } |
290 public: |
152 public: |
291 template <typename _Value> class NodeMap; |
|
292 |
153 |
293 class Node : public Graph2Node { |
154 class Node : public Graph2Node { |
294 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>; |
155 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>; |
295 template <typename _Value> friend class NodeMap; |
|
296 protected: |
156 protected: |
297 bool backward; //true, iff backward |
157 bool backward; //true, iff backward |
298 public: |
158 public: |
299 Node() { } |
159 Node() { } |
300 /// \todo =false is needed, or causes problems? |
160 /// \todo =false is needed, or causes problems? |
317 bool operator!=(const Node& v) const { |
177 bool operator!=(const Node& v) const { |
318 return !(*this==v); |
178 return !(*this==v); |
319 } |
179 } |
320 }; |
180 }; |
321 |
181 |
322 //typedef void Edge; |
182 static bool forward(const Node& n) { return !n.backward; } |
323 class Edge { }; |
183 static bool backward(const Node& n) { return n.backward; } |
324 |
184 static void setForward(Node& n) { n.backward=false; } |
325 void first(Node& i) const { |
185 static void setBackward(Node& n) { n.backward=true; } |
326 Parent1::graph->first(*static_cast<Graph1Node*>(&i)); |
186 }; |
327 i.backward=false; |
187 |
328 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
188 |
329 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
|
330 i.backward=true; |
|
331 } |
|
332 } |
|
333 void next(Node& i) const { |
|
334 if (!(i.backward)) { |
|
335 Parent1::graph->next(*static_cast<Graph1Node*>(&i)); |
|
336 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
|
337 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
|
338 i.backward=true; |
|
339 } |
|
340 } else { |
|
341 Parent2::graph->next(*static_cast<Graph2Node*>(&i)); |
|
342 } |
|
343 } |
|
344 |
|
345 int id(const Node& n) const { |
|
346 if (!n.backward) |
|
347 return this->Parent1::graph->id(n); |
|
348 else |
|
349 return this->Parent2::graph->id(n); |
|
350 } |
|
351 |
|
352 template <typename _Value> |
|
353 class NodeMap { |
|
354 protected: |
|
355 typedef typename _Graph1::template NodeMap<_Value> ParentMap1; |
|
356 typedef typename _Graph2::template NodeMap<_Value> ParentMap2; |
|
357 ParentMap1 forward_map; |
|
358 ParentMap2 backward_map; |
|
359 public: |
|
360 typedef _Value Value; |
|
361 typedef Node Key; |
|
362 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : |
|
363 forward_map(*(gw.Parent1::graph)), |
|
364 backward_map(*(gw.Parent2::graph)) { } |
|
365 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, |
|
366 const _Value& value) : |
|
367 forward_map(*(gw.Parent1::graph), value), |
|
368 backward_map(*(gw.Parent2::graph), value) { } |
|
369 _Value operator[](const Node& n) const { |
|
370 if (!n.backward) |
|
371 return forward_map[n]; |
|
372 else |
|
373 return backward_map[n]; |
|
374 } |
|
375 void set(const Node& n, const _Value& value) { |
|
376 if (!n.backward) |
|
377 forward_map.set(n, value); |
|
378 else |
|
379 backward_map.set(n, value); |
|
380 } |
|
381 // using ParentMap1::operator[]; |
|
382 // using ParentMap2::operator[]; |
|
383 }; |
|
384 |
|
385 }; |
|
386 |
|
387 |
|
388 /*! A graph wrapper base class |
|
389 for merging the node-set of two node-disjoint graphs |
|
390 into the node-set of one graph. |
|
391 Specialized implementaton for the case when _Graph1::Node is derived |
|
392 from _Graph2::Node. |
|
393 */ |
|
394 template <typename _Graph1, typename _Graph2> |
189 template <typename _Graph1, typename _Graph2> |
395 class MergeNodeGraphWrapperBase< |
190 class MergeNodeGraphWrapperBaseBase< |
396 _Graph1, _Graph2, typename boost::enable_if< |
191 _Graph1, _Graph2, typename boost::enable_if< |
397 boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> : |
192 boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> : |
398 public P1<_Graph1>, public P2<_Graph2> { |
193 public P1<_Graph1>, public P2<_Graph2> { |
399 public : |
194 public : |
400 static void printNode() { std::cout << "node: 1st is derived" << std::endl; } |
195 static void printNode() { std::cout << "node: 1st is derived" << std::endl; } |
403 typedef P1<_Graph1> Parent1; |
198 typedef P1<_Graph1> Parent1; |
404 typedef P2<_Graph2> Parent2; |
199 typedef P2<_Graph2> Parent2; |
405 typedef typename Parent1::Node Graph1Node; |
200 typedef typename Parent1::Node Graph1Node; |
406 typedef typename Parent2::Node Graph2Node; |
201 typedef typename Parent2::Node Graph2Node; |
407 protected: |
202 protected: |
408 MergeNodeGraphWrapperBase() { } |
203 MergeNodeGraphWrapperBaseBase() { } |
409 public: |
204 public: |
410 template <typename _Value> class NodeMap; |
|
411 |
205 |
412 class Node : public Graph1Node { |
206 class Node : public Graph1Node { |
413 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>; |
207 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>; |
414 template <typename _Value> friend class NodeMap; |
|
415 protected: |
208 protected: |
416 bool backward; //true, iff backward |
209 bool backward; //true, iff backward |
417 public: |
210 public: |
418 Node() { } |
211 Node() { } |
419 /// \todo =false is needed, or causes problems? |
212 /// \todo =false is needed, or causes problems? |
436 bool operator!=(const Node& v) const { |
229 bool operator!=(const Node& v) const { |
437 return !(*this==v); |
230 return !(*this==v); |
438 } |
231 } |
439 }; |
232 }; |
440 |
233 |
441 //typedef void Edge; |
234 static bool forward(const Node& n) { return !n.backward; } |
|
235 static bool backward(const Node& n) { return n.backward; } |
|
236 static void setForward(Node& n) { n.backward=false; } |
|
237 static void setBackward(Node& n) { n.backward=true; } |
|
238 }; |
|
239 |
|
240 |
|
241 template <typename _Graph1, typename _Graph2> |
|
242 class MergeNodeGraphWrapperBase : |
|
243 public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> { |
|
244 public: |
|
245 typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent; |
|
246 typedef _Graph1 Graph1; |
|
247 typedef _Graph2 Graph2; |
|
248 typedef P1<_Graph1> Parent1; |
|
249 typedef P2<_Graph2> Parent2; |
|
250 typedef typename Parent1::Node Graph1Node; |
|
251 typedef typename Parent2::Node Graph2Node; |
|
252 |
|
253 typedef typename Parent::Node Node; |
442 class Edge { }; |
254 class Edge { }; |
443 |
255 |
444 void first(Node& i) const { |
256 void first(Node& i) const { |
445 Parent1::graph->first(*static_cast<Graph1Node*>(&i)); |
257 Parent1::graph->first(*static_cast<Graph1Node*>(&i)); |
446 i.backward=false; |
258 this->setForward(i); |
447 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
259 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
448 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
260 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
449 i.backward=true; |
261 this->setBackward(i); |
450 } |
262 } |
451 } |
263 } |
452 void next(Node& i) const { |
264 void next(Node& i) const { |
453 if (!(i.backward)) { |
265 if (this->forward(i)) { |
454 Parent1::graph->next(*static_cast<Graph1Node*>(&i)); |
266 Parent1::graph->next(*static_cast<Graph1Node*>(&i)); |
455 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
267 if (*static_cast<Graph1Node*>(&i)==INVALID) { |
456 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
268 Parent2::graph->first(*static_cast<Graph2Node*>(&i)); |
457 i.backward=true; |
269 this->setBackward(i); |
458 } |
270 } |
459 } else { |
271 } else { |
460 Parent2::graph->next(*static_cast<Graph2Node*>(&i)); |
272 Parent2::graph->next(*static_cast<Graph2Node*>(&i)); |
461 } |
273 } |
462 } |
274 } |
463 |
275 |
464 int id(const Node& n) const { |
276 int id(const Node& n) const { |
465 if (!n.backward) |
277 if (this->forward(n)) |
466 return this->Parent1::graph->id(n); |
278 return this->Parent1::graph->id(n); |
467 else |
279 else |
468 return this->Parent2::graph->id(n); |
280 return this->Parent2::graph->id(n); |
469 } |
281 } |
470 |
282 |
484 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, |
296 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, |
485 const _Value& value) : |
297 const _Value& value) : |
486 forward_map(*(gw.Parent1::graph), value), |
298 forward_map(*(gw.Parent1::graph), value), |
487 backward_map(*(gw.Parent2::graph), value) { } |
299 backward_map(*(gw.Parent2::graph), value) { } |
488 _Value operator[](const Node& n) const { |
300 _Value operator[](const Node& n) const { |
489 if (!n.backward) |
301 if (Parent::forward(n)) |
490 return forward_map[n]; |
302 return forward_map[n]; |
491 else |
303 else |
492 return backward_map[n]; |
304 return backward_map[n]; |
493 } |
305 } |
494 void set(const Node& n, const _Value& value) { |
306 void set(const Node& n, const _Value& value) { |
495 if (!n.backward) |
307 if (Parent::forward(n)) |
496 forward_map.set(n, value); |
308 forward_map.set(n, value); |
497 else |
309 else |
498 backward_map.set(n, value); |
310 backward_map.set(n, value); |
499 } |
311 } |
500 // using ParentMap1::operator[]; |
312 // using ParentMap1::operator[]; |
503 |
315 |
504 }; |
316 }; |
505 |
317 |
506 |
318 |
507 /*! A graph wrapper class |
319 /*! A graph wrapper class |
508 fors merging the node-set of two node-disjoint graphs |
320 for merging the node-set of two node-disjoint graphs |
509 into one node-set. It does not satisfy |
321 into the node-set of one graph. |
|
322 Different implementations are according to the relation of |
|
323 _Graph1::Node and _Graph2::Node. |
|
324 If _Graph1::Node and _Graph2::Node are unrelated, then |
|
325 MergeNodeGraphWrapper<_Graph1, _Graph2>::Node |
|
326 is derived from both. |
|
327 If _Graph1::Node and _Graph2::Node are the same type, then |
|
328 MergeNodeGraphWrapper<_Graph1, _Graph2>::Node |
|
329 is derived from _Graph1::Node. |
|
330 If one of _Graph1::Node and _Graph2::Node |
|
331 is derived from the other one, then |
|
332 MergeNodeGraphWrapper<_Graph1, _Graph2>::Node |
|
333 is derived from the derived type. |
|
334 It does not satisfy |
510 StaticGraph concept as it has no edge-set which |
335 StaticGraph concept as it has no edge-set which |
511 works together with the node-set. |
336 works together with the node-set. |
512 */ |
337 */ |
513 template <typename _Graph1, typename _Graph2> |
338 template <typename _Graph1, typename _Graph2> |
514 class MergeNodeGraphWrapper : public |
339 class MergeNodeGraphWrapper : public |
515 IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > { |
340 IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > { |
516 public: |
341 public: |
517 typedef _Graph1 Graph1; |
342 typedef _Graph1 Graph1; |
580 bool operator!=(const Edge& v) const { |
405 bool operator!=(const Edge& v) const { |
581 return !(*this==v); |
406 return !(*this==v); |
582 } |
407 } |
583 }; |
408 }; |
584 |
409 |
|
410 using Parent::forward; |
|
411 using Parent::backward; |
|
412 bool forward(const Edge& e) const { return !e.backward; } |
|
413 bool backward(const Edge& e) const { return e.backward; } |
|
414 |
585 using Parent::first; |
415 using Parent::first; |
586 void first(Edge& i) const { |
416 void first(Edge& i) const { |
587 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
417 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
588 i.backward=false; |
418 i.backward=false; |
589 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
419 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
590 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
420 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
591 i.backward=true; |
421 i.backward=true; |
592 } |
422 } |
593 } |
423 } |
594 void firstIn(Edge& i, const Node& n) const { |
424 void firstIn(Edge& i, const Node& n) const { |
595 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
425 if (!backward(n)) { |
596 i.backward=false; |
426 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
597 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
427 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
428 i=INVALID; |
|
429 else |
|
430 i.backward=false; |
|
431 } else { |
598 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
432 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
599 i.backward=true; |
433 i.backward=true; |
600 } |
434 } |
601 } |
435 } |
602 void firstOut(Edge& i, const Node& n) const { |
436 void firstOut(Edge& i, const Node& n) const { |
603 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
437 if (!backward(n)) { |
604 i.backward=false; |
438 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
605 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
439 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
440 i=INVALID; |
|
441 else |
|
442 i.backward=false; |
|
443 } else { |
606 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
444 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
607 i.backward=true; |
445 i.backward=true; |
608 } |
446 } |
609 } |
447 } |
610 |
448 |
747 /// \todo =false is needed, or causes problems? |
579 /// \todo =false is needed, or causes problems? |
748 /// If \c _backward is false, then we get an edge corresponding to the |
580 /// If \c _backward is false, then we get an edge corresponding to the |
749 /// original one, otherwise its oppositely directed pair is obtained. |
581 /// original one, otherwise its oppositely directed pair is obtained. |
750 Edge(const Graph1Edge& n1, |
582 Edge(const Graph1Edge& n1, |
751 const Graph2Edge& n2, bool _backward) : |
583 const Graph2Edge& n2, bool _backward) : |
752 Graph1Edge(!backward ? n1 : n2), backward(_backward) { } |
584 Graph1Edge(!_backward ? n1 : n2), backward(_backward) { } |
753 Edge(Invalid i) : Graph1Edge(i), backward(true) { } |
585 Edge(Invalid i) : Graph1Edge(i), backward(true) { } |
754 bool operator==(const Edge& v) const { |
586 bool operator==(const Edge& v) const { |
755 return (backward==v.backward && |
587 return (backward==v.backward && |
756 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); |
588 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); |
757 } |
589 } |
758 bool operator!=(const Edge& v) const { |
590 bool operator!=(const Edge& v) const { |
759 return !(*this==v); |
591 return !(*this==v); |
760 } |
592 } |
761 }; |
593 }; |
|
594 |
|
595 using Parent::forward; |
|
596 using Parent::backward; |
|
597 bool forward(const Edge& e) const { return !e.backward; } |
|
598 bool backward(const Edge& e) const { return e.backward; } |
762 |
599 |
763 using Parent::first; |
600 using Parent::first; |
764 void first(Edge& i) const { |
601 void first(Edge& i) const { |
765 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
602 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
766 i.backward=false; |
603 i.backward=false; |
768 Parent2::graph->first(*static_cast<Graph1Edge*>(&i)); |
605 Parent2::graph->first(*static_cast<Graph1Edge*>(&i)); |
769 i.backward=true; |
606 i.backward=true; |
770 } |
607 } |
771 } |
608 } |
772 void firstIn(Edge& i, const Node& n) const { |
609 void firstIn(Edge& i, const Node& n) const { |
773 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
610 if (!backward(n)) { |
774 i.backward=false; |
611 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
775 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
612 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
613 i=INVALID; |
|
614 else |
|
615 i.backward=false; |
|
616 } else { |
776 Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
617 Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
777 i.backward=true; |
618 i.backward=true; |
778 } |
619 } |
779 } |
620 } |
780 void firstOut(Edge& i, const Node& n) const { |
621 void firstOut(Edge& i, const Node& n) const { |
781 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
622 if (!backward(n)) { |
782 i.backward=false; |
623 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
783 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
624 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
625 i=INVALID; |
|
626 else |
|
627 i.backward=false; |
|
628 } else { |
784 Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
629 Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
785 i.backward=true; |
630 i.backward=true; |
786 } |
631 } |
787 } |
632 } |
788 |
633 |
943 bool operator!=(const Edge& v) const { |
782 bool operator!=(const Edge& v) const { |
944 return !(*this==v); |
783 return !(*this==v); |
945 } |
784 } |
946 }; |
785 }; |
947 |
786 |
|
787 using Parent::forward; |
|
788 using Parent::backward; |
|
789 bool forward(const Edge& e) const { return !e.backward; } |
|
790 bool backward(const Edge& e) const { return e.backward; } |
|
791 |
948 using Parent::first; |
792 using Parent::first; |
949 void first(Edge& i) const { |
793 void first(Edge& i) const { |
950 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
794 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
951 i.backward=false; |
795 i.backward=false; |
952 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
796 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
953 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
797 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
954 i.backward=true; |
798 i.backward=true; |
955 } |
799 } |
956 } |
800 } |
957 void firstIn(Edge& i, const Node& n) const { |
801 void firstIn(Edge& i, const Node& n) const { |
958 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
802 if (!backward(n)) { |
959 i.backward=false; |
803 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
960 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
804 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
805 i=INVALID; |
|
806 else |
|
807 i.backward=false; |
|
808 } else { |
961 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
809 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
962 i.backward=true; |
810 i.backward=true; |
963 } |
811 } |
964 } |
812 } |
965 void firstOut(Edge& i, const Node& n) const { |
813 void firstOut(Edge& i, const Node& n) const { |
966 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
814 if (!backward(n)) { |
967 i.backward=false; |
815 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
968 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
816 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
817 i=INVALID; |
|
818 else |
|
819 i.backward=false; |
|
820 } else { |
969 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
821 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
970 i.backward=true; |
822 i.backward=true; |
971 } |
823 } |
972 } |
824 } |
973 |
825 |
1127 bool operator!=(const Edge& v) const { |
973 bool operator!=(const Edge& v) const { |
1128 return !(*this==v); |
974 return !(*this==v); |
1129 } |
975 } |
1130 }; |
976 }; |
1131 |
977 |
|
978 using Parent::forward; |
|
979 using Parent::backward; |
|
980 bool forward(const Edge& e) const { return !e.backward; } |
|
981 bool backward(const Edge& e) const { return e.backward; } |
|
982 |
1132 using Parent::first; |
983 using Parent::first; |
1133 void first(Edge& i) const { |
984 void first(Edge& i) const { |
1134 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
985 Parent1::graph->first(*static_cast<Graph1Edge*>(&i)); |
1135 i.backward=false; |
986 i.backward=false; |
1136 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
987 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
1137 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
988 Parent2::graph->first(*static_cast<Graph2Edge*>(&i)); |
1138 i.backward=true; |
989 i.backward=true; |
1139 } |
990 } |
1140 } |
991 } |
1141 void firstIn(Edge& i, const Node& n) const { |
992 void firstIn(Edge& i, const Node& n) const { |
1142 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
993 if (!backward(n)) { |
1143 i.backward=false; |
994 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n); |
1144 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
995 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
996 i=INVALID; |
|
997 else |
|
998 i.backward=false; |
|
999 } else { |
1145 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
1000 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n); |
1146 i.backward=true; |
1001 i.backward=true; |
1147 } |
1002 } |
1148 } |
1003 } |
1149 void firstOut(Edge& i, const Node& n) const { |
1004 void firstOut(Edge& i, const Node& n) const { |
1150 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
1005 if (!backward(n)) { |
1151 i.backward=false; |
1006 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n); |
1152 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
1007 if (*static_cast<Graph1Edge*>(&i)==INVALID) |
|
1008 i=INVALID; |
|
1009 else |
|
1010 i.backward=false; |
|
1011 } else { |
1153 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
1012 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n); |
1154 i.backward=true; |
1013 i.backward=true; |
1155 } |
1014 } |
1156 } |
1015 } |
1157 |
1016 |
1407 setNodeMap(_n_node); |
1268 setNodeMap(_n_node); |
1408 setENodeMap(_e_node); |
1269 setENodeMap(_e_node); |
1409 } |
1270 } |
1410 }; |
1271 }; |
1411 |
1272 |
|
1273 /*! A graph wrapper class for the following functionality. |
|
1274 The same as NewEdgeSetGrapWrapper, but the bijection and the graph of |
|
1275 new edges is andled inthe class. |
|
1276 */ |
|
1277 template <typename _Graph, typename _EdgeSetGraph> |
|
1278 class NewEdgeSetGraphWrapper2 : |
|
1279 public IterableGraphExtender< |
|
1280 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > { |
|
1281 public: |
|
1282 typedef _Graph Graph; |
|
1283 typedef _EdgeSetGraph EdgeSetGraph; |
|
1284 typedef IterableGraphExtender< |
|
1285 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent; |
|
1286 protected: |
|
1287 _EdgeSetGraph _edge_set_graph; |
|
1288 typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node; |
|
1289 typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node; |
|
1290 NewEdgeSetGraphWrapper2() { } |
|
1291 public: |
|
1292 typedef typename Graph::Node Node; |
|
1293 // typedef typename Parent::Edge Edge; |
|
1294 |
|
1295 NewEdgeSetGraphWrapper2(_Graph& _graph) : |
|
1296 _edge_set_graph(), |
|
1297 _e_node(_graph), _n_node(_edge_set_graph) { |
|
1298 setGraph(_graph); |
|
1299 setEdgeSetGraph(_edge_set_graph); |
|
1300 setNodeMap(_n_node); setENodeMap(_e_node); |
|
1301 Node n; |
|
1302 for (this->first(n); n!=INVALID; this->next(n)) { |
|
1303 typename EdgeSetGraph::Node e=_edge_set_graph.addNode(); |
|
1304 _e_node.set(n, e); |
|
1305 _n_node.set(e, n); |
|
1306 } |
|
1307 } |
|
1308 |
|
1309 // Node addNode() { |
|
1310 // Node n=(*this).Parent::addNode(); |
|
1311 // typename EdgeSetGraph::Node e=_edge_set_graph.addNode(); |
|
1312 // _e_node.set(n, e); |
|
1313 // _n_node.set(e, n); |
|
1314 // return n; |
|
1315 // } |
|
1316 |
|
1317 }; |
1412 |
1318 |
1413 /*! A graph wrapper base class |
1319 /*! A graph wrapper base class |
1414 for merging graphs of type _Graph1 and _Graph2 |
1320 for merging graphs of type _Graph1 and _Graph2 |
1415 which are given on the same node-set |
1321 which are given on the same node-set |
1416 (specially on the node-set of Graph1) |
1322 (specially on the node-set of Graph1) |
1417 into one graph. |
1323 into one graph. |
1418 In an other point of view, _Graph1 is extended with |
1324 In an other point of view, _Graph1 is extended with |
1419 the edge-set of _Graph2. |
1325 the edge-set of _Graph2. |
|
1326 \warning we need specialize dimplementations |
|
1327 \todo we need specialize dimplementations |
|
1328 \bug we need specialize dimplementations |
1420 */ |
1329 */ |
1421 template <typename _Graph1, typename _Graph2, typename Enable=void> |
1330 template <typename _Graph1, typename _Graph2, typename Enable=void> |
1422 class AugmentingGraphWrapperBase : |
1331 class AugmentingGraphWrapperBase : |
1423 public P1<_Graph1> { |
1332 public P1<_Graph1> { |
1424 public: |
1333 public: |
1504 graph2->next(*static_cast<Graph2Edge*>(&i)); |
1413 graph2->next(*static_cast<Graph2Edge*>(&i)); |
1505 } |
1414 } |
1506 } |
1415 } |
1507 void nextIn(Edge& i) const { |
1416 void nextIn(Edge& i) const { |
1508 if (!(i.backward)) { |
1417 if (!(i.backward)) { |
|
1418 Node n=target(i); |
1509 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
1419 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i)); |
1510 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
1420 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
1511 graph2->first(*static_cast<Graph2Edge*>(&i)); |
1421 graph2->firstIn(*static_cast<Graph2Edge*>(&i), n); |
1512 i.backward=true; |
1422 i.backward=true; |
1513 } |
1423 } |
1514 } else { |
1424 } else { |
1515 graph2->nextIn(*static_cast<Graph2Edge*>(&i)); |
1425 graph2->nextIn(*static_cast<Graph2Edge*>(&i)); |
1516 } |
1426 } |
1517 } |
1427 } |
1518 void nextOut(Edge& i) const { |
1428 void nextOut(Edge& i) const { |
1519 if (!(i.backward)) { |
1429 if (!(i.backward)) { |
|
1430 Node n=source(i); |
1520 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
1431 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i)); |
1521 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
1432 if (*static_cast<Graph1Edge*>(&i)==INVALID) { |
1522 graph2->first(*static_cast<Graph2Edge*>(&i)); |
1433 graph2->firstOut(*static_cast<Graph2Edge*>(&i), n); |
1523 i.backward=true; |
1434 i.backward=true; |
1524 } |
1435 } |
1525 } else { |
1436 } else { |
1526 graph2->nextOut(*static_cast<Graph2Edge*>(&i)); |
1437 graph2->nextOut(*static_cast<Graph2Edge*>(&i)); |
1527 } |
1438 } |