Changeset 379:a5bff2813c4d in lemon0.x for src
 Timestamp:
 04/23/04 09:41:48 (21 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@509
 Location:
 src/work/marci
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bipartite_graph_wrapper_test.cc
r368 r379 11 11 #include <bfs_iterator.h> 12 12 #include <graph_wrapper.h> 13 #include <maps.h> 14 #include <edmonds_karp.h> 13 15 14 16 using namespace hugo; … … 42 44 std::cout << bgw.tail(e) << ">" << bgw.head(e) << std::endl; 43 45 } 44 // Graph::NodeMap<OutEdgeIt> pred(G);45 // Timer ts;46 // {47 // ts.reset();48 // Graph::NodeMap<bool> reached(G);49 // reached.set(s, true);50 // pred.set(s, INVALID);51 // std::queue<Node> bfs_queue;52 // bfs_queue.push(t);53 // while (!bfs_queue.empty()) {54 // Node v=bfs_queue.front();55 // bfs_queue.pop();56 // OutEdgeIt e;57 // for(G.first(e,v); G.valid(e); G.next(e)) {58 // Node w=G.head(e);59 // if (!reached[w]) {60 // bfs_queue.push(w);61 // reached.set(w, true);62 // pred.set(w, e);63 // }64 // }65 // }66 46 67 // std::cout << ts << std::endl;68 // } 47 BGW::NodeMap<int> dbyj(bgw); 48 BGW::EdgeMap<int> dbyxcj(bgw); 69 49 70 // { 71 // ts.reset(); 72 // BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); 73 // bfs.pushAndSetReached(s); 74 // pred.set(s, INVALID); 75 // while (!bfs.finished()) { 76 // ++bfs; 77 // if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 78 // pred.set(bfs.bNode(), bfs); 79 // } 80 // std::cout << ts << std::endl; 81 // } 50 typedef stGraphWrapper<BGW> stGW; 51 stGW stgw(bgw); 52 ConstMap<stGW::Edge, int> const1map(1); 53 stGW::NodeMap<int> ize(stgw); 54 stGW::EdgeMap<int> flow(stgw); 55 56 BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw); 57 Graph::NodeIt si; 58 Graph::Node s; 59 s=g.first(si); 60 bfs.pushAndSetReached(BGW::Node(s)); 61 while (!bfs.finished()) ++bfs; 62 63 BGW::EdgeMap<bool> cap(bgw); 64 BGW::EdgeMap<bool> flow1(bgw); 65 66 typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> > 67 RBGW; 68 RBGW rbgw(bgw, cap, flow1); 69 RBGW::NodeMap<int> u(rbgw); 70 71 72 MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 73 max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow); 74 max_flow_test.augmentOnShortestPath(); 82 75 83 76 return 0; 
src/work/marci/graph_wrapper.h
r376 r379 157 157 EdgeIt& next(EdgeIt& i) const { graph>next(i.e); return i; } 158 158 159 Node tail(const Edge& e) const { 160 return Node(graph>tail(static_cast<typename Graph::Edge>(e))); } 159 161 Node head(const Edge& e) const { 160 162 return Node(graph>head(static_cast<typename Graph::Edge>(e))); } 161 Node tail(const Edge& e) const {162 return Node(graph>tail(static_cast<typename Graph::Edge>(e))); }163 163 164 164 bool valid(const Node& n) const { … … 222 222 friend class GraphWrapper<Graph>; 223 223 friend class RevGraphWrapper<Graph>; 224 typename Graph:: OutEdgeIt e;224 typename Graph::InEdgeIt e; 225 225 public: 226 226 OutEdgeIt() { } 227 OutEdgeIt(const typename Graph:: OutEdgeIt& _e) : e(_e) { }227 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 228 228 OutEdgeIt(const Invalid& i) : e(i) { } 229 229 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : … … 234 234 friend class GraphWrapper<Graph>; 235 235 friend class RevGraphWrapper<Graph>; 236 typename Graph:: InEdgeIt e;236 typename Graph::OutEdgeIt e; 237 237 public: 238 238 InEdgeIt() { } 239 InEdgeIt(const typename Graph:: InEdgeIt& _e) : e(_e) { }239 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } 240 240 InEdgeIt(const Invalid& i) : e(i) { } 241 241 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : … … 260 260 Node bNode(const OutEdgeIt& e) const { return Node(graph>bNode(e.e)); } 261 261 Node bNode(const InEdgeIt& e) const { return Node(graph>bNode(e.e)); } 262 263 Node tail(const Edge& e) const { 264 return GraphWrapper<Graph>::head(e); } 265 Node head(const Edge& e) const { 266 return GraphWrapper<Graph>::tail(e); } 267 262 268 }; 263 269 … … 884 890 885 891 public: 892 static const bool S_CLASS=false; 893 static const bool T_CLASS=true; 894 886 895 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 887 896 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) { … … 891 900 typedef typename GraphWrapper<Graph>::Edge Edge; 892 901 //using GraphWrapper<Graph>::EdgeIt; 893 class SNodeIt {902 class ClassNodeIt { 894 903 Node n; 895 904 public: 896 SNodeIt() { }897 SNodeIt(const Invalid& i) : n(i) { }898 SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {899 _G.s_false_t_true_map>first(n, false);905 ClassNodeIt() { } 906 ClassNodeIt(const Invalid& i) : n(i) { } 907 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 908 _G.s_false_t_true_map>first(n, _class); 900 909 } 901 910 operator Node() const { return n; } 902 911 }; 903 class TNodeIt { 904 Node n; 905 public: 906 TNodeIt() { } 907 TNodeIt(const Invalid& i) : n(i) { } 908 TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 909 _G.s_false_t_true_map>first(n, true); 910 } 911 operator Node() const { return n; } 912 }; 912 // class SNodeIt { 913 // Node n; 914 // public: 915 // SNodeIt() { } 916 // SNodeIt(const Invalid& i) : n(i) { } 917 // SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 918 // _G.s_false_t_true_map>first(n, false); 919 // } 920 // operator Node() const { return n; } 921 // }; 922 // class TNodeIt { 923 // Node n; 924 // public: 925 // TNodeIt() { } 926 // TNodeIt(const Invalid& i) : n(i) { } 927 // TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 928 // _G.s_false_t_true_map>first(n, true); 929 // } 930 // operator Node() const { return n; } 931 // }; 913 932 class OutEdgeIt { 914 933 public: 934 915 935 typename Graph::OutEdgeIt e; 916 936 public: … … 919 939 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { 920 940 if (!(*(_G.s_false_t_true_map))[_n]) 921 e= OutEdgeIt(*(_G.graph), typename Graph::Node(_n));941 e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); 922 942 else 923 943 e=INVALID; … … 933 953 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { 934 954 if ((*(_G.s_false_t_true_map))[_n]) 935 e= InEdgeIt(*(_G.graph), typename Graph::Node(_n));955 e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n)); 936 956 else 937 957 e=INVALID; … … 941 961 942 962 using GraphWrapper<Graph>::first; 943 SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } 944 TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } 963 ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 964 n=SNodeIt(*this, _class) ; return n; } 965 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } 966 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } 967 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 968 i=OutEdgeIt(*this, p); return i; 969 } 970 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 971 i=InEdgeIt(*this, p); return i; 972 } 945 973 946 974 using GraphWrapper<Graph>::next; 947 SNodeIt& next(SNodeIt& n) const {975 ClassNodeIt& next(ClassNodeIt& n) const { 948 976 this>s_false_t_true_map>next(n); return n; 949 977 } 950 TNodeIt& next(TNodeIt& n) const { 951 this>s_false_t_true_map>next(n); return n; 952 } 978 // SNodeIt& next(SNodeIt& n) const { 979 // this>s_false_t_true_map>next(n); return n; 980 // } 981 // TNodeIt& next(TNodeIt& n) const { 982 // this>s_false_t_true_map>next(n); return n; 983 // } 984 OutEdgeIt& next(OutEdgeIt& i) const { graph>next(i.e); return i; } 985 InEdgeIt& next(InEdgeIt& i) const { graph>next(i.e); return i; } 953 986 954 987 Node tail(const Edge& e) { … … 977 1010 return Node(this>graph>bNode(e.e)); 978 1011 } 1012 1013 bool inSClass(const Node& n) const { 1014 return !(this>s_false_t_true_map[n]); 1015 } 1016 bool inTClass(const Node& n) const { 1017 return (this>s_false_t_true_map[n]); 1018 } 979 1019 }; 980 1020 981 1021 982 983 // /// experimentral, do not try it. 984 // template<typename Graph> 985 // class stGraphWrapper : public GraphWrapper<Graph> { 986 // public: 987 // class Node; 988 // class NodeIt; 989 // class Edge; 990 // class OutEdgeIt; 991 // class InEdgeIt; 992 // class EdgeIt; 993 994 // const Node s; 995 // const Node t; 996 997 // stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph), 998 // s(INVALID, 1), t(INVALID, 2) { } 999 1000 // class Node : public Graph::Node { 1001 // friend class GraphWrapper<Graph>; 1002 // friend class stGraphWrapper<Graph>; 1003 // protected: 1004 // int spec; //0 if real node, 1 iff s, 2 iff t 1005 // public: 1006 // Node() { } 1007 // Node(const typename Graph::Node& _n, int _spec=0) : 1008 // Graph::Node(_n), spec(_spec) { } 1009 // Node(const Invalid& i) : Graph::Node(i), spec(2) { } 1010 // //invalid: (invalid, 2); 1011 // }; 1012 1013 // class NodeIt { 1014 // friend class GraphWrapper<Graph>; 1015 // friend class stGraphWrapper<Graph>; 1016 // typename Graph::NodeIt n; 1017 // int spec; 1018 // public: 1019 // NodeIt() { } 1020 // NodeIt(const typename Graph::NodeIt& _n, int _spec=0) : 1021 // n(_n), spec(_spec) { } 1022 // NodeIt(const Invalid& i) : n(i), spec(2) { } 1023 // NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 1024 // if (!_G>valid(n)) spec=1; 1025 // } 1026 // operator Node() const { return Node(n, spec); } 1027 // }; 1028 // // typedef typename Graph::Edge Edge; 1029 // class Edge : public Graph::Edge { 1030 // friend class GraphWrapper<Graph>; 1031 // friend class stGraphWrapper<Graph>; 1032 // Node tail_spec; 1033 // Node head_spec; 1034 // public: 1035 // Edge() { } 1036 // Edge(const typename Graph::Edge& _e) : 1037 // Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) { 1038 // //a tailt es a headet real nodera csinaljuk 1039 // } 1040 // Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { } 1041 // }; 1042 // class OutEdgeIt { 1043 // friend class GraphWrapper<Graph>; 1044 // friend class stGraphWrapper<Graph>; 1045 // typename Graph::OutEdgeIt e; 1046 // Node tail_spec; 1047 // Node head_spec; 1048 // public: 1049 // OutEdgeIt() { } 1050 // OutEdgeIt(const typename Graph::OutEdgeIt& _e) : 1051 // e(_e), tail_spec(i, 0), head_spec(i, 0) { 1052 // //a tailt es a headet real nodera csinaljuk 1053 // } 1054 // OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { } 1055 // //invalid: (barmi, 0, 2) 1056 // OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) { 1057 // switch (_n.spec) { 1058 // case 0 : 1059 // e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); 1060 // _tail.spec=0; 1061 // _head.spec=0; 1062 // if (!_G.graph>valid(e)) spec=1; 1063 // break; 1064 // case 1: 1065 // e=INVALID; 1066 // _tail.spec=1; 1067 // _head(_G.graph>first(typename Graph::NodeIt())); 1068 // if _head.spec==1 1069 // break; 1070 // }; 1071 1072 // } 1073 // operator Edge() const { return Edge(typename Graph::Edge(e)); } 1074 // }; 1075 // class InEdgeIt { 1076 // friend class GraphWrapper<Graph>; 1077 // typename Graph::InEdgeIt e; 1078 // public: 1079 // InEdgeIt() { } 1080 // InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 1081 // InEdgeIt(const Invalid& i) : e(i) { } 1082 // InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 1083 // e(*(_G.graph), typename Graph::Node(_n)) { } 1084 // operator Edge() const { return Edge(typename Graph::Edge(e)); } 1085 // }; 1086 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 1087 // class EdgeIt { 1088 // friend class GraphWrapper<Graph>; 1089 // typename Graph::EdgeIt e; 1090 // public: 1091 // EdgeIt() { } 1092 // EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } 1093 // EdgeIt(const Invalid& i) : e(i) { } 1094 // EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { } 1095 // operator Edge() const { return Edge(typename Graph::Edge(e)); } 1096 // }; 1022 /// experimentral, do not try it. 1023 /// It eats a bipartite graph, oriented from S to T. 1024 /// Such one can be made e.g. by the above wrapper. 1025 template<typename Graph> 1026 class stGraphWrapper : public GraphWrapper<Graph> { 1027 public: 1028 class Node; 1029 //GN, int 1030 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend, 1031 //es a vege a false azaz (invalid, 3) 1032 class NodeIt; 1033 //GNI, int 1034 class Edge; 1035 //GE, int, GN 1036 //0 normalis, 1 s>vmi, 2 vmi>t, ez a sorrend, 1037 //invalid: (invalid, 3, invalid) 1038 class OutEdgeIt; 1039 //GO, int, GNI 1040 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid) 1041 //sbol (invalid, 1, first), ... (invalid, 3, invalid) 1042 //tbol (invalid, 3, invalid) 1043 class InEdgeIt; 1044 //GI, int, GNI 1045 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid) 1046 //sbe (invalid, 3, invalid) 1047 //tbe (invalid, 2, first), ... (invalid, 3, invalid) 1048 class EdgeIt; 1049 //(first, 0, invalid) ... 1050 //(invalid, 1, vmi) 1051 //(invalid, 2, vmi) 1052 //invalid, 3, invalid) 1053 template <typename T> class NodeMap; 1054 template <typename T> class EdgeMap; 1055 1056 // template <typename T> friend class NodeMap; 1057 // template <typename T> friend class EdgeMap; 1058 1059 const Node S_NODE; 1060 const Node T_NODE; 1061 1062 static const bool S_CLASS=false; 1063 static const bool T_CLASS=true; 1064 1065 stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , 1066 S_NODE(INVALID, 1), 1067 T_NODE(INVALID, 2) { } 1068 1069 class Node : public Graph::Node { 1070 protected: 1071 friend class GraphWrapper<Graph>; 1072 friend class stGraphWrapper<Graph>; 1073 template <typename T> friend class stGraphWrapper<Graph>::NodeMap; 1074 int spec; 1075 public: 1076 Node() { } 1077 Node(const typename Graph::Node& _n, int _spec=0) : 1078 Graph::Node(_n), spec(_spec) { } 1079 Node(const Invalid& i) : Graph::Node(i), spec(3) { } 1080 friend bool operator==(const Node& u, const Node& v) { 1081 return (u.spec==v.spec && 1082 static_cast<typename Graph::Node>(u)== 1083 static_cast<typename Graph::Node>(v)); 1084 } 1085 friend bool operator!=(const Node& u, const Node& v) { 1086 return (v.spec!=u.spec  1087 static_cast<typename Graph::Node>(u)!= 1088 static_cast<typename Graph::Node>(v)); 1089 } 1090 int getSpec() const { return spec; } 1091 }; 1092 class NodeIt { 1093 friend class GraphWrapper<Graph>; 1094 friend class stGraphWrapper<Graph>; 1095 typename Graph::NodeIt n; 1096 int spec; 1097 public: 1098 NodeIt() { } 1099 NodeIt(const typename Graph::NodeIt& _n, int _spec) : 1100 n(_n), spec(_spec) { } 1101 NodeIt(const Invalid& i) : n(i), spec(3) { } 1102 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 1103 if (!_G>valid(n)) spec=1; 1104 } 1105 operator Node() const { return Node(n, spec); } 1106 }; 1107 class Edge : public Graph::Edge { 1108 friend class GraphWrapper<Graph>; 1109 friend class stGraphWrapper<Graph>; 1110 template <typename T> friend class stGraphWrapper<Graph>::EdgeMap; 1111 int spec; 1112 typename Graph::Node n; 1113 public: 1114 Edge() { } 1115 Edge(const typename Graph::Edge& _e, int _spec, 1116 const typename Graph::Node& _n) : 1117 Graph::Edge(_e), spec(_spec), n(_n) { 1118 } 1119 Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { } 1120 friend bool operator==(const Edge& u, const Edge& v) { 1121 return (u.spec==v.spec && 1122 static_cast<typename Graph::Edge>(u)== 1123 static_cast<typename Graph::Edge>(v) && 1124 u.n==v.n); 1125 } 1126 friend bool operator!=(const Edge& u, const Edge& v) { 1127 return (v.spec!=u.spec  1128 static_cast<typename Graph::Edge>(u)!= 1129 static_cast<typename Graph::Edge>(v)  1130 u.n!=v.n); 1131 } 1132 int getSpec() const { return spec; } 1133 }; 1134 class OutEdgeIt { 1135 friend class GraphWrapper<Graph>; 1136 friend class stGraphWrapper<Graph>; 1137 typename Graph::OutEdgeIt e; 1138 int spec; 1139 typename Graph::ClassNodeIt n; 1140 public: 1141 OutEdgeIt() { } 1142 OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 1143 const typename Graph::ClassNodeIt& _n) : 1144 e(_e), spec(_spec), n(_n) { 1145 } 1146 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } 1147 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) { 1148 switch (_n.spec) { 1149 case 0 : 1150 if (_G.graph>inSClass) { //S, van normalis kiel 1151 e=typename Graph::OutEdgeIt(*(_G.graph), 1152 typename Graph::Node(_n)); 1153 spec=0; 1154 n=INVALID; 1155 if (!_G.graph>valid(e)) spec=3; 1156 } else { //T, specko kiel van 1157 e=INVALID; 1158 spec=2; 1159 n=_n; 1160 } 1161 break; 1162 case 1: 1163 e=INVALID; 1164 spec=1; 1165 _G.graph>first(n, S_CLASS); //s>vmi; 1166 if (!_G.graph>valid(n)) spec=3; //Ha S ures 1167 break; 1168 case 2: 1169 e=INVALID; 1170 spec=3; 1171 n=INVALID; 1172 break; 1173 } 1174 } 1175 operator Edge() const { return Edge(e, spec, n); } 1176 }; 1177 class InEdgeIt { 1178 friend class GraphWrapper<Graph>; 1179 friend class stGraphWrapper<Graph>; 1180 typename Graph::InEdgeIt e; 1181 int spec; 1182 typename Graph::ClassNodeIt n; 1183 public: 1184 InEdgeIt() { } 1185 InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 1186 const typename Graph::ClassNodeIt& _n) : 1187 e(_e), spec(_spec), n(_n) { 1188 } 1189 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } 1190 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) { 1191 switch (_n.spec) { 1192 case 0 : 1193 if (_G.graph>inTClass) { //T, van normalis beel 1194 e=typename Graph::InEdgeIt(*(_G.graph), 1195 typename Graph::Node(_n)); 1196 spec=0; 1197 n=INVALID; 1198 if (!_G.graph>valid(e)) spec=3; 1199 } else { //S, specko beel van 1200 e=INVALID; 1201 spec=1; 1202 n=_n; 1203 } 1204 break; 1205 case 1: 1206 e=INVALID; 1207 spec=3; 1208 n=INVALID; 1209 case 2: 1210 e=INVALID; 1211 spec=1; 1212 _G.graph>first(n, T_CLASS); //vmi>t; 1213 if (!_G.graph>valid(n)) spec=3; //Ha T ures 1214 break; 1215 } 1216 } 1217 operator Edge() const { return Edge(e, spec, n); } 1218 }; 1219 class EdgeIt { 1220 friend class GraphWrapper<Graph>; 1221 friend class stGraphWrapper<Graph>; 1222 typename Graph::EdgeIt e; 1223 int spec; 1224 typename Graph::ClassNodeIt n; 1225 public: 1226 EdgeIt() { } 1227 EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 1228 const typename Graph::ClassNodeIt& _n) : 1229 e(_e), spec(_spec), n(_n) { } 1230 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } 1231 EdgeIt(const GraphWrapper<Graph>& _G) : 1232 e(*(_G.graph)), spec(0), n(INVALID) { 1233 if (!_G.graph>valid(e)) { 1234 spec=1; 1235 _G.graph>first(n, S_CLASS); 1236 if (!_G.graph>valid(n)) { //Ha S ures 1237 spec=2; 1238 _G.graph>first(n, T_CLASS); 1239 if (!_G.graph>valid(n)) { //Ha T ures 1240 spec=3; 1241 } 1242 } 1243 } 1244 } 1245 operator Edge() const { return Edge(e, spec, n); } 1246 }; 1097 1247 1098 // NodeIt& first(NodeIt& i) const { 1099 // i=NodeIt(*this); return i; 1100 // } 1101 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1102 // i=OutEdgeIt(*this, p); return i; 1103 // } 1104 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1105 // i=InEdgeIt(*this, p); return i; 1106 // } 1107 // EdgeIt& first(EdgeIt& i) const { 1108 // i=EdgeIt(*this); return i; 1109 // } 1110 1111 // NodeIt& next(NodeIt& i) const { graph>next(i.n); return i; } 1112 // OutEdgeIt& next(OutEdgeIt& i) const { graph>next(i.e); return i; } 1113 // InEdgeIt& next(InEdgeIt& i) const { graph>next(i.e); return i; } 1114 // EdgeIt& next(EdgeIt& i) const { graph>next(i.e); return i; } 1115 1116 // Node head(const Edge& e) const { 1117 // return Node(graph>head(static_cast<typename Graph::Edge>(e))); } 1118 // Node tail(const Edge& e) const { 1119 // return Node(graph>tail(static_cast<typename Graph::Edge>(e))); } 1120 1121 // bool valid(const Node& n) const { 1122 // return graph>valid(static_cast<typename Graph::Node>(n)); } 1123 // bool valid(const Edge& e) const { 1124 // return graph>valid(static_cast<typename Graph::Edge>(e)); } 1125 1126 // int nodeNum() const { return graph>nodeNum(); } 1127 // int edgeNum() const { return graph>edgeNum(); } 1248 NodeIt& first(NodeIt& i) const { 1249 i=NodeIt(*this); return i; 1250 } 1251 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1252 i=OutEdgeIt(*this, p); return i; 1253 } 1254 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1255 i=InEdgeIt(*this, p); return i; 1256 } 1257 EdgeIt& first(EdgeIt& i) const { 1258 i=EdgeIt(*this); return i; 1259 } 1260 1261 NodeIt& next(NodeIt& i) const { 1262 switch (i.spec) { 1263 case 0: 1264 graph>next(i.n); 1265 if (!graph>valid(i.n)) { 1266 i.spec=1; 1267 } 1268 break; 1269 case 1: 1270 i.spec=2; 1271 break; 1272 case 2: 1273 i.spec=3; 1274 break; 1275 } 1276 return i; 1277 } 1278 OutEdgeIt& next(OutEdgeIt& i) const { 1279 switch (i.spec) { 1280 case 0: //normal edge 1281 typename Graph::Node v=graph>aNode(i.e); 1282 graph>next(i.e); 1283 if (!graph>valid(i.e)) { //Az igazi elek vegere ertunk 1284 if (graph>inSClass(v)) { //S, nincs kiel 1285 i.spec=3; 1286 i.n=INVALID; 1287 } else { //T, van kiel 1288 i.spec=2; 1289 i.n=v; 1290 } 1291 } 1292 break; 1293 case 1: //s>vmi 1294 graph>next(i.n); 1295 if (!graph>valid(i.n)) i.spec=3; 1296 break; 1297 case 2: //vmi>t 1298 i.spec=3; 1299 i.n=INVALID; 1300 break; 1301 } 1302 return i; 1303 } 1304 InEdgeIt& next(InEdgeIt& i) const { 1305 switch (i.spec) { 1306 case 0: //normal edge 1307 typename Graph::Node v=graph>aNode(i.e); 1308 graph>next(i.e); 1309 if (!graph>valid(i.e)) { //Az igazi elek vegere ertunk 1310 if (graph>inTClass(v)) { //S, nincs beel 1311 i.spec=3; 1312 i.n=INVALID; 1313 } else { //S, van beel 1314 i.spec=1; 1315 i.n=v; 1316 } 1317 } 1318 break; 1319 case 1: //s>vmi 1320 i.spec=3; 1321 i.n=INVALID; 1322 break; 1323 case 2: //vmi>t 1324 graph>next(i.n); 1325 if (!graph>valid(i.n)) i.spec=3; 1326 break; 1327 } 1328 return i; 1329 } 1330 1331 EdgeIt& next(EdgeIt& i) const { 1332 switch (i.spec) { 1333 case 0: 1334 graph>next(i.e); 1335 if (!graph>valid(i.e)) { 1336 i.spec=1; 1337 graph>first(n, S_CLASS); 1338 if (!graph>valid(i.n)) { 1339 i.spec=2; 1340 graph>first(n, T_CLASS); 1341 if (!graph>valid(i.n)) spec=3; 1342 } 1343 } 1344 break; 1345 case 1: 1346 graph>next(i.n); 1347 if (!graph>valid(i.n)) { 1348 i.spec=2; 1349 graph>first(n, T_CLASS); 1350 if (!graph>valid(i.n)) spec=3; 1351 } 1352 break; 1353 case 2: 1354 graph>next(i.n); 1355 if (!graph>valid(i.n)) i.spec=3; 1356 break; 1357 } 1358 return i; 1359 } 1360 1361 Node tail(const Edge& e) const { 1362 switch (e.spec) { 1363 case 0: 1364 return Node(graph>tail(e)); 1365 break; 1366 case 1: 1367 return S_NODE; 1368 break; 1369 case 2: 1370 return Node(e.n); 1371 break; 1372 } 1373 } 1374 Node head(const Edge& e) const { 1375 switch (e.spec) { 1376 case 0: 1377 return Node(graph>head(e)); 1378 break; 1379 case 1: 1380 return Node(e.n); 1381 break; 1382 case 2: 1383 return T_NODE; 1384 break; 1385 } 1386 } 1387 1388 bool valid(const Node& n) const { return (n.spec<3); } 1389 bool valid(const Edge& e) const { return (e.spec<3); } 1390 1391 // int nodeNum() const { return graph>nodeNum(); } 1392 // int edgeNum() const { return graph>edgeNum(); } 1128 1393 1129 // Node aNode(const OutEdgeIt& e) const { return Node(graph>aNode(e.e)); }1130 // Node aNode(const InEdgeIt& e) const { return Node(graph>aNode(e.e)); }1131 // Node bNode(const OutEdgeIt& e) const { return Node(graph>bNode(e.e)); }1132 // Node bNode(const InEdgeIt& e) const { return Node(graph>bNode(e.e)); }1394 Node aNode(const OutEdgeIt& e) const { return tail(e); } 1395 Node aNode(const InEdgeIt& e) const { return head(e); } 1396 Node bNode(const OutEdgeIt& e) const { return head(e); } 1397 Node bNode(const InEdgeIt& e) const { return tail(e); } 1133 1398 1134 // 1135 // 1136 // 1137 1138 // 1139 // 1399 // Node addNode() const { return Node(graph>addNode()); } 1400 // Edge addEdge(const Node& tail, const Node& head) const { 1401 // return Edge(graph>addEdge(tail, head)); } 1402 1403 // void erase(const Node& i) const { graph>erase(i); } 1404 // void erase(const Edge& i) const { graph>erase(i); } 1140 1405 1141 // 1406 // void clear() const { graph>clear(); } 1142 1407 1143 // template<typename T> class NodeMap : public Graph::NodeMap<T> { 1144 // public: 1145 // NodeMap(const GraphWrapper<Graph>& _G) : 1146 // Graph::NodeMap<T>(*(_G.graph)) { } 1147 // NodeMap(const GraphWrapper<Graph>& _G, T a) : 1148 // Graph::NodeMap<T>(*(_G.graph), a) { } 1149 // }; 1150 1151 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 1152 // public: 1153 // EdgeMap(const GraphWrapper<Graph>& _G) : 1154 // Graph::EdgeMap<T>(*(_G.graph)) { } 1155 // EdgeMap(const GraphWrapper<Graph>& _G, T a) : 1156 // Graph::EdgeMap<T>(*(_G.graph), a) { } 1157 // }; 1158 // }; 1408 template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> { 1409 T s_value, t_value; 1410 public: 1411 NodeMap(const stGraphWrapper<Graph>& _G) : 1412 GraphWrapper<Graph>::NodeMap<T>(_G) { } 1413 NodeMap(const stGraphWrapper<Graph>& _G, T a) : 1414 GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a), t_value(a) { } 1415 T operator[](const Node& n) const { 1416 switch (n.spec) { 1417 case 0: 1418 return (*this)[n]; 1419 break; 1420 case 1: 1421 return s_value; 1422 break; 1423 case 2: 1424 return t_value; 1425 break; 1426 } 1427 } 1428 void set(const Node& n, T t) { 1429 switch (n.spec) { 1430 case 0: 1431 GraphWrapper<Graph>::NodeMap<T>::set(n, t); 1432 break; 1433 case 1: 1434 s_value=t; 1435 break; 1436 case 2: 1437 t_value=t; 1438 break; 1439 } 1440 } 1441 }; 1442 1443 template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> { 1444 typename GraphWrapper<Graph>::NodeMap<T> node_value; 1445 public: 1446 EdgeMap(const stGraphWrapper<Graph>& _G) : 1447 GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { } 1448 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : 1449 GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { } 1450 T operator[](const Edge& e) const { 1451 switch (e.spec) { 1452 case 0: 1453 return (*this)[e]; 1454 break; 1455 case 1: 1456 return node_value[e.n]; 1457 break; 1458 case 2: 1459 return node_value[e.n]; 1460 break; 1461 } 1462 } 1463 void set(const Edge& e, T t) { 1464 switch (e.spec) { 1465 case 0: 1466 GraphWrapper<Graph>::set(e, t); 1467 break; 1468 case 1: 1469 node_value.set(e, t); 1470 break; 1471 case 2: 1472 node_value.set(e, t); 1473 break; 1474 } 1475 } 1476 }; 1477 }; 1478 1159 1479 1160 1480 } //namespace hugo 
src/work/marci/lg_vs_sg.cc
r334 r379 36 36 Graph::EdgeMap<int> flow(G); //0 flow 37 37 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 38 pre_flow_test(G, s, t, cap, flow );38 pre_flow_test(G, s, t, cap, flow, true); 39 39 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 40 40 max_flow_test(G, s, t, cap, flow); … … 110 110 Graph::EdgeMap<int> flow(G); //0 flow 111 111 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 112 pre_flow_test(G, s, t, cap, flow );112 pre_flow_test(G, s, t, cap, flow, true); 113 113 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 114 114 max_flow_test(G, s, t, cap, flow);
Note: See TracChangeset
for help on using the changeset viewer.