Changeset 650:588ff2ca55bd in lemon0.x for src/hugo/graph_wrapper.h
 Timestamp:
 05/20/04 17:40:59 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@850
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/graph_wrapper.h
r626 r650 12 12 13 13 #include <hugo/invalid.h> 14 #include <hugo/maps.h> 14 15 //#include <iter_map.h> 15 16 … … 104 105 Node() { } 105 106 Node(const typename Graph::Node& _n) : Graph::Node(_n) { } 107 // /// \bug construction throughrthr multiple levels should be 108 // /// handled better 109 // Node(const typename ParentGraph::ParentGraph::Node& _n) : 110 // Graph::Node(_n) { } 106 111 Node(const Invalid& i) : Graph::Node(i) { } 107 112 }; … … 203 208 void clear() const { graph>clear(); } 204 209 210 bool forward(const Edge& e) const { graph>forward(e); } 211 bool backward(const Edge& e) const { graph>backward(e); } 212 213 Edge opposite(const Edge& e) const { Edge(graph>opposite(e)); } 214 205 215 template<typename T> class NodeMap : public Graph::template NodeMap<T> { 206 216 typedef typename Graph::template NodeMap<T> Parent; … … 228 238 template<typename Graph> 229 239 class RevGraphWrapper : public GraphWrapper<Graph> { 240 public: 241 typedef GraphWrapper<Graph> Parent; 230 242 protected: 231 243 RevGraphWrapper() : GraphWrapper<Graph>() { } … … 308 320 typename EdgeFilterMap> 309 321 class SubGraphWrapper : public GraphWrapper<Graph> { 322 public: 323 typedef GraphWrapper<Graph> Parent; 310 324 protected: 311 325 NodeFilterMap* node_filter_map; … … 322 336 323 337 public: 324 325 338 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 326 339 EdgeFilterMap& _edge_filter_map) : … … 497 510 template<typename Graph> 498 511 class UndirGraphWrapper : public GraphWrapper<Graph> { 512 public: 513 typedef GraphWrapper<Graph> Parent; 499 514 protected: 500 515 UndirGraphWrapper() : GraphWrapper<Graph>() { } … … 592 607 593 608 594 ///\brief A wrapper for composing bidirected graph from a directed one. 609 610 ///\brief A wrapper for composing a subgraph of a 611 /// bidirected graph composed from a directed one. 595 612 /// experimental, for fezso's sake. 596 613 /// 597 /// A wrapper for composing bidirected graph from a directed one. 614 /// A wrapper for composing a subgraps of a 615 /// bidirected graph composed from a directed one. 598 616 /// experimental, for fezso's sake. 599 617 /// A bidirected graph is composed over the directed one without physical 600 618 /// storage. As the oppositely directed edges are logically different ones 601 619 /// the maps are able to attach different values for them. 602 template<typename Graph> 603 class BidirGraphWrapper : public GraphWrapper<Graph> { 620 template<typename Graph, 621 typename ForwardFilterMap, typename BackwardFilterMap> 622 class SubBidirGraphWrapper : public GraphWrapper<Graph> { 623 public: 624 typedef GraphWrapper<Graph> Parent; 604 625 protected: 605 626 //const CapacityMap* capacity; 606 627 //FlowMap* flow; 607 628 608 BidirGraphWrapper() : GraphWrapper<Graph>()/*, 629 ForwardFilterMap* forward_filter; 630 BackwardFilterMap* backward_filter; 631 632 SubBidirGraphWrapper() : GraphWrapper<Graph>()/*, 609 633 capacity(0), flow(0)*/ { } 610 // void setCapacityMap(const CapacityMap& _capacity) { 611 // capacity=&_capacity; 612 // } 613 // void setFlowMap(FlowMap& _flow) { 614 // flow=&_flow; 615 // } 616 617 public: 618 619 BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 620 FlowMap& _flow*/) : 621 GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } 634 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { 635 forward_filter=&_forward_filter; 636 } 637 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { 638 backward_filter=&_backward_filter; 639 } 640 641 public: 642 643 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, 644 BackwardFilterMap& _backward_filter) : 645 GraphWrapper<Graph>(_graph), 646 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } 622 647 623 648 class Edge; … … 633 658 634 659 class Edge : public Graph::Edge { 635 friend class BidirGraphWrapper<Graph>; 660 friend class SubBidirGraphWrapper<Graph, 661 ForwardFilterMap, BackwardFilterMap>; 636 662 ///\bug ez nem is kell 637 663 //template<typename T> friend class NodeMap; … … 660 686 661 687 class OutEdgeIt { 662 friend class BidirGraphWrapper<Graph>; 688 friend class SubBidirGraphWrapper<Graph, 689 ForwardFilterMap, BackwardFilterMap>; 663 690 protected: 664 691 typename Graph::OutEdgeIt out; … … 671 698 OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 672 699 //the unique invalid iterator 673 OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 700 OutEdgeIt(const SubBidirGraphWrapper<Graph, 701 ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 674 702 backward=false; 675 703 _G.graph>first(out, v); 676 while(_G.graph>valid(out) && ! _G.enabled(*this)) { _G.graph>next(out); }704 while(_G.graph>valid(out) && !(*_G.forward_filter)[*this]) { _G.graph>next(out); } 677 705 if (!_G.graph>valid(out)) { 678 706 backward=true; 679 707 _G.graph>first(in, v); 680 while(_G.graph>valid(in) && ! _G.enabled(*this)) { _G.graph>next(in); }708 while(_G.graph>valid(in) && !(*_G.backward_filter)[*this]) { _G.graph>next(in); } 681 709 } 682 710 } … … 694 722 695 723 class InEdgeIt { 696 friend class BidirGraphWrapper<Graph>; 724 friend class SubBidirGraphWrapper<Graph, 725 ForwardFilterMap, BackwardFilterMap>; 697 726 protected: 698 727 typename Graph::OutEdgeIt out; … … 705 734 InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 706 735 //the unique invalid iterator 707 InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 736 InEdgeIt(const SubBidirGraphWrapper<Graph, 737 ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 708 738 backward=false; 709 739 _G.graph>first(in, v); 710 while(_G.graph>valid(in) && ! _G.enabled(*this)) { _G.graph>next(in); }740 while(_G.graph>valid(in) && !(*_G.forward_filter)[*this]) { _G.graph>next(in); } 711 741 if (!_G.graph>valid(in)) { 712 742 backward=true; 713 743 _G.graph>first(out, v); 714 while(_G.graph>valid(out) && ! _G.enabled(*this)) { _G.graph>next(out); }744 while(_G.graph>valid(out) && !(*_G.backward_filter)[*this]) { _G.graph>next(out); } 715 745 } 716 746 } … … 728 758 729 759 class EdgeIt { 730 friend class BidirGraphWrapper<Graph>; 760 friend class SubBidirGraphWrapper<Graph, 761 ForwardFilterMap, BackwardFilterMap>; 731 762 protected: 732 763 typename Graph::EdgeIt e; … … 735 766 EdgeIt() { } 736 767 EdgeIt(const Invalid& i) : e(i), backward(true) { } 737 EdgeIt(const BidirGraphWrapper<Graph>& _G) { 768 EdgeIt(const SubBidirGraphWrapper<Graph, 769 ForwardFilterMap, BackwardFilterMap>& _G) { 738 770 backward=false; 739 771 _G.graph>first(e); 740 while (_G.graph>valid(e) && ! _G.enabled(*this)) _G.graph>next(e);772 while (_G.graph>valid(e) && !(*_G.forward_filter)[*this]) _G.graph>next(e); 741 773 if (!_G.graph>valid(e)) { 742 774 backward=true; 743 775 _G.graph>first(e); 744 while (_G.graph>valid(e) && ! _G.enabled(*this)) _G.graph>next(e);776 while (_G.graph>valid(e) && !(*_G.backward_filter)[*this]) _G.graph>next(e); 745 777 } 746 778 } … … 771 803 Node v=this>graph>aNode(e.out); 772 804 this>graph>next(e.out); 773 while(this>graph>valid(e.out) && ! enabled(e)) {805 while(this>graph>valid(e.out) && !(*forward_filter)[e]) { 774 806 this>graph>next(e.out); } 775 807 if (!this>graph>valid(e.out)) { 776 808 e.backward=true; 777 809 this>graph>first(e.in, v); 778 while(this>graph>valid(e.in) && ! enabled(e)) {810 while(this>graph>valid(e.in) && !(*backward_filter)[e]) { 779 811 this>graph>next(e.in); } 780 812 } 781 813 } else { 782 814 this>graph>next(e.in); 783 while(this>graph>valid(e.in) && ! enabled(e)) {815 while(this>graph>valid(e.in) && !(*backward_filter)[e]) { 784 816 this>graph>next(e.in); } 785 817 } … … 791 823 Node v=this>graph>aNode(e.in); 792 824 this>graph>next(e.in); 793 while(this>graph>valid(e.in) && ! enabled(e)) {825 while(this>graph>valid(e.in) && !(*forward_filter)[e]) { 794 826 this>graph>next(e.in); } 795 827 if (!this>graph>valid(e.in)) { 796 828 e.backward=true; 797 829 this>graph>first(e.out, v); 798 while(this>graph>valid(e.out) && ! enabled(e)) {830 while(this>graph>valid(e.out) && !(*backward_filter)[e]) { 799 831 this>graph>next(e.out); } 800 832 } 801 833 } else { 802 834 this>graph>next(e.out); 803 while(this>graph>valid(e.out) && ! enabled(e)) {835 while(this>graph>valid(e.out) && !(*backward_filter)[e]) { 804 836 this>graph>next(e.out); } 805 837 } … … 809 841 if (!e.backward) { 810 842 this>graph>next(e.e); 811 while(this>graph>valid(e.e) && ! enabled(e)) {843 while(this>graph>valid(e.e) && !(*forward_filter)[e]) { 812 844 this>graph>next(e.e); } 813 845 if (!this>graph>valid(e.e)) { 814 846 e.backward=true; 815 847 this>graph>first(e.e); 816 while(this>graph>valid(e.e) && ! enabled(e)) {848 while(this>graph>valid(e.e) && !(*backward_filter)[e]) { 817 849 this>graph>next(e.e); } 818 850 } 819 851 } else { 820 852 this>graph>next(e.e); 821 while(this>graph>valid(e.e) && ! enabled(e)) {853 while(this>graph>valid(e.e) && !(*backward_filter)[e]) { 822 854 this>graph>next(e.e); } 823 855 } … … 877 909 // } 878 910 879 bool enabled(const Edge& e) const {880 if (!e.backward)881 // return (capacity>get(e.out)flow>get(e.out));882 //return ((*capacity)[e](*flow)[e]);883 return true;884 else885 // return (flow>get(e.in));886 //return ((*flow)[e]);887 return true;888 }911 // bool enabled(const Edge& e) const { 912 // if (!e.backward) 913 // // return (capacity>get(e.out)flow>get(e.out)); 914 // //return ((*capacity)[e](*flow)[e]); 915 // return true; 916 // else 917 // // return (flow>get(e.in)); 918 // //return ((*flow)[e]); 919 // return true; 920 // } 889 921 890 922 // Number enabled(typename Graph::OutEdgeIt out) const { … … 904 936 typedef T ValueType; 905 937 typedef Edge KeyType; 906 EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } 907 EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 938 EdgeMap(const SubBidirGraphWrapper<Graph, 939 ForwardFilterMap, BackwardFilterMap>& _G) : 940 forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } 941 EdgeMap(const SubBidirGraphWrapper<Graph, 942 ForwardFilterMap, BackwardFilterMap>& _G, T a) : 943 forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 908 944 void set(Edge e, T a) { 909 945 if (!e.backward) … … 930 966 }; 931 967 }; 968 969 970 971 ///\brief A wrapper for composing bidirected graph from a directed one. 972 /// experimental, for fezso's sake. 973 /// 974 /// A wrapper for composing bidirected graph from a directed one. 975 /// experimental, for fezso's sake. 976 /// A bidirected graph is composed over the directed one without physical 977 /// storage. As the oppositely directed edges are logically different ones 978 /// the maps are able to attach different values for them. 979 template<typename Graph> 980 class BidirGraphWrapper : 981 public SubBidirGraphWrapper< 982 Graph, 983 ConstMap<typename Graph::Edge, bool>, 984 ConstMap<typename Graph::Edge, bool> > { 985 public: 986 typedef SubBidirGraphWrapper< 987 Graph, 988 ConstMap<typename Graph::Edge, bool>, 989 ConstMap<typename Graph::Edge, bool> > Parent; 990 protected: 991 ConstMap<typename Graph::Edge, bool> cm; 992 //const CapacityMap* capacity; 993 //FlowMap* flow; 994 995 BidirGraphWrapper() : Parent(), cm(true) { } 996 // void setCapacityMap(const CapacityMap& _capacity) { 997 // capacity=&_capacity; 998 // } 999 // void setFlowMap(FlowMap& _flow) { 1000 // flow=&_flow; 1001 // } 1002 1003 public: 1004 1005 BidirGraphWrapper(Graph& _graph) : Parent() { 1006 Parent::setGraph(_graph); 1007 Parent::setForwardFilterMap(cm); 1008 Parent::setBackwardFilterMap(cm); 1009 } 1010 }; 1011 1012 1013 1014 1015 // ///\brief A wrapper for composing bidirected graph from a directed one. 1016 // /// experimental, for fezso's sake. 1017 // /// 1018 // /// A wrapper for composing bidirected graph from a directed one. 1019 // /// experimental, for fezso's sake. 1020 // /// A bidirected graph is composed over the directed one without physical 1021 // /// storage. As the oppositely directed edges are logically different ones 1022 // /// the maps are able to attach different values for them. 1023 // template<typename Graph> 1024 // class BidirGraphWrapper : public GraphWrapper<Graph> { 1025 // public: 1026 // typedef GraphWrapper<Graph> Parent; 1027 // protected: 1028 // //const CapacityMap* capacity; 1029 // //FlowMap* flow; 1030 1031 // BidirGraphWrapper() : GraphWrapper<Graph>()/*, 1032 // capacity(0), flow(0)*/ { } 1033 // // void setCapacityMap(const CapacityMap& _capacity) { 1034 // // capacity=&_capacity; 1035 // // } 1036 // // void setFlowMap(FlowMap& _flow) { 1037 // // flow=&_flow; 1038 // // } 1039 1040 // public: 1041 1042 // BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 1043 // FlowMap& _flow*/) : 1044 // GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } 1045 1046 // class Edge; 1047 // class OutEdgeIt; 1048 // friend class Edge; 1049 // friend class OutEdgeIt; 1050 1051 // //template<typename T> class NodeMap; 1052 // template<typename T> class EdgeMap; 1053 1054 // typedef typename GraphWrapper<Graph>::Node Node; 1055 // typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 1056 1057 // class Edge : public Graph::Edge { 1058 // friend class BidirGraphWrapper<Graph>; 1059 // ///\bug ez nem is kell 1060 // //template<typename T> friend class NodeMap; 1061 // template<typename T> friend class EdgeMap; 1062 // protected: 1063 // bool backward; //true, iff backward 1064 // // typename Graph::Edge e; 1065 // public: 1066 // Edge() { } 1067 // ///\bug =false kelle? zsoltnak kell az addEdge miatt 1068 // Edge(const typename Graph::Edge& _e, bool _backward=false) : 1069 // Graph::Edge(_e), backward(_backward) { } 1070 // Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } 1071 // //the unique invalid iterator 1072 // friend bool operator==(const Edge& u, const Edge& v) { 1073 // return (v.backward==u.backward && 1074 // static_cast<typename Graph::Edge>(u)== 1075 // static_cast<typename Graph::Edge>(v)); 1076 // } 1077 // friend bool operator!=(const Edge& u, const Edge& v) { 1078 // return (v.backward!=u.backward  1079 // static_cast<typename Graph::Edge>(u)!= 1080 // static_cast<typename Graph::Edge>(v)); 1081 // } 1082 // }; 1083 1084 // class OutEdgeIt { 1085 // friend class BidirGraphWrapper<Graph>; 1086 // protected: 1087 // typename Graph::OutEdgeIt out; 1088 // typename Graph::InEdgeIt in; 1089 // bool backward; 1090 // public: 1091 // OutEdgeIt() { } 1092 // //FIXME 1093 // // OutEdgeIt(const Edge& e) : Edge(e) { } 1094 // OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 1095 // //the unique invalid iterator 1096 // OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 1097 // backward=false; 1098 // _G.graph>first(out, v); 1099 // while(_G.graph>valid(out) && !_G.enabled(*this)) { _G.graph>next(out); } 1100 // if (!_G.graph>valid(out)) { 1101 // backward=true; 1102 // _G.graph>first(in, v); 1103 // while(_G.graph>valid(in) && !_G.enabled(*this)) { _G.graph>next(in); } 1104 // } 1105 // } 1106 // operator Edge() const { 1107 // // Edge e; 1108 // // e.forward=this>forward; 1109 // // if (this>forward) e=out; else e=in; 1110 // // return e; 1111 // if (this>backward) 1112 // return Edge(in, this>backward); 1113 // else 1114 // return Edge(out, this>backward); 1115 // } 1116 // }; 1117 1118 // class InEdgeIt { 1119 // friend class BidirGraphWrapper<Graph>; 1120 // protected: 1121 // typename Graph::OutEdgeIt out; 1122 // typename Graph::InEdgeIt in; 1123 // bool backward; 1124 // public: 1125 // InEdgeIt() { } 1126 // //FIXME 1127 // // OutEdgeIt(const Edge& e) : Edge(e) { } 1128 // InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } 1129 // //the unique invalid iterator 1130 // InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 1131 // backward=false; 1132 // _G.graph>first(in, v); 1133 // while(_G.graph>valid(in) && !_G.enabled(*this)) { _G.graph>next(in); } 1134 // if (!_G.graph>valid(in)) { 1135 // backward=true; 1136 // _G.graph>first(out, v); 1137 // while(_G.graph>valid(out) && !_G.enabled(*this)) { _G.graph>next(out); } 1138 // } 1139 // } 1140 // operator Edge() const { 1141 // // Edge e; 1142 // // e.forward=this>forward; 1143 // // if (this>forward) e=out; else e=in; 1144 // // return e; 1145 // if (this>backward) 1146 // return Edge(out, this>backward); 1147 // else 1148 // return Edge(in, this>backward); 1149 // } 1150 // }; 1151 1152 // class EdgeIt { 1153 // friend class BidirGraphWrapper<Graph>; 1154 // protected: 1155 // typename Graph::EdgeIt e; 1156 // bool backward; 1157 // public: 1158 // EdgeIt() { } 1159 // EdgeIt(const Invalid& i) : e(i), backward(true) { } 1160 // EdgeIt(const BidirGraphWrapper<Graph>& _G) { 1161 // backward=false; 1162 // _G.graph>first(e); 1163 // while (_G.graph>valid(e) && !_G.enabled(*this)) _G.graph>next(e); 1164 // if (!_G.graph>valid(e)) { 1165 // backward=true; 1166 // _G.graph>first(e); 1167 // while (_G.graph>valid(e) && !_G.enabled(*this)) _G.graph>next(e); 1168 // } 1169 // } 1170 // operator Edge() const { 1171 // return Edge(e, this>backward); 1172 // } 1173 // }; 1174 1175 // using GraphWrapper<Graph>::first; 1176 // // NodeIt& first(NodeIt& i) const { 1177 // // i=NodeIt(*this); return i; 1178 // // } 1179 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1180 // i=OutEdgeIt(*this, p); return i; 1181 // } 1182 // // FIXME not tested 1183 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1184 // i=InEdgeIt(*this, p); return i; 1185 // } 1186 // EdgeIt& first(EdgeIt& i) const { 1187 // i=EdgeIt(*this); return i; 1188 // } 1189 1190 // using GraphWrapper<Graph>::next; 1191 // // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } 1192 // OutEdgeIt& next(OutEdgeIt& e) const { 1193 // if (!e.backward) { 1194 // Node v=this>graph>aNode(e.out); 1195 // this>graph>next(e.out); 1196 // while(this>graph>valid(e.out) && !enabled(e)) { 1197 // this>graph>next(e.out); } 1198 // if (!this>graph>valid(e.out)) { 1199 // e.backward=true; 1200 // this>graph>first(e.in, v); 1201 // while(this>graph>valid(e.in) && !enabled(e)) { 1202 // this>graph>next(e.in); } 1203 // } 1204 // } else { 1205 // this>graph>next(e.in); 1206 // while(this>graph>valid(e.in) && !enabled(e)) { 1207 // this>graph>next(e.in); } 1208 // } 1209 // return e; 1210 // } 1211 // // FIXME Not tested 1212 // InEdgeIt& next(InEdgeIt& e) const { 1213 // if (!e.backward) { 1214 // Node v=this>graph>aNode(e.in); 1215 // this>graph>next(e.in); 1216 // while(this>graph>valid(e.in) && !enabled(e)) { 1217 // this>graph>next(e.in); } 1218 // if (!this>graph>valid(e.in)) { 1219 // e.backward=true; 1220 // this>graph>first(e.out, v); 1221 // while(this>graph>valid(e.out) && !enabled(e)) { 1222 // this>graph>next(e.out); } 1223 // } 1224 // } else { 1225 // this>graph>next(e.out); 1226 // while(this>graph>valid(e.out) && !enabled(e)) { 1227 // this>graph>next(e.out); } 1228 // } 1229 // return e; 1230 // } 1231 // EdgeIt& next(EdgeIt& e) const { 1232 // if (!e.backward) { 1233 // this>graph>next(e.e); 1234 // while(this>graph>valid(e.e) && !enabled(e)) { 1235 // this>graph>next(e.e); } 1236 // if (!this>graph>valid(e.e)) { 1237 // e.backward=true; 1238 // this>graph>first(e.e); 1239 // while(this>graph>valid(e.e) && !enabled(e)) { 1240 // this>graph>next(e.e); } 1241 // } 1242 // } else { 1243 // this>graph>next(e.e); 1244 // while(this>graph>valid(e.e) && !enabled(e)) { 1245 // this>graph>next(e.e); } 1246 // } 1247 // return e; 1248 // } 1249 1250 // Node tail(Edge e) const { 1251 // return ((!e.backward) ? this>graph>tail(e) : this>graph>head(e)); } 1252 // Node head(Edge e) const { 1253 // return ((!e.backward) ? this>graph>head(e) : this>graph>tail(e)); } 1254 1255 // Node aNode(OutEdgeIt e) const { 1256 // return ((!e.backward) ? this>graph>aNode(e.out) : 1257 // this>graph>aNode(e.in)); } 1258 // Node bNode(OutEdgeIt e) const { 1259 // return ((!e.backward) ? this>graph>bNode(e.out) : 1260 // this>graph>bNode(e.in)); } 1261 1262 // Node aNode(InEdgeIt e) const { 1263 // return ((!e.backward) ? this>graph>aNode(e.in) : 1264 // this>graph>aNode(e.out)); } 1265 // Node bNode(InEdgeIt e) const { 1266 // return ((!e.backward) ? this>graph>bNode(e.in) : 1267 // this>graph>bNode(e.out)); } 1268 1269 // /// Gives back the opposite edge. 1270 // Edge opposite(const Edge& e) const { 1271 // Edge f=e; 1272 // f.backward=!f.backward; 1273 // return f; 1274 // } 1275 1276 // // int nodeNum() const { return graph>nodeNum(); } 1277 // //FIXME 1278 // void edgeNum() const { } 1279 // //int edgeNum() const { return graph>edgeNum(); } 1280 1281 1282 // // int id(Node v) const { return graph>id(v); } 1283 1284 // bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } 1285 // bool valid(Edge e) const { 1286 // return this>graph>valid(e); 1287 // //return e.forward ? graph>valid(e.out) : graph>valid(e.in); 1288 // } 1289 1290 // bool forward(const Edge& e) const { return !e.backward; } 1291 // bool backward(const Edge& e) const { return e.backward; } 1292 1293 // // void augment(const Edge& e, Number a) const { 1294 // // if (!e.backward) 1295 // // // flow>set(e.out, flow>get(e.out)+a); 1296 // // flow>set(e, (*flow)[e]+a); 1297 // // else 1298 // // // flow>set(e.in, flow>get(e.in)a); 1299 // // flow>set(e, (*flow)[e]a); 1300 // // } 1301 1302 // bool enabled(const Edge& e) const { 1303 // if (!e.backward) 1304 // // return (capacity>get(e.out)flow>get(e.out)); 1305 // //return ((*capacity)[e](*flow)[e]); 1306 // return true; 1307 // else 1308 // // return (flow>get(e.in)); 1309 // //return ((*flow)[e]); 1310 // return true; 1311 // } 1312 1313 // // Number enabled(typename Graph::OutEdgeIt out) const { 1314 // // // return (capacity>get(out)flow>get(out)); 1315 // // return ((*capacity)[out](*flow)[out]); 1316 // // } 1317 1318 // // Number enabled(typename Graph::InEdgeIt in) const { 1319 // // // return (flow>get(in)); 1320 // // return ((*flow)[in]); 1321 // // } 1322 1323 // template <typename T> 1324 // class EdgeMap { 1325 // typename Graph::template EdgeMap<T> forward_map, backward_map; 1326 // public: 1327 // typedef T ValueType; 1328 // typedef Edge KeyType; 1329 // EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } 1330 // EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 1331 // void set(Edge e, T a) { 1332 // if (!e.backward) 1333 // forward_map.set(e/*.out*/, a); 1334 // else 1335 // backward_map.set(e/*.in*/, a); 1336 // } 1337 // T operator[](Edge e) const { 1338 // if (!e.backward) 1339 // return forward_map[e/*.out*/]; 1340 // else 1341 // return backward_map[e/*.in*/]; 1342 // } 1343 // void update() { 1344 // forward_map.update(); 1345 // backward_map.update(); 1346 // } 1347 // // T get(Edge e) const { 1348 // // if (e.out_or_in) 1349 // // return forward_map.get(e.out); 1350 // // else 1351 // // return backward_map.get(e.in); 1352 // // } 1353 // }; 1354 // }; 932 1355 933 1356 /// \brief A bidirected graph template. … … 942 1365 template<typename Graph> 943 1366 class BidirGraph : public BidirGraphWrapper<Graph> { 1367 public: 944 1368 typedef UndirGraphWrapper<Graph> Parent; 945 1369 protected: … … 950 1374 } 951 1375 }; 1376 1377 1378 1379 /// An experiment for ResGraphWrapper. 1380 template<typename Graph, typename Number, 1381 typename CapacityMap, typename FlowMap> 1382 class ForwardFilter { 1383 const Graph* graph; 1384 const CapacityMap* capacity; 1385 const FlowMap* flow; 1386 public: 1387 ForwardFilter(const Graph& _graph, 1388 const CapacityMap& _capacity, const FlowMap& _flow) : 1389 graph(&_graph), capacity(&_capacity), flow(&_flow) { } 1390 bool operator[](const typename Graph::Edge& e) const { 1391 return ((*flow)[e] < (*capacity)[e]); 1392 } 1393 }; 1394 1395 /// An experiment for ResGraphWrapper. 1396 template<typename Graph, typename Number, 1397 typename CapacityMap, typename FlowMap> 1398 class BackwardFilter { 1399 const Graph* graph; 1400 const CapacityMap* capacity; 1401 const FlowMap* flow; 1402 public: 1403 BackwardFilter(const Graph& _graph, 1404 const CapacityMap& _capacity, const FlowMap& _flow) : 1405 graph(&_graph), capacity(&_capacity), flow(&_flow) { } 1406 bool operator[](const typename Graph::Edge& e) const { 1407 return (0 < (*flow)[e]); 1408 } 1409 }; 1410 1411 1412 /// An experiment for ResGraphWrapper. 1413 template<typename Graph, typename Number, 1414 typename CapacityMap, typename FlowMap> 1415 class ExpResGraphWrapper : 1416 public SubBidirGraphWrapper< 1417 Graph, 1418 ForwardFilter<Graph, Number, CapacityMap, FlowMap>, 1419 BackwardFilter<Graph, Number, CapacityMap, FlowMap> > { 1420 public: 1421 typedef SubBidirGraphWrapper< 1422 Graph, 1423 ForwardFilter<Graph, Number, CapacityMap, FlowMap>, 1424 BackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent; 1425 protected: 1426 const CapacityMap* capacity; 1427 FlowMap* flow; 1428 ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter; 1429 BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter; 1430 public: 1431 ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 1432 FlowMap& _flow) : 1433 Parent(), capacity(&_capacity), flow(&_flow), 1434 forward_filter(_graph, _capacity, _flow), 1435 backward_filter(_graph, _capacity, _flow) { 1436 Parent::setGraph(_graph); 1437 Parent::setForwardFilterMap(forward_filter); 1438 Parent::setBackwardFilterMap(backward_filter); 1439 } 1440 1441 // bool forward(const Parent::Edge& e) const { return Parent::forward(e); } 1442 //bool backward(const Edge& e) const { return e.backward; } 1443 1444 void augment(const typename Parent::Edge& e, Number a) const { 1445 if (Parent::forward(e)) 1446 // flow>set(e.out, flow>get(e.out)+a); 1447 flow>set(e, (*flow)[e]+a); 1448 else 1449 //flow>set(e.in, flow>get(e.in)a); 1450 flow>set(e, (*flow)[e]a); 1451 } 1452 1453 Number resCap(const typename Parent::Edge& e) const { 1454 if (Parent::forward(e)) 1455 // return (capacity>get(e.out)flow>get(e.out)); 1456 return ((*capacity)[e](*flow)[e]); 1457 else 1458 // return (flow>get(e.in)); 1459 return ((*flow)[e]); 1460 } 1461 1462 }; 1463 1464 1465 1466 1467 // /// An experiment for ResGraphWrapper. 1468 // template<typename Graph, typename Number, 1469 // typename CapacityMap, typename FlowMap> 1470 // class ExpResGraphWrapper : 1471 // public SubGraphWrapper< BidirGraphWrapper<Graph>, 1472 // ConstMap<typename BidirGraphWrapper<Graph>::Node, 1473 // bool>, 1474 // EdgeFilter< BidirGraphWrapper<Graph>, 1475 // CapacityMap, FlowMap> > { 1476 // public: 1477 // typedef SubGraphWrapper< BidirGraphWrapper<Graph>, 1478 // ConstMap<typename BidirGraphWrapper<Graph>::Node, 1479 // bool>, 1480 // EdgeFilter< BidirGraphWrapper<Graph>, 1481 // CapacityMap, FlowMap> > Parent; 1482 // protected: 1483 // const CapacityMap* capacity; 1484 // FlowMap* flow; 1485 // BidirGraphWrapper<Graph> bidir_graph; 1486 // ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter; 1487 // EdgeFilter< BidirGraphWrapper<Graph>, CapacityMap, FlowMap> edge_filter; 1488 // public: 1489 // ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 1490 // FlowMap& _flow) : 1491 // Parent(), capacity(&_capacity), flow(&_flow), 1492 // bidir_graph(_graph), 1493 // node_filter(true), 1494 // edge_filter(bidir_graph, *capacity, *flow) { 1495 // Parent::setGraph(bidir_graph); 1496 // Parent::setNodeFilterMap(node_filter); 1497 // Parent::setEdgeFilterMap(edge_filter); 1498 // } 1499 1500 // // bool forward(const Parent::Edge& e) const { return Parent::forward(e); } 1501 // //bool backward(const Edge& e) const { return e.backward; } 1502 1503 // void augment(const typename Parent::Edge& e, Number a) const { 1504 // if (Parent::forward(e)) 1505 // // flow>set(e.out, flow>get(e.out)+a); 1506 // flow>set(e, (*flow)[e]+a); 1507 // else 1508 // // flow>set(e.in, flow>get(e.in)a); 1509 // flow>set(e, (*flow)[e]a); 1510 // } 1511 1512 // Number resCap(const typename Parent::Edge& e) const { 1513 // if (Parent::forward(e)) 1514 // // return (capacity>get(e.out)flow>get(e.out)); 1515 // return ((*capacity)[e](*flow)[e]); 1516 // else 1517 // // return (flow>get(e.in)); 1518 // return ((*flow)[e]); 1519 // } 1520 1521 // }; 1522 952 1523 953 1524 … … 958 1529 typename CapacityMap, typename FlowMap> 959 1530 class ResGraphWrapper : public GraphWrapper<Graph> { 1531 public: 1532 typedef GraphWrapper<Graph> Parent; 960 1533 protected: 961 1534 const CapacityMap* capacity; … … 1284 1857 template<typename Graph, typename FirstOutEdgesMap> 1285 1858 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { 1859 public: 1860 typedef GraphWrapper<Graph> Parent; 1286 1861 protected: 1287 1862 FirstOutEdgesMap* first_out_edges;
Note: See TracChangeset
for help on using the changeset viewer.