Changeset 1013:b3bdd856faf4 in lemon-0.x for src/work
- Timestamp:
- 11/20/04 15:09:27 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1403
- Location:
- src/work/marci
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
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 node-set of two node-disjoint graphs 42 into the node-set of one graph. 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. 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 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 */ 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 node-set of two node-disjoint graphs 271 into the node-set 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 node-set of two node-disjoint graphs 324 into one node-set. It does not satisfy 325 StaticGraph concept as it has no edge-set which 326 works together with the node-set. 327 */ 221 328 template <typename _Graph1, typename _Graph2> 222 329 class MergeNodeGraphWrapper : public … … 237 344 238 345 239 /*! A base class for merging the node-sets and edge-sets of 346 /*! A grah wrapper base class 347 for merging the node-sets and edge-sets of 240 348 two node-disjoint 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 node-sets and edge-sets of 527 two node-disjoint 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 node-sets and edge-sets of 705 two node-disjoint 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 node-sets of two graphs, 728 then the second one can be considered as a new edge-set 729 over th first node-set. 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 node-sets of two graphs, 830 then the second one can be considered as a new edge-set 831 over th first node-set. 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 node-set 862 (specially on the node-set of Graph1) 863 into one graph. 864 In an other point of view, _Graph1 is extended with 865 the edge-set 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 node-set 1041 (specially on the node-set of Graph1) 1042 into one graph. 1043 In an other point of view, _Graph1 is extended with 1044 the edge-set 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.