Changeset 569:3b6afd33c221 in lemon0.x
 Timestamp:
 05/07/04 09:44:44 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@744
 Location:
 src
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/graph_wrapper.h
r565 r569 219 219 }; 220 220 221 222 221 223 /// A graph wrapper which reverses the orientation of the edges. 222 224 … … 292 294 293 295 }; 296 297 294 298 295 299 /// Wrapper for hiding nodes and edges from a graph. … … 464 468 }; 465 469 470 471 466 472 /// A wrapper for forgetting the orientation of a graph. 467 473 … … 561 567 }; 562 568 563 564 565 /// A wrapper for composing the residual graph for directed flow and circulation problems. 566 567 /// A wrapper for composing the residual graph for directed flow and circulation problems. 568 template<typename Graph, typename Number, 569 typename CapacityMap, typename FlowMap> 570 class ResGraphWrapper : public GraphWrapper<Graph> { 569 570 571 /// A wrapper for composing bidirected graph from a directed one. 572 /// experimental, for fezso's sake. 573 template<typename Graph> 574 class BidirGraphWrapper : public GraphWrapper<Graph> { 571 575 protected: 572 const CapacityMap* capacity;573 FlowMap* flow;574 575 ResGraphWrapper() : GraphWrapper<Graph>(0),576 capacity(0), flow(0){ }577 void setCapacityMap(const CapacityMap& _capacity) {578 capacity=&_capacity;579 }580 void setFlowMap(FlowMap& _flow) {581 flow=&_flow;582 }576 //const CapacityMap* capacity; 577 //FlowMap* flow; 578 579 BidirGraphWrapper() : GraphWrapper<Graph>()/*, 580 capacity(0), flow(0)*/ { } 581 // void setCapacityMap(const CapacityMap& _capacity) { 582 // capacity=&_capacity; 583 // } 584 // void setFlowMap(FlowMap& _flow) { 585 // flow=&_flow; 586 // } 583 587 584 588 public: 585 589 586 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,587 FlowMap& _flow) :588 GraphWrapper<Graph>(_graph) , capacity(&_capacity), flow(&_flow){ }590 BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 591 FlowMap& _flow*/) : 592 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } 589 593 590 594 class Edge; … … 596 600 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 597 601 class Edge : public Graph::Edge { 598 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;602 friend class BidirGraphWrapper<Graph>; 599 603 protected: 600 604 bool backward; //true, iff backward … … 619 623 620 624 class OutEdgeIt { 621 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;625 friend class BidirGraphWrapper<Graph>; 622 626 protected: 623 627 typename Graph::OutEdgeIt out; … … 630 634 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 631 635 //the unique invalid iterator 632 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {636 OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 633 637 backward=false; 634 resG.graph>first(out, v);635 while( resG.graph>valid(out) && !(resG.resCap(*this)>0) ) { resG.graph>next(out); }636 if (! resG.graph>valid(out)) {638 _G.graph>first(out, v); 639 while(_G.graph>valid(out) && !_G.enabled(*this)) { _G.graph>next(out); } 640 if (!_G.graph>valid(out)) { 637 641 backward=true; 638 resG.graph>first(in, v);639 while( resG.graph>valid(in) && !(resG.resCap(*this)>0) ) { resG.graph>next(in); }642 _G.graph>first(in, v); 643 while(_G.graph>valid(in) && !_G.enabled(*this)) { _G.graph>next(in); } 640 644 } 641 645 } … … 653 657 654 658 class InEdgeIt { 655 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;659 friend class BidirGraphWrapper<Graph>; 656 660 protected: 657 661 typename Graph::OutEdgeIt out; … … 664 668 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 665 669 //the unique invalid iterator 666 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {670 InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 667 671 backward=false; 668 resG.graph>first(in, v);669 while( resG.graph>valid(in) && !(resG.resCap(*this)>0) ) { resG.graph>next(in); }670 if (! resG.graph>valid(in)) {672 _G.graph>first(in, v); 673 while(_G.graph>valid(in) && !_G.enabled(*this)) { _G.graph>next(in); } 674 if (!_G.graph>valid(in)) { 671 675 backward=true; 672 resG.graph>first(out, v);673 while( resG.graph>valid(out) && !(resG.resCap(*this)>0) ) { resG.graph>next(out); }676 _G.graph>first(out, v); 677 while(_G.graph>valid(out) && !_G.enabled(*this)) { _G.graph>next(out); } 674 678 } 675 679 } … … 687 691 688 692 class EdgeIt { 693 friend class BidirGraphWrapper<Graph>; 694 protected: 695 typename Graph::EdgeIt e; 696 bool backward; 697 public: 698 EdgeIt() { } 699 EdgeIt(const Invalid& i) : e(i), backward(true) { } 700 EdgeIt(const BidirGraphWrapper<Graph>& _G) { 701 backward=false; 702 _G.graph>first(e); 703 while (_G.graph>valid(e) && !_G.enabled(*this)) _G.graph>next(e); 704 if (!_G.graph>valid(e)) { 705 backward=true; 706 _G.graph>first(e); 707 while (_G.graph>valid(e) && !_G.enabled(*this)) _G.graph>next(e); 708 } 709 } 710 operator Edge() const { 711 return Edge(e, this>backward); 712 } 713 }; 714 715 using GraphWrapper<Graph>::first; 716 // NodeIt& first(NodeIt& i) const { 717 // i=NodeIt(*this); return i; 718 // } 719 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 720 i=OutEdgeIt(*this, p); return i; 721 } 722 // FIXME not tested 723 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 724 i=InEdgeIt(*this, p); return i; 725 } 726 EdgeIt& first(EdgeIt& i) const { 727 i=EdgeIt(*this); return i; 728 } 729 730 using GraphWrapper<Graph>::next; 731 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } 732 OutEdgeIt& next(OutEdgeIt& e) const { 733 if (!e.backward) { 734 Node v=this>graph>aNode(e.out); 735 this>graph>next(e.out); 736 while(this>graph>valid(e.out) && !enabled(e)) { 737 this>graph>next(e.out); } 738 if (!this>graph>valid(e.out)) { 739 e.backward=true; 740 this>graph>first(e.in, v); 741 while(this>graph>valid(e.in) && !enabled(e)) { 742 this>graph>next(e.in); } 743 } 744 } else { 745 this>graph>next(e.in); 746 while(this>graph>valid(e.in) && !enabled(e)) { 747 this>graph>next(e.in); } 748 } 749 return e; 750 } 751 // FIXME Not tested 752 InEdgeIt& next(InEdgeIt& e) const { 753 if (!e.backward) { 754 Node v=this>graph>aNode(e.in); 755 this>graph>next(e.in); 756 while(this>graph>valid(e.in) && !enabled(e)) { 757 this>graph>next(e.in); } 758 if (!this>graph>valid(e.in)) { 759 e.backward=true; 760 this>graph>first(e.out, v); 761 while(this>graph>valid(e.out) && !enabled(e)) { 762 this>graph>next(e.out); } 763 } 764 } else { 765 this>graph>next(e.out); 766 while(this>graph>valid(e.out) && !enabled(e)) { 767 this>graph>next(e.out); } 768 } 769 return e; 770 } 771 EdgeIt& next(EdgeIt& e) const { 772 if (!e.backward) { 773 this>graph>next(e.e); 774 while(this>graph>valid(e.e) && !enabled(e)) { 775 this>graph>next(e.e); } 776 if (!this>graph>valid(e.e)) { 777 e.backward=true; 778 this>graph>first(e.e); 779 while(this>graph>valid(e.e) && !enabled(e)) { 780 this>graph>next(e.e); } 781 } 782 } else { 783 this>graph>next(e.e); 784 while(this>graph>valid(e.e) && !enabled(e)) { 785 this>graph>next(e.e); } 786 } 787 return e; 788 } 789 790 Node tail(Edge e) const { 791 return ((!e.backward) ? this>graph>tail(e) : this>graph>head(e)); } 792 Node head(Edge e) const { 793 return ((!e.backward) ? this>graph>head(e) : this>graph>tail(e)); } 794 795 Node aNode(OutEdgeIt e) const { 796 return ((!e.backward) ? this>graph>aNode(e.out) : 797 this>graph>aNode(e.in)); } 798 Node bNode(OutEdgeIt e) const { 799 return ((!e.backward) ? this>graph>bNode(e.out) : 800 this>graph>bNode(e.in)); } 801 802 Node aNode(InEdgeIt e) const { 803 return ((!e.backward) ? this>graph>aNode(e.in) : 804 this>graph>aNode(e.out)); } 805 Node bNode(InEdgeIt e) const { 806 return ((!e.backward) ? this>graph>bNode(e.in) : 807 this>graph>bNode(e.out)); } 808 809 // int nodeNum() const { return graph>nodeNum(); } 810 //FIXME 811 void edgeNum() const { } 812 //int edgeNum() const { return graph>edgeNum(); } 813 814 815 // int id(Node v) const { return graph>id(v); } 816 817 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } 818 bool valid(Edge e) const { 819 return this>graph>valid(e); 820 //return e.forward ? graph>valid(e.out) : graph>valid(e.in); 821 } 822 823 bool forward(const Edge& e) const { return !e.backward; } 824 bool backward(const Edge& e) const { return e.backward; } 825 826 // void augment(const Edge& e, Number a) const { 827 // if (!e.backward) 828 // // flow>set(e.out, flow>get(e.out)+a); 829 // flow>set(e, (*flow)[e]+a); 830 // else 831 // // flow>set(e.in, flow>get(e.in)a); 832 // flow>set(e, (*flow)[e]a); 833 // } 834 835 bool enabled(const Edge& e) const { 836 if (!e.backward) 837 // return (capacity>get(e.out)flow>get(e.out)); 838 //return ((*capacity)[e](*flow)[e]); 839 return true; 840 else 841 // return (flow>get(e.in)); 842 //return ((*flow)[e]); 843 return true; 844 } 845 846 // Number enabled(typename Graph::OutEdgeIt out) const { 847 // // return (capacity>get(out)flow>get(out)); 848 // return ((*capacity)[out](*flow)[out]); 849 // } 850 851 // Number enabled(typename Graph::InEdgeIt in) const { 852 // // return (flow>get(in)); 853 // return ((*flow)[in]); 854 // } 855 856 template <typename T> 857 class EdgeMap { 858 typename Graph::template EdgeMap<T> forward_map, backward_map; 859 public: 860 EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } 861 EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 862 void set(Edge e, T a) { 863 if (!e.backward) 864 forward_map.set(e.out, a); 865 else 866 backward_map.set(e.in, a); 867 } 868 T operator[](Edge e) const { 869 if (!e.backward) 870 return forward_map[e.out]; 871 else 872 return backward_map[e.in]; 873 } 874 // T get(Edge e) const { 875 // if (e.out_or_in) 876 // return forward_map.get(e.out); 877 // else 878 // return backward_map.get(e.in); 879 // } 880 }; 881 }; 882 883 884 885 /// A wrapper for composing the residual graph for directed flow and circulation problems. 886 887 /// A wrapper for composing the residual graph for directed flow and circulation problems. 888 template<typename Graph, typename Number, 889 typename CapacityMap, typename FlowMap> 890 class ResGraphWrapper : public GraphWrapper<Graph> { 891 protected: 892 const CapacityMap* capacity; 893 FlowMap* flow; 894 895 ResGraphWrapper() : GraphWrapper<Graph>(0), 896 capacity(0), flow(0) { } 897 void setCapacityMap(const CapacityMap& _capacity) { 898 capacity=&_capacity; 899 } 900 void setFlowMap(FlowMap& _flow) { 901 flow=&_flow; 902 } 903 904 public: 905 906 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 907 FlowMap& _flow) : 908 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { } 909 910 class Edge; 911 class OutEdgeIt; 912 friend class Edge; 913 friend class OutEdgeIt; 914 915 typedef typename GraphWrapper<Graph>::Node Node; 916 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 917 class Edge : public Graph::Edge { 918 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 919 protected: 920 bool backward; //true, iff backward 921 // typename Graph::Edge e; 922 public: 923 Edge() { } 924 Edge(const typename Graph::Edge& _e, bool _backward) : 925 Graph::Edge(_e), backward(_backward) { } 926 Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } 927 //the unique invalid iterator 928 friend bool operator==(const Edge& u, const Edge& v) { 929 return (v.backward==u.backward && 930 static_cast<typename Graph::Edge>(u)== 931 static_cast<typename Graph::Edge>(v)); 932 } 933 friend bool operator!=(const Edge& u, const Edge& v) { 934 return (v.backward!=u.backward  935 static_cast<typename Graph::Edge>(u)!= 936 static_cast<typename Graph::Edge>(v)); 937 } 938 }; 939 940 class OutEdgeIt { 941 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 942 protected: 943 typename Graph::OutEdgeIt out; 944 typename Graph::InEdgeIt in; 945 bool backward; 946 public: 947 OutEdgeIt() { } 948 //FIXME 949 // OutEdgeIt(const Edge& e) : Edge(e) { } 950 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 951 //the unique invalid iterator 952 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 953 backward=false; 954 _G.graph>first(out, v); 955 while( _G.graph>valid(out) && !(_G.resCap(*this)>0) ) { _G.graph>next(out); } 956 if (!_G.graph>valid(out)) { 957 backward=true; 958 _G.graph>first(in, v); 959 while( _G.graph>valid(in) && !(_G.resCap(*this)>0) ) { _G.graph>next(in); } 960 } 961 } 962 operator Edge() const { 963 // Edge e; 964 // e.forward=this>forward; 965 // if (this>forward) e=out; else e=in; 966 // return e; 967 if (this>backward) 968 return Edge(in, this>backward); 969 else 970 return Edge(out, this>backward); 971 } 972 }; 973 974 class InEdgeIt { 975 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 976 protected: 977 typename Graph::OutEdgeIt out; 978 typename Graph::InEdgeIt in; 979 bool backward; 980 public: 981 InEdgeIt() { } 982 //FIXME 983 // OutEdgeIt(const Edge& e) : Edge(e) { } 984 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 985 //the unique invalid iterator 986 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 987 backward=false; 988 _G.graph>first(in, v); 989 while( _G.graph>valid(in) && !(_G.resCap(*this)>0) ) { _G.graph>next(in); } 990 if (!_G.graph>valid(in)) { 991 backward=true; 992 _G.graph>first(out, v); 993 while( _G.graph>valid(out) && !(_G.resCap(*this)>0) ) { _G.graph>next(out); } 994 } 995 } 996 operator Edge() const { 997 // Edge e; 998 // e.forward=this>forward; 999 // if (this>forward) e=out; else e=in; 1000 // return e; 1001 if (this>backward) 1002 return Edge(out, this>backward); 1003 else 1004 return Edge(in, this>backward); 1005 } 1006 }; 1007 1008 class EdgeIt { 689 1009 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>; 690 1010 protected: … … 694 1014 EdgeIt() { } 695 1015 EdgeIt(const Invalid& i) : e(i), backward(true) { } 696 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {1016 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 697 1017 backward=false; 698 resG.graph>first(e);699 while ( resG.graph>valid(e) && !(resG.resCap(*this)>0)) resG.graph>next(e);700 if (! resG.graph>valid(e)) {1018 _G.graph>first(e); 1019 while (_G.graph>valid(e) && !(_G.resCap(*this)>0)) _G.graph>next(e); 1020 if (!_G.graph>valid(e)) { 701 1021 backward=true; 702 resG.graph>first(e);703 while ( resG.graph>valid(e) && !(resG.resCap(*this)>0)) resG.graph>next(e);1022 _G.graph>first(e); 1023 while (_G.graph>valid(e) && !(_G.resCap(*this)>0)) _G.graph>next(e); 704 1024 } 705 1025 } … … 875 1195 }; 876 1196 1197 1198 877 1199 /// ErasingFirstGraphWrapper for blocking flows. 878 1200 
src/work/marci/iterator_bfs_demo.cc
r557 r569 315 315 } 316 316 317 318 319 { 320 typedef BidirGraphWrapper<const Graph> GW; 321 GW gw(G); 322 323 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 324 325 cout << "bfs and dfs iterator demo on the undirected graph" << endl; 326 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 327 cout << node_name[GW::Node(n)] << ": "; 328 cout << "out edges: "; 329 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 330 cout << edge_name[e] << " "; 331 cout << "in edges: "; 332 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 333 cout << edge_name[e] << " "; 334 cout << endl; 335 } 336 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 337 // cout << edge_name.get(e) << " "; 338 // } 339 // cout << endl; 340 341 cout << "bfs from t ..." << endl; 342 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); 343 bfs.pushAndSetReached(t); 344 while (!bfs.finished()) { 345 //cout << "edge: "; 346 if (gw.valid(GW::OutEdgeIt(bfs))) { 347 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 348 node_name[gw.aNode(bfs)] << 349 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 350 node_name[gw.bNode(bfs)] << 351 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 352 ": is not newly reached."); 353 } else { 354 cout << "invalid" << /*endl*/", " << 355 node_name[bfs.aNode()] << 356 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 357 358 "invalid."; 359 } 360 cout << endl; 361 ++bfs; 362 } 363 364 cout << " /> > "<< endl; 365 cout << " / / v1 <\\ / v3\\ "<< endl; 366 cout << " /   / /> \\ "<< endl; 367 cout << " /   /  ^ \\ "<< endl; 368 cout << "s   /   \\> t "<< endl; 369 cout << " \\   /   /> "<< endl; 370 cout << " \\  / /   / "<< endl; 371 cout << " \\ \\> v2 </ \\ v4 / "<< endl; 372 cout << " \\> > "<< endl; 373 374 cout << "dfs from t ..." << endl; 375 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); 376 dfs.pushAndSetReached(t); 377 while (!dfs.finished()) { 378 ++dfs; 379 //cout << "edge: "; 380 if (gw.valid(GW::OutEdgeIt(dfs))) { 381 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 382 node_name[gw.aNode(dfs)] << 383 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 384 node_name[gw.bNode(dfs)] << 385 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 386 ": is not newly reached."); 387 } else { 388 cout << "invalid" << /*endl*/", " << 389 node_name[dfs.aNode()] << 390 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 391 392 "invalid."; 393 } 394 cout << endl; 395 } 396 } 397 398 399 317 400 return 0; 318 401 }
Note: See TracChangeset
for help on using the changeset viewer.