28 /// graph or a directed graph with edges oriented from S to T. |
28 /// graph or a directed graph with edges oriented from S to T. |
29 /// |
29 /// |
30 /// \author Marton Makai |
30 /// \author Marton Makai |
31 template<typename Graph> |
31 template<typename Graph> |
32 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
32 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
33 protected: |
33 public: |
34 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
34 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
35 SFalseTTrueMap; |
35 SFalseTTrueMap; |
|
36 protected: |
36 SFalseTTrueMap* s_false_t_true_map; |
37 SFalseTTrueMap* s_false_t_true_map; |
37 |
38 |
38 BipartiteGraphWrapper() : GraphWrapper<Graph>()/*, |
39 BipartiteGraphWrapper() : GraphWrapper<Graph>()/*, |
39 S_CLASS(false), T_CLASS(true)*/ { } |
40 S_CLASS(false), T_CLASS(true)*/ { } |
40 void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) { |
41 void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) { |
44 public: |
45 public: |
45 //marci |
46 //marci |
46 //FIXME vhogy igy kellene, csak az en forditom nem eszi meg |
47 //FIXME vhogy igy kellene, csak az en forditom nem eszi meg |
47 static const bool S_CLASS; |
48 static const bool S_CLASS; |
48 static const bool T_CLASS; |
49 static const bool T_CLASS; |
|
50 |
|
51 /// This method is to reach the iterable maps of the bipartite graph or |
|
52 /// bipartite graph wrapper. |
|
53 const SFalseTTrueMap& sFalseTTrueMap() const { |
|
54 return *s_false_t_true_map; |
|
55 } |
49 |
56 |
50 //bool S_CLASS; |
57 //bool S_CLASS; |
51 //bool T_CLASS; |
58 //bool T_CLASS; |
52 |
59 |
53 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) |
60 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) |
209 /// |
216 /// |
210 ///\bug experimental. Do not use this while the bipartitemap augmentation |
217 ///\bug experimental. Do not use this while the bipartitemap augmentation |
211 /// does not work well. |
218 /// does not work well. |
212 template<typename Graph> |
219 template<typename Graph> |
213 class BipartiteGraph : public BipartiteGraphWrapper<Graph> { |
220 class BipartiteGraph : public BipartiteGraphWrapper<Graph> { |
214 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
221 // typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
215 SFalseTTrueMap; |
222 // SFalseTTrueMap; |
216 typedef BipartiteGraphWrapper<Graph> Parent; |
223 typedef BipartiteGraphWrapper<Graph> Parent; |
217 protected: |
224 protected: |
218 Graph gr; |
225 Graph gr; |
219 typename Graph::template NodeMap<int> bipartite_map; |
226 typename Graph::template NodeMap<int> bipartite_map; |
220 SFalseTTrueMap s_false_t_true_map; |
227 typename Parent::SFalseTTrueMap s_false_t_true_map; |
221 public: |
228 public: |
222 typedef typename Parent::Node Node; |
229 typedef typename Parent::Node Node; |
223 typedef typename Parent::Edge Edge; |
230 typedef typename Parent::Edge Edge; |
224 BipartiteGraph() : BipartiteGraphWrapper<Graph>(), |
231 BipartiteGraph() : BipartiteGraphWrapper<Graph>(), |
225 gr(), bipartite_map(gr, -1), |
232 gr(), bipartite_map(gr, -1), |
256 FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e); |
263 FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e); |
257 FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n); |
264 FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n); |
258 } |
265 } |
259 }; |
266 }; |
260 |
267 |
261 |
268 template<typename Graph, typename sIterableMap, typename tIterableMap> |
|
269 class stGraphWrapper; |
|
270 |
|
271 /// Easier stuff for bipartite graphs. |
262 template<typename Graph> |
272 template<typename Graph> |
263 class stGraphWrapper; |
273 class stBipartiteGraphWrapper : public |
|
274 stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, |
|
275 typename Graph::SFalseTTrueMap> { |
|
276 public: |
|
277 typedef stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, |
|
278 typename Graph::SFalseTTrueMap> Parent; |
|
279 stBipartiteGraphWrapper(Graph& _graph) : |
|
280 Parent(_graph, _graph.sFalseTTrueMap(), _graph.sFalseTTrueMap()) { } |
|
281 }; |
264 |
282 |
265 // template<typename Graph> |
283 // template<typename Graph> |
266 // std::ostream& |
284 // std::ostream& |
267 // operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { |
285 // operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { |
268 // os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; |
286 // os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; |
285 /// generally, capacitataed b-matching problem to a flow problem. |
303 /// generally, capacitataed b-matching problem to a flow problem. |
286 /// According to the bipartite graph concepts the bipartite |
304 /// According to the bipartite graph concepts the bipartite |
287 /// graph have to be oriented from S to T. |
305 /// graph have to be oriented from S to T. |
288 /// |
306 /// |
289 /// \author Marton Makai |
307 /// \author Marton Makai |
290 template<typename Graph> |
308 template<typename Graph, typename sIterableMap, typename tIterableMap> |
291 class stGraphWrapper : public GraphWrapper<Graph> { |
309 class stGraphWrapper : public GraphWrapper<Graph> { |
|
310 protected: |
|
311 const sIterableMap* s_iterable_map; |
|
312 const tIterableMap* t_iterable_map; |
292 public: |
313 public: |
293 class Node; |
314 class Node; |
294 friend class Node; |
315 friend class Node; |
295 //GN, int |
316 //GN, int |
296 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend, |
317 //0 normalis, 1 s, 2 t, ez az iteralasi sorrend, |
297 //es a vege a false azaz (invalid, 3) |
318 //es a vege a false azaz (invalid, 3) |
298 class NodeIt; |
319 class NodeIt; |
299 friend class NodeIt; |
320 friend class NodeIt; |
300 //GNI, int |
321 //GNI, int |
301 class Edge; |
322 class Edge; |
332 const Node T_NODE; |
353 const Node T_NODE; |
333 |
354 |
334 static const bool S_CLASS=false; |
355 static const bool S_CLASS=false; |
335 static const bool T_CLASS=true; |
356 static const bool T_CLASS=true; |
336 |
357 |
337 stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , |
358 // \bug not too nice constructor. |
338 S_NODE(INVALID, 1), |
359 stGraphWrapper(Graph& _graph, |
339 T_NODE(INVALID, 2) { } |
360 const sIterableMap& _s_iterable_map, |
|
361 const tIterableMap& _t_iterable_map) : |
|
362 GraphWrapper<Graph>(_graph), |
|
363 s_iterable_map(&_s_iterable_map), |
|
364 t_iterable_map(&_t_iterable_map), |
|
365 S_NODE(INVALID, 1), |
|
366 T_NODE(INVALID, 2) { } |
340 |
367 |
341 |
368 |
342 // std::ostream& |
369 // std::ostream& |
343 // operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i); |
370 // operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i); |
344 // friend std::ostream& |
371 // friend std::ostream& |
347 // operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i); |
374 // operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i); |
348 |
375 |
349 class Node : public Graph::Node { |
376 class Node : public Graph::Node { |
350 protected: |
377 protected: |
351 friend class GraphWrapper<Graph>; |
378 friend class GraphWrapper<Graph>; |
352 friend class stGraphWrapper<Graph>; |
379 friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>; |
353 template <typename T> friend class NodeMap; |
380 template <typename T> friend class NodeMap; |
354 friend class Edge; |
381 friend class Edge; |
355 friend class OutEdgeIt; |
382 friend class OutEdgeIt; |
356 friend class InEdgeIt; |
383 friend class InEdgeIt; |
357 friend class EdgeIt; |
384 friend class EdgeIt; |
378 int getSpec() const { return spec; } |
405 int getSpec() const { return spec; } |
379 }; |
406 }; |
380 |
407 |
381 class NodeIt { |
408 class NodeIt { |
382 friend class GraphWrapper<Graph>; |
409 friend class GraphWrapper<Graph>; |
383 friend class stGraphWrapper<Graph>; |
410 friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>; |
384 typename Graph::NodeIt n; |
411 typename Graph::NodeIt n; |
385 int spec; |
412 int spec; |
386 public: |
413 public: |
387 NodeIt() { } |
414 NodeIt() { } |
388 NodeIt(const typename Graph::NodeIt& _n, int _spec) : |
415 NodeIt(const typename Graph::NodeIt& _n, int _spec) : |
389 n(_n), spec(_spec) { } |
416 n(_n), spec(_spec) { } |
390 NodeIt(const Invalid& i) : n(i), spec(3) { } |
417 NodeIt(const Invalid& i) : n(i), spec(3) { } |
391 NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { |
418 NodeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) |
|
419 : n(*(_G.graph)), spec(0) { |
392 if (!_G.graph->valid(n)) spec=1; |
420 if (!_G.graph->valid(n)) spec=1; |
393 } |
421 } |
394 operator Node() const { return Node(n, spec); } |
422 operator Node() const { return Node(n, spec); } |
395 }; |
423 }; |
396 |
424 |
397 class Edge : public Graph::Edge { |
425 class Edge : public Graph::Edge { |
398 friend class GraphWrapper<Graph>; |
426 friend class GraphWrapper<Graph>; |
399 friend class stGraphWrapper<Graph>; |
427 friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>; |
400 template <typename T> friend class EdgeMap; |
428 template <typename T> friend class EdgeMap; |
401 int spec; |
429 int spec; |
402 typename Graph::Node n; |
430 typename Graph::Node n; |
403 public: |
431 public: |
404 Edge() { } |
432 Edge() { } |
427 typename Graph::Node getNode() const { return n; } |
455 typename Graph::Node getNode() const { return n; } |
428 }; |
456 }; |
429 |
457 |
430 class OutEdgeIt { |
458 class OutEdgeIt { |
431 friend class GraphWrapper<Graph>; |
459 friend class GraphWrapper<Graph>; |
432 friend class stGraphWrapper<Graph>; |
460 friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>; |
433 typename Graph::OutEdgeIt e; |
461 typename Graph::OutEdgeIt e; |
434 int spec; |
462 int spec; |
435 typename Graph::ClassNodeIt n; |
463 typename Graph::ClassNodeIt n; |
436 public: |
464 public: |
437 OutEdgeIt() { } |
465 OutEdgeIt() { } |
438 OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, |
466 OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, |
439 const typename Graph::ClassNodeIt& _n) : |
467 const typename Graph::ClassNodeIt& _n) : |
440 e(_e), spec(_spec), n(_n) { |
468 e(_e), spec(_spec), n(_n) { |
441 } |
469 } |
442 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
470 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
443 OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) { |
471 OutEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, |
|
472 const Node& _n) { |
444 switch (_n.spec) { |
473 switch (_n.spec) { |
445 case 0 : |
474 case 0 : |
446 if (_G.graph->inSClass(_n)) { //S, van normalis kiel |
475 if (_G.graph->inSClass(_n)) { //S, van normalis kiel |
447 e=typename Graph::OutEdgeIt(*(_G.graph), |
476 e=typename Graph::OutEdgeIt(*(_G.graph), |
448 typename Graph::Node(_n)); |
477 typename Graph::Node(_n)); |
471 operator Edge() const { return Edge(e, spec, n); } |
500 operator Edge() const { return Edge(e, spec, n); } |
472 }; |
501 }; |
473 |
502 |
474 class InEdgeIt { |
503 class InEdgeIt { |
475 friend class GraphWrapper<Graph>; |
504 friend class GraphWrapper<Graph>; |
476 friend class stGraphWrapper<Graph>; |
505 friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>; |
477 typename Graph::InEdgeIt e; |
506 typename Graph::InEdgeIt e; |
478 int spec; |
507 int spec; |
479 typename Graph::ClassNodeIt n; |
508 typename Graph::ClassNodeIt n; |
480 public: |
509 public: |
481 InEdgeIt() { } |
510 InEdgeIt() { } |
482 InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, |
511 InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, |
483 const typename Graph::ClassNodeIt& _n) : |
512 const typename Graph::ClassNodeIt& _n) : |
484 e(_e), spec(_spec), n(_n) { |
513 e(_e), spec(_spec), n(_n) { |
485 } |
514 } |
486 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
515 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
487 InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) { |
516 InEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, |
|
517 const Node& _n) { |
488 switch (_n.spec) { |
518 switch (_n.spec) { |
489 case 0 : |
519 case 0 : |
490 if (_G.graph->inTClass(_n)) { //T, van normalis beel |
520 if (_G.graph->inTClass(_n)) { //T, van normalis beel |
491 e=typename Graph::InEdgeIt(*(_G.graph), |
521 e=typename Graph::InEdgeIt(*(_G.graph), |
492 typename Graph::Node(_n)); |
522 typename Graph::Node(_n)); |
515 operator Edge() const { return Edge(e, spec, n); } |
545 operator Edge() const { return Edge(e, spec, n); } |
516 }; |
546 }; |
517 |
547 |
518 class EdgeIt { |
548 class EdgeIt { |
519 friend class GraphWrapper<Graph>; |
549 friend class GraphWrapper<Graph>; |
520 friend class stGraphWrapper<Graph>; |
550 friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>; |
521 typename Graph::EdgeIt e; |
551 typename Graph::EdgeIt e; |
522 int spec; |
552 int spec; |
523 typename Graph::ClassNodeIt n; |
553 typename Graph::ClassNodeIt n; |
524 public: |
554 public: |
525 EdgeIt() { } |
555 EdgeIt() { } |
526 EdgeIt(const typename Graph::EdgeIt& _e, int _spec, |
556 EdgeIt(const typename Graph::EdgeIt& _e, int _spec, |
527 const typename Graph::ClassNodeIt& _n) : |
557 const typename Graph::ClassNodeIt& _n) : |
528 e(_e), spec(_spec), n(_n) { } |
558 e(_e), spec(_spec), n(_n) { } |
529 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
559 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
530 EdgeIt(const stGraphWrapper<Graph>& _G) : |
560 EdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) : |
531 e(*(_G.graph)), spec(0), n(INVALID) { |
561 e(*(_G.graph)), spec(0), n(INVALID) { |
532 if (!_G.graph->valid(e)) { |
562 if (!_G.graph->valid(e)) { |
533 spec=1; |
563 spec=1; |
534 _G.graph->first(n, S_CLASS); |
564 _G.graph->first(n, S_CLASS); |
535 if (!_G.graph->valid(n)) { //Ha S ures |
565 if (!_G.graph->valid(n)) { //Ha S ures |
716 template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { |
746 template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { |
717 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent; |
747 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent; |
718 protected: |
748 protected: |
719 T s_value, t_value; |
749 T s_value, t_value; |
720 public: |
750 public: |
721 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
751 NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) : |
722 s_value(), |
752 Parent(_G), |
723 t_value() { } |
753 s_value(), |
724 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
754 t_value() { } |
725 s_value(a), |
755 NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a) |
726 t_value(a) { } |
756 : Parent(_G, a), |
|
757 s_value(a), |
|
758 t_value(a) { } |
727 T operator[](const Node& n) const { |
759 T operator[](const Node& n) const { |
728 switch (n.spec) { |
760 switch (n.spec) { |
729 case 0: |
761 case 0: |
730 return Parent::operator[](n); |
762 return Parent::operator[](n); |
731 case 1: |
763 case 1: |
751 } |
783 } |
752 }; |
784 }; |
753 |
785 |
754 /// This class is to wrap a node-map of \c Graph and two variables |
786 /// This class is to wrap a node-map of \c Graph and two variables |
755 /// storing values for \c S_NODE and \c T_NODE to a node-map of |
787 /// storing values for \c S_NODE and \c T_NODE to a node-map of |
756 /// stGraphWrapper<Graph>. |
788 /// stGraphWrapper<Graph, sIterableMap, tIterableMap>. |
757 template<typename NM> class NodeMapWrapper { |
789 template<typename NM> class NodeMapWrapper { |
758 public: |
790 public: |
759 typedef Node KeyType; |
791 typedef Node KeyType; |
760 typedef typename NM::ValueType ValueType; |
792 typedef typename NM::ValueType ValueType; |
761 protected: |
793 protected: |
795 class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { |
827 class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { |
796 typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; |
828 typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; |
797 protected: |
829 protected: |
798 typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
830 typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
799 public: |
831 public: |
800 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
832 EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) |
801 node_value(_G) { } |
833 : Parent(_G), |
802 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
834 node_value(_G) { } |
803 node_value(_G, a) { } |
835 EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a) |
|
836 : Parent(_G, a), |
|
837 node_value(_G, a) { } |
804 T operator[](const Edge& e) const { |
838 T operator[](const Edge& e) const { |
805 switch (e.spec) { |
839 switch (e.spec) { |
806 case 0: |
840 case 0: |
807 return Parent::operator[](e); |
841 return Parent::operator[](e); |
808 case 1: |
842 case 1: |
827 } |
861 } |
828 } |
862 } |
829 }; |
863 }; |
830 |
864 |
831 /// This class is to wrap an edge-map and a node-map of \c Graph |
865 /// This class is to wrap an edge-map and a node-map of \c Graph |
832 /// to an edge-map of stGraphWrapper<Graph>. |
866 /// to an edge-map of stGraphWrapper<Graph, sIterableMap, tIterableMap>. |
833 template<typename EM, typename NM> |
867 template<typename EM, typename NM> |
834 class EdgeMapWrapper { |
868 class EdgeMapWrapper { |
835 public: |
869 public: |
836 typedef Edge KeyType; |
870 typedef Edge KeyType; |
837 typedef typename EM::ValueType ValueType; |
871 typedef typename EM::ValueType ValueType; |