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

 4 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; 
src/work/jacint/max_flow.h
r647 r650 64 64 FlowMap* flow; 65 65 int n; //the number of nodes of G 66 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; 66 // typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; 67 typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; 67 68 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; 68 69 typedef typename ResGW::Edge ResGWEdge; … … 140 141 map(&_map), number_of_augmentations(&_number_of_augmentations) { } 141 142 void set(const Node& n, bool b) { 142 map>set(n, *number_of_augmentations); 143 if (b) 144 map>set(n, *number_of_augmentations); 145 else 146 map>set(n, *number_of_augmentations1); 143 147 } 144 148 bool operator[](const Node& n) const { … … 942 946 943 947 if (status!=AFTER_AUGMENTING) { 944 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 1);945 number_of_augmentations= 0;948 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 3*n); 949 number_of_augmentations=3*n+1; 946 950 } else { 947 951 ++number_of_augmentations; 
src/work/marci/bfs_dfs.h
r646 r650 21 21 /// Bfs searches for the nodes wich are not marked in 22 22 /// \c reached_map 23 /// Reached have to work as readwrite bool Nodemap.23 /// Reached have to be a readwrite bool nodemap. 24 24 /// \ingroup galgs 25 25 template <typename Graph, /*typename OutEdgeIt,*/ … … 37 37 public: 38 38 /// In that constructor \c _reached have to be a reference 39 /// for a bool Nodemap. The algorithm will search in a bfs order for 40 /// the nodes which are \c false initially 39 /// for a bool bodemap. The algorithm will search for the 40 /// initially \c false nodes 41 /// in a bfs order. 41 42 BfsIterator(const Graph& _graph, ReachedMap& _reached) : 42 43 graph(&_graph), reached(_reached), … … 44 45 /// The same as above, but the map storing the reached nodes 45 46 /// is constructed dynamically to everywhere false. 47 /// \deprecated 46 48 BfsIterator(const Graph& _graph) : 47 49 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), … … 122 124 Node bNode() const { return graph>bNode(actual_edge); } 123 125 /// Guess what? 126 /// \deprecated 124 127 const ReachedMap& getReachedMap() const { return reached; } 125 128 /// Guess what? 129 /// \deprecated 126 130 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } 127 131 }; … … 130 134 /// \c reached_map 131 135 /// Reached have to work as a readwrite bool Nodemap, 132 /// Pred is a write Edge Nodemap and133 /// Dist is a readwrite Nodemap of integral value, have to be.136 /// Pred is a write edge nodemap and 137 /// Dist is a readwrite nodemap of integral value, have to be. 134 138 /// \ingroup galgs 135 139 template <typename Graph, … … 180 184 } 181 185 /// Guess what? 186 /// \deprecated 182 187 const PredMap& getPredMap() const { return pred; } 183 188 /// Guess what? 189 /// \deprecated 184 190 const DistMap& getDistMap() const { return dist; } 185 191 }; … … 204 210 public: 205 211 /// In that constructor \c _reached have to be a reference 206 /// for a bool Nodemap. The algorithm will search in a dfs order for212 /// for a bool nodemap. The algorithm will search in a dfs order for 207 213 /// the nodes which are \c false initially 208 214 DfsIterator(const Graph& _graph, ReachedMap& _reached) : … … 266 272 Node bNode() const { return graph>bNode(actual_edge); } 267 273 /// Guess what? 274 /// \deprecated 268 275 const ReachedMap& getReachedMap() const { return reached; } 269 276 /// Guess what? 277 /// \deprecated 270 278 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } 271 279 }; … … 273 281 /// Dfs searches for the nodes wich are not marked in 274 282 /// \c reached_map 275 /// Reached is a readwrite bool Nodemap,276 /// Pred is a write Nodemap, have to be.283 /// Reached is a readwrite bool nodemap, 284 /// Pred is a write nodemap, have to be. 277 285 /// \ingroup galgs 278 286 template <typename Graph, … … 319 327 } 320 328 /// Guess what? 329 /// \deprecated 321 330 const PredMap& getPredMap() const { return pred; } 322 331 }; 
src/work/marci/leda/leda_graph_wrapper.h
r646 r650 34 34 void setGraph(Graph& _l_graph) { l_graph=&_l_graph; } 35 35 public: 36 37 //LedaGraphWrapper() { }36 37 /// Constructor for wrapping LEDA graphs. 38 38 LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { } 39 LedaGraphWrapper(const LedaGraphWrapper &G) : l_graph(G.l_graph) { } 39 /// Copy constructor 40 LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { } 40 41 41 42 template <typename T> class NodeMap; … … 51 52 class InEdgeIt; 52 53 53 /// T he base type of the node iterators.54 /// Trivial nodeiterator 54 55 class Node { 55 56 friend class LedaGraphWrapper<Graph>; … … 66 67 /// @warning The default constructor sets the iterator 67 68 /// to an undefined value. 68 Node() { } //FIXME69 Node() { } //FIXME 69 70 /// Initialize the iterator to be invalid 70 71 Node(Invalid) : l_n(0) { } … … 80 81 /// @warning The default constructor sets the iterator 81 82 /// to an undefined value. 82 NodeIt() { } //FIXME83 /// Initialize the iterator to be invalid 84 NodeIt(Invalid i) : Node(i) { }83 NodeIt() { } //FIXME 84 /// Initialize the iterator to be invalid 85 NodeIt(Invalid i) : Node(i) { } 85 86 /// Sets the iterator to the first node of \c G. 86 87 NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph>first_node()) { } … … 88 89 }; 89 90 90 /// T he base type of the edge iterators.91 /// Trivial edgeiterator. 91 92 class Edge { 92 93 friend class LedaGraphWrapper; … … 99 100 /// @warning The default constructor sets the iterator 100 101 /// to an undefined value. 101 Edge() { } //FIXME102 /// Initialize the iterator to be invalid 103 Edge(Invalid) : l_e(0) { }102 Edge() { } //FIXME 103 /// Initialize the iterator to be invalid 104 Edge(Invalid) : l_e(0) { } 104 105 //Edge(const Edge &) {} 105 106 bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME … … 108 109 }; 109 110 110 /// This iterator goes trought the outgoing edges of a certain graph. 111 111 /// This iterator goes trought the outgoing edges of a certain node. 112 112 class OutEdgeIt : public Edge { 113 113 public: 114 114 /// @warning The default constructor sets the iterator 115 115 /// to an undefined value. 116 OutEdgeIt() { }117 /// Initialize the iterator to be invalid 118 OutEdgeIt(Invalid i) : Edge(i) { }116 OutEdgeIt() { } 117 /// Initialize the iterator to be invalid 118 OutEdgeIt(Invalid i) : Edge(i) { } 119 119 /// This constructor sets the iterator to first outgoing edge. 120 120 … … 126 126 }; 127 127 128 /// This iterator goes trought the incoming edges of a certain node. 128 129 class InEdgeIt : public Edge { 129 130 public: 130 131 /// @warning The default constructor sets the iterator 131 132 /// to an undefined value. 132 InEdgeIt() { }133 /// Initialize the iterator to be invalid 134 InEdgeIt(Invalid i) : Edge(i) { }133 InEdgeIt() { } 134 /// Initialize the iterator to be invalid 135 InEdgeIt(Invalid i) : Edge(i) { } 135 136 InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph>first_in_edge(n.l_n)) { } 136 137 }; 137 138 138 139 // class SymEdgeIt : public Edge {}; 140 141 /// This iterator goes trought the edges of the graph. 139 142 class EdgeIt : public Edge { 140 143 public: 141 144 /// @warning The default constructor sets the iterator 142 145 /// to an undefined value. 143 EdgeIt() { }144 /// Initialize the iterator to be invalid 145 EdgeIt(Invalid i) : Edge(i) { }146 EdgeIt() { } 147 /// Initialize the iterator to be invalid 148 EdgeIt(Invalid i) : Edge(i) { } 146 149 EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph>first_edge()) { } 147 150 }; 148 151 149 152 /// First node of the graph. 150 153 /// 151 154 /// \post \c i and the return value will be the first node. 152 155 /// … … 164 167 } 165 168 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} 166 /// The first edge of the Graph.169 /// The first edge of the graph. 167 170 EdgeIt &first(EdgeIt &i) const { 168 171 i=EdgeIt(*this); … … 254 257 int edgeNum() const { return l_graph>number_of_edges(); } 255 258 256 /// Read/write map from the nodes to type \c T.259 /// Read/write map from the nodes to type \c T. 257 260 template<typename T> class NodeMap 258 261 { … … 274 277 }; 275 278 276 /// Read/write map from the edges to type \c T.279 /// Read/write map from the edges to type \c T. 277 280 template<typename T> class EdgeMap 278 281 { … … 295 298 296 299 297 ///Read/write map from the nodes to type \c T. 300 /// This class is to wrap existing 301 /// LEDA nodemaps to HUGO ones. 298 302 template<typename T> class NodeMapWrapper 299 303 { 300 leda_node_ map<T>* leda_stuff;304 leda_node_array<T>* leda_stuff; 301 305 public: 302 306 typedef T ValueType; 303 307 typedef Node KeyType; 304 308 305 NodeMapWrapper(leda_node_ map<T>& _leda_stuff) :309 NodeMapWrapper(leda_node_array<T>& _leda_stuff) : 306 310 leda_stuff(&_leda_stuff) { } 307 311 //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {} 308 312 309 313 void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; } 310 T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary314 //T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary 311 315 T &operator[](Node i) { return (*leda_stuff)[i.l_n]; } 312 316 const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; } … … 316 320 }; 317 321 318 ///Read/write map from the edges to type \c T. 322 /// This class is to wrap existing 323 /// LEDA edgemaps to HUGO ones. 319 324 template<typename T> class EdgeMapWrapper 320 325 { 321 leda_edge_ map<T>* leda_stuff;326 leda_edge_array<T>* leda_stuff; 322 327 public: 323 328 typedef T ValueType; 324 329 typedef Edge KeyType; 325 330 326 EdgeMapWrapper(leda_edge_ map<T>& _leda_stuff) :331 EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) : 327 332 leda_stuff(_leda_stuff) { } 328 333 //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {} 329 334 330 335 void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; } 331 T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary336 //T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary 332 337 T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; } 333 338 const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; } … … 335 340 void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ } 336 341 //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary 342 }; 343 344 /// This class is used for access nodedata of 345 /// LEDA parametrized graphs. 346 template<typename T> 347 class NodeDataMap : public NodeMapWrapper<T> 348 { 349 public: 350 NodeDataMap(LedaGraphWrapper<Graph>& LGW) : 351 NodeMapWrapper<T>(*(LGW._g_graph).node_data()) { } 352 }; 353 354 /// This class is used for access edgedata of 355 /// LEDA parametrized graphs. 356 template<typename T> 357 class EdgeDataMap : public EdgeMapWrapper<T> 358 { 359 public: 360 EdgeDataMap(LedaGraphWrapper<Graph>& LGW) : 361 EdgeMapWrapper<T>(*(LGW._g_graph).edge_data()) { } 337 362 }; 338 363
Note: See TracChangeset
for help on using the changeset viewer.