Changeset 1013:b3bdd856faf4 in lemon0.x
 Timestamp:
 11/20/04 15:09:27 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1403
 Location:
 src
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r1004 r1013 1176 1176 ForwardFilterMap, BackwardFilterMap>& g, T a) : 1177 1177 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } 1178 1179 // template <typename TT>1180 // EdgeMap(const EdgeMap<TT>& copy)1181 // : forward_map(copy.forward_map), backward_map(copy.backward_map) {}1182 1183 // template <typename TT>1184 // EdgeMap& operator=(const EdgeMap<TT>& copy) {1185 // forward_map = copy.forward_map;1186 // backward_map = copy.backward_map;1187 // return *this;1188 // }1189 1178 1190 1179 void set(Edge e, T a) { 
src/work/marci/merge_node_graph_wrapper.h
r1009 r1013 23 23 #include <lemon/graph_wrapper.h> 24 24 #include <iostream> 25 25 26 using std::cout; 26 27 using std::endl; … … 39 40 }; 40 41 41 /*! A base class for merging the nodeset of two nodedisjoint graphs 42 into the nodeset of one graph. 42 43 /*! A graph wrapper base class 44 for merging the nodeset of two nodedisjoint graphs 45 into the nodeset of one graph. 46 Generic implementation for unrelated _Graph1::Node and _Graph2::Node. 43 47 */ 44 48 template <typename _Graph1, typename _Graph2, typename Enable=void> … … 46 50 public P1<_Graph1>, public P2<_Graph2> { 47 51 public: 48 void printNode() const { std::cout << "generic" << std::endl; }52 static void printNode() { std::cout << "node: generic" << std::endl; } 49 53 typedef _Graph1 Graph1; 50 54 typedef _Graph2 Graph2; … … 60 64 class Node : public Graph1Node, public Graph2Node { 61 65 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>; 62 template <typename Value> friend class NodeMap;66 template <typename _Value> friend class NodeMap; 63 67 protected: 64 68 bool backward; //true, iff backward … … 73 77 Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { } 74 78 bool operator==(const Node& v) const { 75 return (this>backward==v.backward && 76 static_cast<Graph1Node>(*this)== 77 static_cast<Graph1Node>(v) && 78 static_cast<Graph2Node>(*this)== 79 static_cast<Graph2Node>(v)); 79 if (backward) 80 return (v.backward && 81 static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v)); 82 else 83 return (!v.backward && 84 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 80 85 } 81 86 bool operator!=(const Node& v) const { 82 return (this>backward!=v.backward  83 static_cast<Graph1Node>(*this)!= 84 static_cast<Graph1Node>(v)  85 static_cast<Graph2Node>(*this)!= 86 static_cast<Graph2Node>(v)); 87 return !(*this==v); 87 88 } 88 89 }; … … 119 120 120 121 template <typename _Value> 121 class NodeMap : public Parent1::template NodeMap<_Value>, 122 public Parent2::template NodeMap<_Value> { 123 typedef typename Parent1::template NodeMap<_Value> ParentMap1; 124 typedef typename Parent2::template NodeMap<_Value> ParentMap2; 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; 125 128 public: 126 129 typedef _Value Value; 127 130 typedef Node Key; 128 131 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : 129 ParentMap1(gw), ParentMap2(gw) { } 132 forward_map(*(gw.Parent1::graph)), 133 backward_map(*(gw.Parent2::graph)) { } 130 134 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, 131 135 const _Value& value) : 132 ParentMap1(gw, value), ParentMap2(gw, value) { } 136 forward_map(*(gw.Parent1::graph), value), 137 backward_map(*(gw.Parent2::graph), value) { } 133 138 _Value operator[](const Node& n) const { 134 139 if (!n.backward) 135 return ParentMap1::operator[](n);136 else 137 return ParentMap2::operator[](n);140 return forward_map[n]; 141 else 142 return backward_map[n]; 138 143 } 139 144 void set(const Node& n, const _Value& value) { 140 145 if (!n.backward) 141 ParentMap1::set(n, value);142 else 143 ParentMap2::set(n, value);146 forward_map.set(n, value); 147 else 148 backward_map.set(n, value); 144 149 } 145 150 // using ParentMap1::operator[]; … … 149 154 }; 150 155 151 //not yet working 156 157 /*! A graph wrapper base class 158 for merging the nodeset of two nodedisjoint graphs 159 into the nodeset of one graph. 160 Specialization for the case when _Graph1::Node are the same _Graph2::Node. 161 */ 152 162 template <typename _Graph1, typename _Graph2> 153 163 class MergeNodeGraphWrapperBase< … … 155 165 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : 156 166 public P1<_Graph1>, public P2<_Graph2> { 157 public 158 void printNode() const { std::cout << "same" << std::endl; }167 public: 168 static void printNode() { std::cout << "node: same" << std::endl; } 159 169 typedef _Graph1 Graph1; 160 170 typedef _Graph2 Graph2; … … 166 176 MergeNodeGraphWrapperBase() { } 167 177 public: 168 class Node { }; 178 template <typename _Value> class NodeMap; 179 180 class Node : public Graph1Node { 181 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>; 182 template <typename _Value> friend class NodeMap; 183 protected: 184 bool backward; //true, iff backward 185 public: 186 Node() { } 187 /// \todo =false is needed, or causes problems? 188 /// If \c _backward is false, then we get an edge corresponding to the 189 /// original one, otherwise its oppositely directed pair is obtained. 190 Node(const Graph1Node& n1, 191 const Graph2Node& n2, bool _backward) : 192 Graph1Node(!backward ? n1 : n2), backward(_backward) { } 193 Node(Invalid i) : Graph1Node(i), backward(true) { } 194 bool operator==(const Node& v) const { 195 return (backward==v.backward && 196 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v)); 197 } 198 bool operator!=(const Node& v) const { 199 return !(*this==v); 200 } 201 }; 202 203 //typedef void Edge; 169 204 class Edge { }; 170 void first() const; 171 void next() const; 172 }; 173 174 //not yet working 205 206 void first(Node& i) const { 207 Parent1::graph>first(*static_cast<Graph1Node*>(&i)); 208 i.backward=false; 209 if (*static_cast<Graph1Node*>(&i)==INVALID) { 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 nodeset of two nodedisjoint graphs 271 into the nodeset of one graph. 272 Specialization for the case when 273 _Graph1::Node are base and derived _Graph2::Node. 274 NOT YET IMPLEMENTED 275 */ 175 276 template <typename _Graph1, typename _Graph2> 176 277 class MergeNodeGraphWrapperBase< … … 179 280 public P1<_Graph1>, public P2<_Graph2> { 180 281 public : 181 void printNode() const { std::cout << "2. nagyobb" << std::endl; }282 static void printNode() { std::cout << "node: 2nd is derived" << std::endl; } 182 283 typedef _Graph1 Graph1; 183 284 typedef _Graph2 Graph2; … … 202 303 public P1<_Graph1>, public P2<_Graph2> { 203 304 public : 204 void printNode() const { std::cout << "1. nagyobb" << std::endl; }305 static void printNode() { std::cout << "node: 1st is derived" << std::endl; } 205 306 typedef _Graph1 Graph1; 206 307 typedef _Graph2 Graph2; … … 219 320 220 321 322 /*! A graph wrapper class 323 fors merging the nodeset of two nodedisjoint graphs 324 into one nodeset. It does not satisfy 325 StaticGraph concept as it has no edgeset which 326 works together with the nodeset. 327 */ 221 328 template <typename _Graph1, typename _Graph2> 222 329 class MergeNodeGraphWrapper : public … … 237 344 238 345 239 /*! A base class for merging the nodesets and edgesets of 346 /*! A grah wrapper base class 347 for merging the nodesets and edgesets of 240 348 two nodedisjoint graphs 241 349 into one graph. 350 Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge. 242 351 */ 243 352 template <typename _Graph1, typename _Graph2, typename Enable=void> … … 245 354 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { 246 355 public: 247 void printEdge() const { std::cout << "generic" << std::endl; }356 static void printEdge() { std::cout << "edge: generic" << std::endl; } 248 357 typedef _Graph1 Graph1; 249 358 typedef _Graph2 Graph2; … … 264 373 class Edge : public Graph1Edge, public Graph2Edge { 265 374 friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>; 266 template <typename Value> friend class EdgeMap;375 template <typename _Value> friend class EdgeMap; 267 376 protected: 268 377 bool backward; //true, iff backward … … 277 386 Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { } 278 387 bool operator==(const Edge& v) const { 279 return (this>backward==v.backward && 280 static_cast<Graph1Edge>(*this)== 281 static_cast<Graph1Edge>(v) && 282 static_cast<Graph2Edge>(*this)== 283 static_cast<Graph2Edge>(v)); 388 if (backward) 389 return (v.backward && 390 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 391 else 392 return (!v.backward && 393 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 284 394 } 285 395 bool operator!=(const Edge& v) const { 286 return (this>backward!=v.backward  287 static_cast<Graph1Edge>(*this)!= 288 static_cast<Graph1Edge>(v)  289 static_cast<Graph2Edge>(*this)!= 290 static_cast<Graph2Edge>(v)); 396 return !(*this==v); 291 397 } 292 398 }; … … 382 488 383 489 template <typename _Value> 384 class EdgeMap : public Parent1::template EdgeMap<_Value>, 385 public Parent2::template EdgeMap<_Value> { 386 typedef typename Parent1::template EdgeMap<_Value> ParentMap1; 387 typedef typename Parent2::template EdgeMap<_Value> ParentMap2; 490 class EdgeMap { 491 protected: 492 typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1; 493 typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2; 494 ParentMap1 forward_map; 495 ParentMap2 backward_map; 388 496 public: 389 497 typedef _Value Value; 390 498 typedef Edge Key; 391 499 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : 392 ParentMap1(gw), ParentMap2(gw) { } 500 forward_map(*(gw.Parent1::graph)), 501 backward_map(*(gw.Parent2::graph)) { } 393 502 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, 394 503 const _Value& value) : 395 ParentMap1(gw, value), ParentMap2(gw, value) { } 504 forward_map(*(gw.Parent1::graph), value), 505 backward_map(*(gw.Parent2::graph), value) { } 396 506 _Value operator[](const Edge& n) const { 397 507 if (!n.backward) 398 return ParentMap1::operator[](n);399 else 400 return ParentMap2::operator[](n);508 return forward_map[n]; 509 else 510 return backward_map[n]; 401 511 } 402 512 void set(const Edge& n, const _Value& value) { 403 513 if (!n.backward) 404 ParentMap1::set(n, value);405 else 406 ParentMap2::set(n, value);514 forward_map.set(n, value); 515 else 516 backward_map.set(n, value); 407 517 } 408 518 // using ParentMap1::operator[]; … … 413 523 414 524 525 /*! A graph wrapper base class 526 for merging the nodesets and edgesets of 527 two nodedisjoint graphs 528 into one graph. 529 Specialization for the case when _Graph1::Edge and _Graph2::Edge 530 are the same. 531 */ 532 template <typename _Graph1, typename _Graph2> 533 class MergeEdgeGraphWrapperBase< 534 _Graph1, _Graph2, typename boost::enable_if< 535 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : 536 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> { 537 public: 538 static void printEdge() { std::cout << "edge: same" << std::endl; } 539 typedef _Graph1 Graph1; 540 typedef _Graph2 Graph2; 541 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent; 542 typedef typename Parent::Parent1 Parent1; 543 typedef typename Parent::Parent2 Parent2; 544 // typedef P1<_Graph1> Parent1; 545 // typedef P2<_Graph2> Parent2; 546 typedef typename Parent1::Edge Graph1Edge; 547 typedef typename Parent2::Edge Graph2Edge; 548 protected: 549 MergeEdgeGraphWrapperBase() { } 550 public: 551 template <typename _Value> class EdgeMap; 552 553 typedef typename Parent::Node Node; 554 555 class Edge : public Graph1Edge { 556 friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>; 557 template <typename _Value> friend class EdgeMap; 558 protected: 559 bool backward; //true, iff backward 560 public: 561 Edge() { } 562 /// \todo =false is needed, or causes problems? 563 /// If \c _backward is false, then we get an edge corresponding to the 564 /// original one, otherwise its oppositely directed pair is obtained. 565 Edge(const Graph1Edge& n1, 566 const Graph2Edge& n2, bool _backward) : 567 Graph1Edge(!backward ? n1 : n2), backward(_backward) { } 568 Edge(Invalid i) : Graph1Edge(i), backward(true) { } 569 bool operator==(const Edge& v) const { 570 return (backward==v.backward && 571 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 572 } 573 bool operator!=(const Edge& v) const { 574 return !(*this==v); 575 } 576 }; 577 578 using Parent::first; 579 void first(Edge& i) const { 580 Parent1::graph>first(*static_cast<Graph1Edge*>(&i)); 581 i.backward=false; 582 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 583 Parent2::graph>first(*static_cast<Graph1Edge*>(&i)); 584 i.backward=true; 585 } 586 } 587 void firstIn(Edge& i, const Node& n) const { 588 Parent1::graph>firstIn(*static_cast<Graph1Edge*>(&i), n); 589 i.backward=false; 590 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 591 Parent2::graph>firstIn(*static_cast<Graph1Edge*>(&i), n); 592 i.backward=true; 593 } 594 } 595 void firstOut(Edge& i, const Node& n) const { 596 Parent1::graph>firstOut(*static_cast<Graph1Edge*>(&i), n); 597 i.backward=false; 598 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 599 Parent2::graph>firstOut(*static_cast<Graph1Edge*>(&i), n); 600 i.backward=true; 601 } 602 } 603 604 using Parent::next; 605 void next(Edge& i) const { 606 if (!(i.backward)) { 607 Parent1::graph>next(*static_cast<Graph1Edge*>(&i)); 608 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 609 Parent2::graph>first(*static_cast<Graph1Edge*>(&i)); 610 i.backward=true; 611 } 612 } else { 613 Parent2::graph>next(*static_cast<Graph1Edge*>(&i)); 614 } 615 } 616 void nextIn(Edge& i) const { 617 if (!(i.backward)) { 618 Parent1::graph>nextIn(*static_cast<Graph1Edge*>(&i)); 619 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 620 Parent2::graph>first(*static_cast<Graph1Edge*>(&i)); 621 i.backward=true; 622 } 623 } else { 624 Parent2::graph>nextIn(*static_cast<Graph1Edge*>(&i)); 625 } 626 } 627 void nextOut(Edge& i) const { 628 if (!(i.backward)) { 629 Parent1::graph>nextOut(*static_cast<Graph1Edge*>(&i)); 630 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 631 Parent2::graph>first(*static_cast<Graph1Edge*>(&i)); 632 i.backward=true; 633 } 634 } else { 635 Parent2::graph>nextOut(*static_cast<Graph1Edge*>(&i)); 636 } 637 } 638 639 Node source(const Edge& i) const { 640 if (!(i.backward)) { 641 return 642 Node(Parent1::graph>source(i), INVALID, false); 643 } else { 644 return 645 Node(INVALID, Parent2::graph>source(i), true); 646 } 647 } 648 649 Node target(const Edge& i) const { 650 if (!(i.backward)) { 651 return 652 Node(Parent1::graph>target(i), INVALID, false); 653 } else { 654 return 655 Node(INVALID, Parent2::graph>target(i), true); 656 } 657 } 658 659 using Parent::id; 660 int id(const Edge& n) const { 661 if (!n.backward) 662 return this>Parent1::graph>id(n); 663 else 664 return this>Parent2::graph>id(n); 665 } 666 667 template <typename _Value> 668 class EdgeMap { 669 protected: 670 typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1; 671 typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2; 672 ParentMap1 forward_map; 673 ParentMap2 backward_map; 674 public: 675 typedef _Value Value; 676 typedef Edge Key; 677 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) : 678 forward_map(*(gw.Parent1::graph)), 679 backward_map(*(gw.Parent2::graph)) { } 680 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw, 681 const _Value& value) : 682 forward_map(*(gw.Parent1::graph), value), 683 backward_map(*(gw.Parent2::graph), value) { } 684 _Value operator[](const Edge& n) const { 685 if (!n.backward) 686 return forward_map[n]; 687 else 688 return backward_map[n]; 689 } 690 void set(const Edge& n, const _Value& value) { 691 if (!n.backward) 692 forward_map.set(n, value); 693 else 694 backward_map.set(n, value); 695 } 696 // using ParentMap1::operator[]; 697 // using ParentMap2::operator[]; 698 }; 699 700 }; 701 702 703 /*! A graph wrapper class 704 for merging the nodesets and edgesets of 705 two nodedisjoint graphs 706 into one graph. 707 */ 415 708 template <typename _Graph1, typename _Graph2> 416 709 class MergeEdgeGraphWrapper : public … … 431 724 432 725 726 /*! A graph wrapper base class for the following functionality. 727 If a bijection is given between the nodesets of two graphs, 728 then the second one can be considered as a new edgeset 729 over th first nodeset. 730 */ 433 731 template <typename _Graph, typename _EdgeSetGraph> 434 732 class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> { … … 508 806 bool backward(const Edge& e) const { return edge_set_graph>backward(e); } 509 807 510 using Parent::id;808 int id(const Node& e) const { return Parent::id(e); } 511 809 int id(const Edge& e) const { return edge_set_graph>id(e); } 512 810 … … 527 825 }; 528 826 827 828 /*! A graph wrapper class for the following functionality. 829 If a bijection is given between the nodesets of two graphs, 830 then the second one can be considered as a new edgeset 831 over th first nodeset. 832 */ 529 833 template <typename _Graph, typename _EdgeSetGraph> 530 834 class NewEdgeSetGraphWrapper : … … 552 856 }; 553 857 858 859 /*! A graph wrapper base class 860 for merging graphs of type _Graph1 and _Graph2 861 which are given on the same nodeset 862 (specially on the nodeset of Graph1) 863 into one graph. 864 In an other point of view, _Graph1 is extended with 865 the edgeset of _Graph2. 866 */ 867 template <typename _Graph1, typename _Graph2, typename Enable=void> 868 class AugmentingGraphWrapperBase : 869 public P1<_Graph1> { 870 public: 871 void printAugment() const { std::cout << "generic" << std::endl; } 872 typedef _Graph1 Graph1; 873 typedef _Graph2 Graph2; 874 typedef P1<_Graph1> Parent1; 875 typedef P2<_Graph2> Parent2; 876 typedef typename Parent1::Edge Graph1Edge; 877 typedef typename Parent2::Edge Graph2Edge; 878 protected: 879 AugmentingGraphWrapperBase() { } 880 _Graph2* graph2; 881 void setGraph2(_Graph2& _graph2) { graph2=&_graph2; } 882 public: 883 884 template <typename _Value> class EdgeMap; 885 886 typedef typename Parent1::Node Node; 887 888 class Edge : public Graph1Edge, public Graph2Edge { 889 friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>; 890 template <typename _Value> friend class EdgeMap; 891 protected: 892 bool backward; //true, iff backward 893 public: 894 Edge() { } 895 /// \todo =false is needed, or causes problems? 896 /// If \c _backward is false, then we get an edge corresponding to the 897 /// original one, otherwise its oppositely directed pair is obtained. 898 Edge(const Graph1Edge& n1, 899 const Graph2Edge& n2, bool _backward) : 900 Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { } 901 Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { } 902 bool operator==(const Edge& v) const { 903 if (backward) 904 return (v.backward && 905 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v)); 906 else 907 return (!v.backward && 908 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v)); 909 } 910 bool operator!=(const Edge& v) const { 911 return !(*this==v); 912 } 913 }; 914 915 using Parent1::first; 916 void first(Edge& i) const { 917 Parent1::graph>first(*static_cast<Graph1Edge*>(&i)); 918 i.backward=false; 919 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 920 graph2>first(*static_cast<Graph2Edge*>(&i)); 921 i.backward=true; 922 } 923 } 924 void firstIn(Edge& i, const Node& n) const { 925 Parent1::graph>firstIn(*static_cast<Graph1Edge*>(&i), n); 926 i.backward=false; 927 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 928 graph2>firstIn(*static_cast<Graph2Edge*>(&i), n); 929 i.backward=true; 930 } 931 } 932 void firstOut(Edge& i, const Node& n) const { 933 Parent1::graph>firstOut(*static_cast<Graph1Edge*>(&i), n); 934 i.backward=false; 935 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 936 graph2>firstOut(*static_cast<Graph2Edge*>(&i), n); 937 i.backward=true; 938 } 939 } 940 941 using Parent1::next; 942 void next(Edge& i) const { 943 if (!(i.backward)) { 944 Parent1::graph>next(*static_cast<Graph1Edge*>(&i)); 945 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 946 graph2>first(*static_cast<Graph2Edge*>(&i)); 947 i.backward=true; 948 } 949 } else { 950 graph2>next(*static_cast<Graph2Edge*>(&i)); 951 } 952 } 953 void nextIn(Edge& i) const { 954 if (!(i.backward)) { 955 Parent1::graph>nextIn(*static_cast<Graph1Edge*>(&i)); 956 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 957 graph2>first(*static_cast<Graph2Edge*>(&i)); 958 i.backward=true; 959 } 960 } else { 961 graph2>nextIn(*static_cast<Graph2Edge*>(&i)); 962 } 963 } 964 void nextOut(Edge& i) const { 965 if (!(i.backward)) { 966 Parent1::graph>nextOut(*static_cast<Graph1Edge*>(&i)); 967 if (*static_cast<Graph1Edge*>(&i)==INVALID) { 968 graph2>first(*static_cast<Graph2Edge*>(&i)); 969 i.backward=true; 970 } 971 } else { 972 graph2>nextOut(*static_cast<Graph2Edge*>(&i)); 973 } 974 } 975 976 Node source(const Edge& i) const { 977 if (!(i.backward)) { 978 return Parent1::graph>source(i); 979 } else { 980 return graph2>source(i); 981 } 982 } 983 984 Node target(const Edge& i) const { 985 if (!(i.backward)) { 986 return Parent1::graph>target(i); 987 } else { 988 return graph2>target(i); 989 } 990 } 991 992 int id(const Node& n) const { 993 return Parent1::id(n); 994 }; 995 int id(const Edge& n) const { 996 if (!n.backward) 997 return this>Parent1::graph>id(n); 998 else 999 return this>graph2>id(n); 1000 } 1001 1002 template <typename _Value> 1003 class EdgeMap { 1004 protected: 1005 typedef typename _Graph1::template EdgeMap<_Value> ParentMap1; 1006 typedef typename _Graph2::template EdgeMap<_Value> ParentMap2; 1007 ParentMap1 forward_map; 1008 ParentMap2 backward_map; 1009 public: 1010 typedef _Value Value; 1011 typedef Edge Key; 1012 EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) : 1013 forward_map(*(gw.Parent1::graph)), 1014 backward_map(*(gw.graph2)) { } 1015 EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw, 1016 const _Value& value) : 1017 forward_map(*(gw.Parent1::graph), value), 1018 backward_map(*(gw.graph2), value) { } 1019 _Value operator[](const Edge& n) const { 1020 if (!n.backward) 1021 return forward_map[n]; 1022 else 1023 return backward_map[n]; 1024 } 1025 void set(const Edge& n, const _Value& value) { 1026 if (!n.backward) 1027 forward_map.set(n, value); 1028 else 1029 backward_map.set(n, value); 1030 } 1031 // using ParentMap1::operator[]; 1032 // using ParentMap2::operator[]; 1033 }; 1034 1035 }; 1036 1037 1038 /*! A graph wrapper class 1039 for merging two graphs (of type _Graph1 and _Graph2) 1040 with the same nodeset 1041 (specially on the nodeset of Graph1) 1042 into one graph. 1043 In an other point of view, _Graph1 is extended with 1044 the edgeset of _Graph2. 1045 */ 1046 template <typename _Graph1, typename _Graph2> 1047 class AugmentingGraphWrapper : public 1048 IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > { 1049 public: 1050 typedef 1051 IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > 1052 Parent; 1053 typedef _Graph1 Graph1; 1054 typedef _Graph2 Graph2; 1055 protected: 1056 AugmentingGraphWrapper() { } 1057 public: 1058 AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 1059 setGraph(_graph1); 1060 setGraph2(_graph2); 1061 } 1062 }; 1063 554 1064 } //namespace lemon 555 1065 
src/work/marci/merge_node_graph_wrapper_test.cc
r1009 r1013 5 5 #include <lemon/smart_graph.h> 6 6 #include <lemon/dimacs.h> 7 #include <lemon/full_graph.h> 7 8 #include <merge_node_graph_wrapper.h> 8 9 … … 22 23 }; 23 24 24 int main() { 25 typedef SmartGraph Graph1; 26 typedef ListGraph Graph2; 27 28 { 29 checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >(); 30 } 31 { 32 checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >(); 33 } 34 35 Graph1 g; 36 Graph2 h; 37 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; 38 GW gw(g, h); 39 40 std::ifstream f1("graph1.dim"); 41 std::ifstream f2("graph2.dim"); 42 readDimacs(f1, g); 43 readDimacs(f2, h); 44 { 45 46 // Graph1::Node n1=g.addNode(); 47 // Graph1::Node n2=g.addNode(); 48 // Graph1::Node n3=g.addNode(); 49 // Graph2::Node n4=h.addNode(); 50 // Graph2::Node n5=h.addNode(); 51 // Graph2::Node n6=h.addNode(); 52 // Graph1::Edge e1=g.addEdge(n1, n2); 53 // Graph1::Edge e2=g.addEdge(n1, n3); 54 // Graph2::Edge e3=h.addEdge(n4, n5); 55 // Graph2::Edge e4=h.addEdge(n4, n5); 56 //GW::NodeIt n(gw) 57 cout << "1st graph" << endl; 25 template <typename Graph> 26 void printGraph(const Graph& g) { 58 27 cout << " nodes:" << endl; 59 for ( Graph1::NodeIt n(g); n!=INVALID; ++n) {28 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { 60 29 cout << " " << g.id(n) << endl; 61 30 } 62 31 cout << " edges:" << endl; 63 for ( Graph1::EdgeIt n(g); n!=INVALID; ++n) {32 for (typename Graph::EdgeIt n(g); n!=INVALID; ++n) { 64 33 cout << " " << g.id(n) << ": " 65 34 << g.id(g.source(n)) << ">" << g.id(g.target(n)) << endl; 66 } 67 cout << "2nd graph" << endl; 68 cout << " nodes:" << endl; 69 for (Graph2::NodeIt n(h); n!=INVALID; ++n) { 70 cout << " " << h.id(n) << endl; 71 } 72 cout << " edges:" << endl; 73 for (Graph2::EdgeIt n(h); n!=INVALID; ++n) { 74 cout << " " << h.id(n) << ": " 75 << h.id(h.source(n)) << ">" << h.id(h.target(n)) << endl; 76 } 77 cout << "merged graph" << endl; 78 cout << " nodes:" << endl; 79 for (GW::NodeIt n(gw); n!=INVALID; ++n) { 80 cout << " "<< gw.id(n) << endl; 81 } 82 cout << " edges:" << endl; 83 for (GW::EdgeIt n(gw); n!=INVALID; ++n) { 84 cout << " " << gw.id(n) << ": " 85 << gw.id(gw.source(n)) << ">" << gw.id(gw.target(n)) << endl; 35 } 36 } 37 38 int main() { 39 { 40 cout << "FIRST TEST" << endl; 41 typedef SmartGraph Graph1; 42 typedef ListGraph Graph2; 43 44 { 45 checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >(); 46 MergeEdgeGraphWrapper<Graph1, Graph2>::printNode(); 47 MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge(); 48 checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >(); 49 MergeEdgeGraphWrapper<Graph1, Graph1>::printNode(); 50 MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge(); 51 } 52 53 Graph1 g1; 54 Graph2 g2; 55 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; 56 GW gw(g1, g2); 57 58 std::ifstream f1("graph1.dim"); 59 std::ifstream f2("graph2.dim"); 60 readDimacs(f1, g1); 61 readDimacs(f2, g2); 62 63 cout << "1st graph" << endl; 64 printGraph(g1); 65 66 cout << "2nd graph" << endl; 67 printGraph(g2); 68 69 cout << "merged graph" << endl; 70 printGraph(gw); 71 86 72 } 87 73 88 GW::NodeMap<int> nm(gw); 89 int i=0; 90 for (GW::NodeIt n(gw); n!=INVALID; ++n) { 91 ++i; 92 nm.set(n, i); 93 } 94 for (Graph1::NodeIt n(g); n!=INVALID; ++n) { 95 cout << nm[GW::Node(n,INVALID,false)] << endl; 96 } 97 for (Graph2::NodeIt n(h); n!=INVALID; ++n) { 98 cout << nm[GW::Node(INVALID,n,true)] << endl; 74 75 { 76 cout << "SECOND TEST" << endl; 77 typedef SmartGraph Graph1; 78 { 79 checkConcept<StaticGraph, Graph1>(); 80 } 81 82 Graph1 g1; 83 84 FullGraph pre_g2(2); 85 ConstMap<FullGraph::Edge, bool> const_false_map(false); 86 typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> > 87 Graph2; 88 { 89 checkConcept<StaticGraph, Graph2>(); 90 } 91 92 Graph2 g2(pre_g2, const_false_map); 93 94 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; 95 { 96 checkConcept<StaticGraph, GW>(); 97 } 98 GW gw(g1, g2); 99 GW::Node sw; 100 GW::Node tw; 101 { 102 Graph2::NodeIt k(g2); 103 sw=GW::Node(INVALID, k, true); 104 ++k; 105 tw=GW::Node(INVALID, k, true); 106 } 107 108 std::ifstream f1("graph2.dim"); 109 readDimacs(f1, g1); 110 111 cout << "1st graph" << endl; 112 printGraph(g1); 113 114 cout << "2nd graph" << endl; 115 printGraph(g2); 116 117 cout << "merged graph" << endl; 118 printGraph(gw); 119 120 typedef ListGraph Graph3; 121 Graph3 g3; 122 GW::NodeMap<Graph3::Node> gwn(gw); 123 Graph3::NodeMap<GW::Node> g3n(g3); 124 for (GW::NodeIt n(gw); n!=INVALID; ++n) { 125 Graph3::Node m=g3.addNode(); 126 gwn.set(n, m); 127 g3n.set(m, n); 128 } 129 130 typedef NewEdgeSetGraphWrapper<GW, Graph3> GWW; 131 { 132 checkConcept<StaticGraph, GWW>(); 133 } 134 135 GWW gww(gw, g3, gwn, g3n); 136 137 for (Graph1::NodeIt n(g1); n!=INVALID; ++n) { 138 g3.addEdge(gwn[sw], gwn[GW::Node(n,INVALID,false)]); 139 } 140 141 // for (Graph1::NodeIt n(g1); n!=INVALID; ++n) { 142 // gww.addEdge(sw, GW::Node(n,INVALID,false)); 143 // } 144 145 cout << "new edges" << endl; 146 printGraph(g3); 147 148 cout << "new edges in the new graph" << endl; 149 printGraph(gww); 150 151 typedef AugmentingGraphWrapper<GW, GWW> GWWW; 152 { 153 checkConcept<StaticGraph, GWWW>(); 154 } 155 GWWW gwww(gw, gww); 156 157 cout << "new edges merged into the original graph" << endl; 158 printGraph(gwww); 159 99 160 } 100 161 101 gw.printNode();102 103 {104 // typedef SmartGraph Graph1;105 typedef ListGraph Graph1;106 typedef ListGraph Graph2;107 Graph1 g;108 Graph2 h;109 typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;110 GW gw(g, h);111 gw.printNode();112 }113 {114 // typedef SmartGraph Graph1;115 typedef Graph3 Graph1;116 typedef ListGraph Graph2;117 Graph1 g;118 Graph2 h;119 typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;120 GW gw(g, h);121 gw.printNode();122 }123 {124 // typedef SmartGraph Graph1;125 typedef ListGraph Graph1;126 typedef Graph3 Graph2;127 Graph1 g;128 Graph2 h;129 typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;130 GW gw(g, h);131 gw.printNode();132 }133 }134 {135 Graph1 g;136 Graph2 h;137 typedef Graph1::Node Node1;138 typedef Graph2::Node Node2;139 typedef NewEdgeSetGraphWrapper<Graph1, Graph2> GW;140 Graph1::NodeMap<Graph2::Node> e_node(g);141 Graph2::NodeMap<Graph1::Node> n_node(h);142 GW gw(g, h, e_node, n_node);143 for (int i=0; i<4; ++i) {144 Node1 n=g.addNode();145 e_node.set(n, INVALID);146 }147 for (int i=0; i<4; ++i) {148 Graph1::Node n1=g.addNode();149 Graph2::Node n2=h.addNode();150 e_node.set(n1, n2);151 n_node.set(n2, n1);152 }153 for (Graph2::NodeIt n(h); n!=INVALID; ++n)154 for (Graph2::NodeIt m(h); m!=INVALID; ++m)155 if ((h.id(n)+h.id(m))%3==0) h.addEdge(n, m);156 // Graph1::NodeIt n(g);157 // Node1 n1=n;158 // Node1 n2=++n;159 // Node1 n3=++n;160 // Node1 n4=n;161 // gw.addEdge(n1, n2);162 // gw.addEdge(n1, n2);163 // for (EdgeIt(e))164 // Graph1::Node n1=g.addNode();165 // Graph1::Node n2=g.addNode();166 // Graph1::Node n3=g.addNode();167 // Graph2::Node n4=h.addNode();168 // Graph2::Node n5=h.addNode();169 for (GW::EdgeIt e(gw); e!=INVALID; ++e)170 cout << gw.id(e) << endl;171 for (GW::NodeIt n(gw); n!=INVALID; ++n) {172 if (e_node[n]==INVALID) {173 cout<<gw.id(n)<<" INVALID"<<endl;174 } else {175 cout <<gw.id(n)<<" "<<h.id(e_node[n])<<" out_edges: ";176 // cout << &e_node << endl;177 //cout << &n_node << endl;178 for (GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) {179 cout<<gw.id(e)<<" ";180 }181 cout<< endl;182 }183 }184 }185 162 }
Note: See TracChangeset
for help on using the changeset viewer.