Changeset 155:8c6292ec54c6 in lemon0.x for src/work/marci
 Timestamp:
 03/04/04 20:38:07 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@217
 Location:
 src/work/marci
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/edmonds_karp_demo.cc
r146 r155 6 6 #include <edmonds_karp.hh> 7 7 #include <time_measure.h> 8 #include <graph_wrapper.h> 8 9 9 10 using namespace hugo; … … 58 59 ListGraph::EdgeMap<int> cap(G); 59 60 readDimacsMaxFlow(std::cin, G, s, t, cap); 61 /* 62 typedef TrivGraphWrapper<ListGraph> TGW; 63 TGW gw(G); 64 TGW::EachNodeIt sw; 65 gw.getFirst(sw); 66 std::cout << "p1:" << gw.nodeNum() << std::endl; 67 gw.erase(sw); 68 std::cout << "p2:" << gw.nodeNum() << std::endl; 69 70 typedef const ListGraph cLG; 71 typedef TrivGraphWrapper<const cLG> CTGW; 72 CTGW cgw(G); 73 CTGW::EachNodeIt csw; 74 cgw.getFirst(csw); 75 std::cout << "p1:" << cgw.nodeNum() << std::endl; 76 //cgw.erase(csw); 77 std::cout << "p2:" << cgw.nodeNum() << std::endl; 78 */ 60 79 61 80 { 
src/work/marci/graph_wrapper.h
r148 r155 13 13 14 14 typedef typename Graph::NodeIt NodeIt; 15 typedef typename Graph::EachNodeIt EachNodeIt; 16 15 17 typedef typename Graph::EdgeIt EdgeIt; 16 17 typedef typename Graph::EachNodeIt EachNodeIt;18 19 18 typedef typename Graph::OutEdgeIt OutEdgeIt; 20 19 typedef typename Graph::InEdgeIt InEdgeIt; 21 typedef typename Graph::SymEdgeIt SymEdgeIt;20 //typedef typename Graph::SymEdgeIt SymEdgeIt; 22 21 typedef typename Graph::EachEdgeIt EachEdgeIt; 23 24 int nodeNum() const { return graph>nodeNum(); }25 int edgeNum() const { return graph>edgeNum(); }26 22 27 23 template<typename I> I& getFirst(I& i) const { return graph>getFirst(i); } 28 24 template<typename I, typename P> I& getFirst(I& i, const P& p) const { 29 25 return graph>getFirst(i, p); } 30 //template<typename I> I next(const I i); { return graph>goNext(i); } 31 //template<typename I> I &goNext(I &i); { return graph>goNext(i); } 26 27 template<typename I> I getNext(const I& i) const { 28 return graph>getNext(i); } 29 template<typename I> I& next(I &i) const { return graph>next(i); } 32 30 33 31 template< typename It > It first() const { 34 32 It e; getFirst(e); return e; } 35 33 36 template< typename It > It first( NodeItv) const {34 template< typename It > It first(const NodeIt& v) const { 37 35 It e; getFirst(e, v); return e; } 38 36 39 37 NodeIt head(const EdgeIt& e) const { return graph>head(e); } 40 38 NodeIt tail(const EdgeIt& e) const { return graph>tail(e); } 39 40 template<typename I> bool valid(const I& i) const 41 { return graph>valid(i); } 42 43 //template<typename I> void setInvalid(const I &i); 44 //{ return graph>setInvalid(i); } 45 46 int nodeNum() const { return graph>nodeNum(); } 47 int edgeNum() const { return graph>edgeNum(); } 41 48 42 49 template<typename I> NodeIt aNode(const I& e) const { … … 45 52 return graph>bNode(e); } 46 53 47 //template<typename I> bool valid(const I& i)48 //{ return graph>valid(i); }49 50 //template<typename I> void setInvalid(const I &i);51 //{ return graph>setInvalid(i); }52 53 54 NodeIt addNode() const { return graph>addNode(); } 54 55 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { … … 58 59 59 60 void clear() const { graph>clear(); } 60 61 61 62 template<typename T> class NodeMap : public Graph::NodeMap<T> { 62 63 public: 63 NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { } 64 NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { } 65 }; 66 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { }; 67 64 NodeMap(const TrivGraphWrapper<Graph>& _G) : 65 Graph::NodeMap<T>(*(_G.G)) { } 66 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) : 67 Graph::NodeMap<T>(*(_G.G), a) { } 68 }; 69 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 70 public: 71 EdgeMap(const TrivGraphWrapper<Graph>& _G) : 72 Graph::EdgeMap<T>(*(_G.G)) { } 73 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) : 74 Graph::EdgeMap<T>(*(_G.G), a) { } 75 }; 76 68 77 void setGraph(Graph& _graph) { graph = &_graph; } 69 Graph& getGraph() { return (*graph); }78 Graph& getGraph() const { return (*graph); } 70 79 71 80 //TrivGraphWrapper() : graph(0) { } … … 74 83 75 84 template<typename Graph> 76 class ConstTrivGraphWrapper { 77 const Graph* graph; 85 class RevGraphWrapper 86 { 87 Graph* graph; 78 88 79 89 public: 80 90 typedef Graph BaseGraph; 81 91 82 typedef typename Graph::NodeIt NodeIt; 92 typedef typename Graph::NodeIt NodeIt; 93 typedef typename Graph::EachNodeIt EachNodeIt; 94 83 95 typedef typename Graph::EdgeIt EdgeIt; 84 85 typedef typename Graph::EachNodeIt EachNodeIt; 86 87 typedef typename Graph::OutEdgeIt OutEdgeIt; 88 typedef typename Graph::InEdgeIt InEdgeIt; 89 typedef typename Graph::SymEdgeIt SymEdgeIt; 96 typedef typename Graph::OutEdgeIt InEdgeIt; 97 typedef typename Graph::InEdgeIt OutEdgeIt; 98 //typedef typename Graph::SymEdgeIt SymEdgeIt; 90 99 typedef typename Graph::EachEdgeIt EachEdgeIt; 91 92 int nodeNum() const { return graph>nodeNum(); }93 int edgeNum() const { return graph>edgeNum(); }94 100 95 101 template<typename I> I& getFirst(I& i) const { return graph>getFirst(i); } 96 102 template<typename I, typename P> I& getFirst(I& i, const P& p) const { 97 103 return graph>getFirst(i, p); } 98 //template<typename I> I next(const I i); { return graph>goNext(i); } 99 //template<typename I> I &goNext(I &i); { return graph>goNext(i); } 104 105 template<typename I> I getNext(const I& i) const { 106 return graph>getNext(i); } 107 template<typename I> I& next(I &i) const { return graph>next(i); } 100 108 101 109 template< typename It > It first() const { 102 110 It e; getFirst(e); return e; } 103 111 104 template< typename It > It first( NodeItv) const {112 template< typename It > It first(const NodeIt& v) const { 105 113 It e; getFirst(e, v); return e; } 106 114 107 NodeIt head(const EdgeIt& e) const { return graph>head(e); } 108 NodeIt tail(const EdgeIt& e) const { return graph>tail(e); } 115 NodeIt head(const EdgeIt& e) const { return graph>tail(e); } 116 NodeIt tail(const EdgeIt& e) const { return graph>head(e); } 117 118 template<typename I> bool valid(const I& i) const 119 { return graph>valid(i); } 120 121 //template<typename I> void setInvalid(const I &i); 122 //{ return graph>setInvalid(i); } 109 123 110 124 template<typename I> NodeIt aNode(const I& e) const { … … 112 126 template<typename I> NodeIt bNode(const I& e) const { 113 127 return graph>bNode(e); } 114 115 //template<typename I> bool valid(const I& i) 116 //{ return graph>valid(i); } 117 118 //template<typename I> void setInvalid(const I &i); 119 //{ return graph>setInvalid(i); } 120 128 121 129 NodeIt addNode() const { return graph>addNode(); } 122 130 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 123 131 return graph>addEdge(tail, head); } 124 132 125 template<typename I> void erase(const I& i) const { graph>erase(i); }126 127 void clear() const { graph>clear(); }128 129 template<typename T> class NodeMap : public Graph::NodeMap<T> {130 public:131 NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }132 NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }133 };134 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };135 136 void setGraph(const Graph& _graph) { graph = &_graph; }137 const Graph& getGraph() { return (*graph); }138 139 //ConstTrivGraphWrapper() : graph(0) { }140 ConstTrivGraphWrapper(const Graph& _graph) : graph(&_graph) { }141 };142 143 144 template<typename Graph>145 class RevGraphWrapper146 {147 Graph* graph;148 149 public:150 typedef Graph BaseGraph;151 152 typedef typename Graph::NodeIt NodeIt;153 typedef typename Graph::EdgeIt EdgeIt;154 155 typedef typename Graph::EachNodeIt EachNodeIt;156 157 typedef typename Graph::OutEdgeIt InEdgeIt;158 typedef typename Graph::InEdgeIt OutEdgeIt;159 typedef typename Graph::SymEdgeIt SymEdgeIt;160 typedef typename Graph::EachEdgeIt EachEdgeIt;161 162 133 int nodeNum() const { return graph>nodeNum(); } 163 134 int edgeNum() const { return graph>edgeNum(); } 164 165 template<typename I> I& getFirst(I& i) const { return graph>getFirst(i); } 166 template<typename I, typename P> I& getFirst(I& i, const P& p) const { 167 return graph>getFirst(i, p); } 168 //template<typename I> I next(const I i); { return graph>goNext(i); } 169 //template<typename I> I &goNext(I &i); { return graph>goNext(i); } 170 171 template< typename It > It first() const { 172 It e; getFirst(e); return e; } 173 174 template< typename It > It first(NodeIt v) const { 175 It e; getFirst(e, v); return e; } 176 177 NodeIt head(const EdgeIt& e) const { return graph>tail(e); } 178 NodeIt tail(const EdgeIt& e) const { return graph>head(e); } 179 180 template<typename I> NodeIt aNode(const I& e) const { 181 return graph>aNode(e); } 182 template<typename I> NodeIt bNode(const I& e) const { 183 return graph>bNode(e); } 184 185 //template<typename I> bool valid(const I i); 186 //{ return graph>valid(i); } 187 188 //template<typename I> void setInvalid(const I &i); 189 //{ return graph>setInvalid(i); } 190 191 NodeIt addNode() { return graph>addNode(); } 192 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 193 return graph>addEdge(tail, head); } 194 195 template<typename I> void erase(const I& i) { graph>erase(i); } 196 197 void clear() { graph>clear(); } 198 199 template<typename T> class NodeMap : public Graph::NodeMap<T> { }; 200 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { }; 201 135 136 template<typename I> void erase(const I& i) const { graph>erase(i); } 137 138 void clear() const { graph>clear(); } 139 140 template<typename T> class NodeMap : public Graph::NodeMap<T> { 141 public: 142 NodeMap(const RevGraphWrapper<Graph>& _G) : 143 Graph::NodeMap<T>(*(_G.G)) { } 144 NodeMap(const RevGraphWrapper<Graph>& _G, T a) : 145 Graph::NodeMap<T>(*(_G.G), a) { } 146 }; 147 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 148 public: 149 EdgeMap(const RevGraphWrapper<Graph>& _G) : 150 Graph::EdgeMap<T>(*(_G.G)) { } 151 EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : 152 Graph::EdgeMap<T>(*(_G.G), a) { } 153 }; 154 202 155 void setGraph(Graph& _graph) { graph = &_graph; } 203 Graph& getGraph() { return (*graph); }156 Graph& getGraph() const { return (*graph); } 204 157 205 158 //RevGraphWrapper() : graph(0) { } … … 207 160 }; 208 161 209 template<typename Graph> 210 class SymGraphWrapper 211 { 212 Graph* graph; 213 162 163 // template<typename Graph> 164 // class SymGraphWrapper 165 // { 166 // Graph* graph; 167 168 // public: 169 // typedef Graph BaseGraph; 170 171 // typedef typename Graph::NodeIt NodeIt; 172 // typedef typename Graph::EdgeIt EdgeIt; 173 174 // typedef typename Graph::EachNodeIt EachNodeIt; 175 176 // //FIXME tagekkel megcsinalni, hogy abbol csinaljon 177 // //iranyitatlant, ami van 178 // //mert csak 1 dolgot lehet be typedefelni 179 // typedef typename Graph::OutEdgeIt SymEdgeIt; 180 // //typedef typename Graph::InEdgeIt SymEdgeIt; 181 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 182 // typedef typename Graph::EachEdgeIt EachEdgeIt; 183 184 // int nodeNum() const { return graph>nodeNum(); } 185 // int edgeNum() const { return graph>edgeNum(); } 186 187 // template<typename I> I& getFirst(I& i) const { return graph>getFirst(i); } 188 // template<typename I, typename P> I& getFirst(I& i, const P& p) const { 189 // return graph>getFirst(i, p); } 190 // //template<typename I> I next(const I i); { return graph>goNext(i); } 191 // //template<typename I> I &goNext(I &i); { return graph>goNext(i); } 192 193 // template< typename It > It first() const { 194 // It e; getFirst(e); return e; } 195 196 // template< typename It > It first(NodeIt v) const { 197 // It e; getFirst(e, v); return e; } 198 199 // NodeIt head(const EdgeIt& e) const { return graph>head(e); } 200 // NodeIt tail(const EdgeIt& e) const { return graph>tail(e); } 201 202 // template<typename I> NodeIt aNode(const I& e) const { 203 // return graph>aNode(e); } 204 // template<typename I> NodeIt bNode(const I& e) const { 205 // return graph>bNode(e); } 206 207 // //template<typename I> bool valid(const I i); 208 // //{ return graph>valid(i); } 209 210 // //template<typename I> void setInvalid(const I &i); 211 // //{ return graph>setInvalid(i); } 212 213 // NodeIt addNode() { return graph>addNode(); } 214 // EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 215 // return graph>addEdge(tail, head); } 216 217 // template<typename I> void erase(const I& i) { graph>erase(i); } 218 219 // void clear() { graph>clear(); } 220 221 // template<typename T> class NodeMap : public Graph::NodeMap<T> { }; 222 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { }; 223 224 // void setGraph(Graph& _graph) { graph = &_graph; } 225 // Graph& getGraph() { return (*graph); } 226 227 // //SymGraphWrapper() : graph(0) { } 228 // SymGraphWrapper(Graph& _graph) : graph(&_graph) { } 229 // }; 230 231 232 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 233 class ResGraphWrapper { 214 234 public: 215 235 typedef Graph BaseGraph; 216 217 236 typedef typename Graph::NodeIt NodeIt; 218 typedef typename Graph::EdgeIt EdgeIt;219 220 237 typedef typename Graph::EachNodeIt EachNodeIt; 238 private: 239 typedef typename Graph::OutEdgeIt OldOutEdgeIt; 240 typedef typename Graph::InEdgeIt OldInEdgeIt; 241 const Graph* G; 242 FlowMap* flow; 243 const CapacityMap* capacity; 244 public: 245 ResGraphWrapper(const Graph& _G, FlowMap& _flow, 246 const CapacityMap& _capacity) : 247 G(&_G), flow(&_flow), capacity(&_capacity) { } 248 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 249 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { } 250 class EdgeIt; 251 class OutEdgeIt; 252 friend class EdgeIt; 253 friend class OutEdgeIt; 254 255 class EdgeIt { 256 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 257 protected: 258 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG; 259 const Graph* G; 260 FlowMap* flow; 261 const CapacityMap* capacity; 262 //OldSymEdgeIt sym; 263 OldOutEdgeIt out; 264 OldInEdgeIt in; 265 bool out_or_in; //true, iff out 266 public: 267 EdgeIt() : out_or_in(true) { } 268 EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : 269 G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { } 270 //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { } 271 Number free() const { 272 if (out_or_in) { 273 return (/*resG>*/capacity>get(out)/*resG>*/flow>get(out)); 274 } else { 275 return (/*resG>*/flow>get(in)); 276 } 277 } 278 bool valid() const { 279 return out_or_in && out.valid()  in.valid(); } 280 void augment(Number a) const { 281 if (out_or_in) { 282 /*resG>*/flow>set(out, /*resG>*/flow>get(out)+a); 283 } else { 284 /*resG>*/flow>set(in, /*resG>*/flow>get(in)a); 285 } 286 } 287 void print() { 288 if (out_or_in) { 289 std::cout << "out "; 290 if (out.valid()) 291 std::cout << G>id(G>tail(out)) << ""<< G>id(out) <<">"<< G>id(G>head(out)); 292 else 293 std::cout << "invalid"; 294 } 295 else { 296 std::cout << "in "; 297 if (in.valid()) 298 std::cout << G>id(G>head(in)) << "<"<< G>id(in) <<""<< G>id(G>tail(in)); 299 else 300 std::cout << "invalid"; 301 } 302 std::cout << std::endl; 303 } 304 }; 305 306 Number free(OldOutEdgeIt out) const { 307 return (/*resG>*/capacity>get(out)/*resG>*/flow>get(out)); 308 } 309 Number free(OldInEdgeIt in) const { 310 return (/*resG>*/flow>get(in)); 311 } 312 313 class OutEdgeIt : public EdgeIt { 314 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 315 public: 316 OutEdgeIt() { } 317 private: 318 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 319 //out=/*resG>*/G>template first<OldOutEdgeIt>(v); 320 G>getFirst(out, v); 321 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } 322 if (!out.valid()) { 323 out_or_in=0; 324 //in=/*resG>*/G>template first<OldInEdgeIt>(v); 325 G>getFirst(in, v); 326 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 327 } 328 } 329 public: 330 OutEdgeIt& operator++() { 331 if (out_or_in) { 332 NodeIt v=/*resG>*/G>aNode(out); 333 ++out; 334 while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } 335 if (!out.valid()) { 336 out_or_in=0; 337 G>getFirst(in, v); //=/*resG>*/G>template first<OldInEdgeIt>(v); 338 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 339 } 340 } else { 341 ++in; 342 while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 343 } 344 return *this; 345 } 346 }; 347 348 class EachEdgeIt : public EdgeIt { 349 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 350 typename Graph::EachNodeIt v; 351 public: 352 EachEdgeIt() { } 353 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } 354 EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { 355 out_or_in=true; 356 G>getFirst(v); 357 if (v.valid()) G>getFirst(out, v); else out=OldOutEdgeIt(); 358 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 359 while (v.valid() && !out.valid()) { 360 ++v; 361 if (v.valid()) G>getFirst(out, v); 362 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 363 } 364 if (!out.valid()) { 365 out_or_in=0; 366 G>getFirst(v); 367 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt(); 368 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 369 while (v.valid() && !in.valid()) { 370 ++v; 371 if (v.valid()) G>getFirst(in, v); 372 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 373 } 374 } 375 } 376 EachEdgeIt& operator++() { 377 if (out_or_in) { 378 ++out; 379 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 380 while (v.valid() && !out.valid()) { 381 ++v; 382 if (v.valid()) G>getFirst(out, v); 383 while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } 384 } 385 if (!out.valid()) { 386 out_or_in=0; 387 G>getFirst(v); 388 if (v.valid()) G>getFirst(in, v); else in=OldInEdgeIt(); 389 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 390 while (v.valid() && !in.valid()) { 391 ++v; 392 if (v.valid()) G>getFirst(in, v); 393 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 394 } 395 } 396 } else { 397 ++in; 398 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 399 while (v.valid() && !in.valid()) { 400 ++v; 401 if (v.valid()) G>getFirst(in, v); 402 while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } 403 } 404 } 405 return *this; 406 } 407 }; 408 409 void getFirst(EachNodeIt& v) const { G>getFirst(v); } 410 void getFirst(OutEdgeIt& e, NodeIt v) const { 411 e=OutEdgeIt(*G, v, *flow, *capacity); 412 } 413 void getFirst(EachEdgeIt& e) const { 414 e=EachEdgeIt(*G, *flow, *capacity); 415 } 416 417 EachNodeIt& next(EachNodeIt& n) const { return G>next(n); } 418 419 OutEdgeIt& next(OutEdgeIt& e) const { 420 if (e.out_or_in) { 421 NodeIt v=G>aNode(e.out); 422 ++(e.out); 423 while( G>valid(e.out) && !(e.free()>0) ) { ++(e.out); } 424 if (!G>valid(e.out)) { 425 e.out_or_in=0; 426 G>getFirst(e.in, v); //=/*resG>*/G>template first<OldInEdgeIt>(v); 427 while( G>valid(e.in) && !(e.free()>0) ) { ++(e.in); } 428 } 429 } else { 430 ++(e.in); 431 while( G>valid(e.in) && !(e.free()>0) ) { ++(e.in); } 432 } 433 return e; 434 } 435 436 EachEdgeIt& next(EachEdgeIt& e) const { 437 if (e.out_or_in) { 438 ++(e.out); 439 while (G>valid(e.out) && !(e.free()>0) ) { ++(e.out); } 440 while (G>valid(e.v) && !G>valid(e.out)) { 441 ++(e.v); 442 if (G>valid(e.v)) G>getFirst(e.out, e.v); 443 while (G>valid(e.out) && !(e.free()>0) ) { ++(e.out); } 444 } 445 if (!G>valid(e.out)) { 446 e.out_or_in=0; 447 G>getFirst(e.v); 448 if (G>valid(e.v)) G>getFirst(e.in, e.v); else e.in=OldInEdgeIt(); 449 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); } 450 while (G>valid(e.v) && !G>valid(e.in)) { 451 ++(e.v); 452 if (G>valid(e.v)) G>getFirst(e.in, e.v); 453 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); } 454 } 455 } 456 } else { 457 ++(e.in); 458 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); } 459 while (G>valid(e.v) && !G>valid(e.in)) { 460 ++(e.v); 461 if (G>valid(e.v)) G>getFirst(e.in, e.v); 462 while (G>valid(e.in) && !(e.free()>0) ) { ++(e.in); } 463 } 464 } 465 return e; 466 } 221 467 222 //FIXME tagekkel megcsinalni, hogy abbol csinaljon 223 //iranyitatlant, ami van 224 //mert csak 1 dolgot lehet be typedefelni 225 typedef typename Graph::OutEdgeIt SymEdgeIt; 226 //typedef typename Graph::InEdgeIt SymEdgeIt; 227 //typedef typename Graph::SymEdgeIt SymEdgeIt; 228 typedef typename Graph::EachEdgeIt EachEdgeIt; 229 230 int nodeNum() const { return graph>nodeNum(); } 231 int edgeNum() const { return graph>edgeNum(); } 232 233 template<typename I> I& getFirst(I& i) const { return graph>getFirst(i); } 234 template<typename I, typename P> I& getFirst(I& i, const P& p) const { 235 return graph>getFirst(i, p); } 236 //template<typename I> I next(const I i); { return graph>goNext(i); } 237 //template<typename I> I &goNext(I &i); { return graph>goNext(i); } 238 239 template< typename It > It first() const { 240 It e; getFirst(e); return e; } 241 242 template< typename It > It first(NodeIt v) const { 243 It e; getFirst(e, v); return e; } 244 245 NodeIt head(const EdgeIt& e) const { return graph>head(e); } 246 NodeIt tail(const EdgeIt& e) const { return graph>tail(e); } 247 248 template<typename I> NodeIt aNode(const I& e) const { 249 return graph>aNode(e); } 250 template<typename I> NodeIt bNode(const I& e) const { 251 return graph>bNode(e); } 252 253 //template<typename I> bool valid(const I i); 254 //{ return graph>valid(i); } 255 256 //template<typename I> void setInvalid(const I &i); 257 //{ return graph>setInvalid(i); } 258 259 NodeIt addNode() { return graph>addNode(); } 260 EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 261 return graph>addEdge(tail, head); } 262 263 template<typename I> void erase(const I& i) { graph>erase(i); } 264 265 void clear() { graph>clear(); } 266 267 template<typename T> class NodeMap : public Graph::NodeMap<T> { }; 268 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { }; 269 270 void setGraph(Graph& _graph) { graph = &_graph; } 271 Graph& getGraph() { return (*graph); } 272 273 //SymGraphWrapper() : graph(0) { } 274 SymGraphWrapper(Graph& _graph) : graph(&_graph) { } 468 469 template< typename It > 470 It first() const { 471 It e; 472 getFirst(e); 473 return e; 474 } 475 476 template< typename It > 477 It first(NodeIt v) const { 478 It e; 479 getFirst(e, v); 480 return e; 481 } 482 483 NodeIt tail(EdgeIt e) const { 484 return ((e.out_or_in) ? G>aNode(e.out) : G>aNode(e.in)); } 485 NodeIt head(EdgeIt e) const { 486 return ((e.out_or_in) ? G>bNode(e.out) : G>bNode(e.in)); } 487 488 NodeIt aNode(OutEdgeIt e) const { 489 return ((e.out_or_in) ? G>aNode(e.out) : G>aNode(e.in)); } 490 NodeIt bNode(OutEdgeIt e) const { 491 return ((e.out_or_in) ? G>bNode(e.out) : G>bNode(e.in)); } 492 493 int id(NodeIt v) const { return G>id(v); } 494 495 bool valid(NodeIt n) const { return G>valid(n); } 496 bool valid(EdgeIt e) const { 497 return e.out_or_in ? G>valid(e.out) : G>valid(e.in); } 498 499 template<typename T> class NodeMap : public Graph::NodeMap<T> { 500 public: 501 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) 502 : Graph::NodeMap<T>(*(_G.G)) { } 503 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, 504 T a) : Graph::NodeMap<T>(*(_G.G), a) { } 505 }; 506 507 // template <typename T> 508 // class NodeMap { 509 // typename Graph::NodeMap<T> node_map; 510 // public: 511 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { } 512 // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { } 513 // void set(NodeIt nit, T a) { node_map.set(nit, a); } 514 // T get(NodeIt nit) const { return node_map.get(nit); } 515 // }; 516 517 template <typename T> 518 class EdgeMap { 519 typename Graph::EdgeMap<T> forward_map, backward_map; 520 public: 521 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { } 522 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { } 523 void set(EdgeIt e, T a) { 524 if (e.out_or_in) 525 forward_map.set(e.out, a); 526 else 527 backward_map.set(e.in, a); 528 } 529 T get(EdgeIt e) { 530 if (e.out_or_in) 531 return forward_map.get(e.out); 532 else 533 return backward_map.get(e.in); 534 } 535 }; 536 275 537 }; 276 538 … … 423 685 // }; 424 686 425 426 // // FIXME: comparison should be made better!!!427 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>428 // class ConstResGraphWrapper429 // {430 // const Graph* graph;431 // const LowerMap* low;432 // FlowMap* flow;433 // const UpperMap* up;434 // public:435 // typedef Graph BaseGraph;436 437 // typedef typename Graph::NodeIt NodeIt;438 // typedef typename Graph::EdgeIt EdgeIt;439 440 // typedef typename Graph::EachNodeIt EachNodeIt;441 442 // class OutEdgeIt {443 // public:444 // //Graph::NodeIt n;445 // bool out_or_in;446 // typename Graph::SymEdgeIt sym;447 // };448 // class InEdgeIt {449 // public:450 // //Graph::NodeIt n;451 // bool out_or_in;452 // typename Graph::OutEdgeIt sym;453 // };454 // //typedef typename Graph::SymEdgeIt SymEdgeIt;455 // //typedef typename Graph::EachEdgeIt EachEdgeIt;456 457 // int nodeNum() const { return graph>nodeNum(); }458 // //int edgeNum() const { return graph>edgeNum(); }459 460 // NodeIt& getFirst(NodeIt& n) const { return graph>getFirst(n); }461 462 // // EachEdge and SymEdge is missing!!!!463 // // EdgeIt <> In/OutEdgeIt conversion is missing!!!!464 465 466 // //FIXME467 // OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const468 // {469 // e.n=n;470 // graph>getFirst(e.o,n);471 // while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o))472 // graph>goNext(e.o);473 // if(!graph>valid(e.o)) {474 // graph>getFirst(e.i,n);475 // while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))476 // graph>goNext(e.i);477 // }478 // return e;479 // }480 // /*481 // OutEdgeIt &goNext(OutEdgeIt &e)482 // {483 // if(graph>valid(e.o)) {484 // while(graph>valid(e.o) && fmap.get(e.o)>=himap.get(e.o))485 // graph>goNext(e.o);486 // if(graph>valid(e.o)) return e;487 // else graph>getFirst(e.i,e.n);488 // }489 // else {490 // while(graph>valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))491 // graph>goNext(e.i);492 // return e;493 // }494 // }495 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}496 // */497 // //bool valid(const OutEdgeIt e) { return graph>valid(e.o)graph>valid(e.i);}498 499 // //FIXME500 // InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const501 // {502 // e.n=n;503 // graph>getFirst(e.i,n);504 // while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i))505 // graph>goNext(e.i);506 // if(!graph>valid(e.i)) {507 // graph>getFirst(e.o,n);508 // while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))509 // graph>goNext(e.o);510 // }511 // return e;512 // }513 // /*514 // InEdgeIt &goNext(InEdgeIt &e)515 // {516 // if(graph>valid(e.i)) {517 // while(graph>valid(e.i) && fmap.get(e.i)>=himap.get(e.i))518 // graph>goNext(e.i);519 // if(graph>valid(e.i)) return e;520 // else graph>getFirst(e.o,e.n);521 // }522 // else {523 // while(graph>valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))524 // graph>goNext(e.o);525 // return e;526 // }527 // }528 // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}529 // */530 // //bool valid(const InEdgeIt e) { return graph>valid(e.i)graph>valid(e.o);}531 532 // //template<typename I> I &goNext(I &i); { return graph>goNext(i); }533 // //template<typename I> I next(const I i); { return graph>goNext(i); }534 535 // template< typename It > It first() const {536 // It e; getFirst(e); return e; }537 538 // template< typename It > It first(NodeIt v) const {539 // It e; getFirst(e, v); return e; }540 541 // NodeIt head(const EdgeIt& e) const { return graph>head(e); }542 // NodeIt tail(const EdgeIt& e) const { return graph>tail(e); }543 544 // template<typename I> NodeIt aNode(const I& e) const {545 // return graph>aNode(e); }546 // template<typename I> NodeIt bNode(const I& e) const {547 // return graph>bNode(e); }548 549 // //template<typename I> bool valid(const I i);550 // //{ return graph>valid(i); }551 552 // //template<typename I> void setInvalid(const I &i);553 // //{ return graph>setInvalid(i); }554 555 // NodeIt addNode() { return graph>addNode(); }556 // EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {557 // return graph>addEdge(tail, head); }558 559 // template<typename I> void erase(const I& i) { graph>erase(i); }560 561 // void clear() { graph>clear(); }562 563 // template<typename S> class NodeMap : public Graph::NodeMap<S> { };564 // template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };565 566 // void setGraph(const Graph& _graph) { graph = &_graph; }567 // const Graph& getGraph() { return (*graph); }568 569 // //ConstResGraphWrapper() : graph(0) { }570 // ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }571 // };572 573 574 575 576 577 687 } //namespace hugo 578 688
Note: See TracChangeset
for help on using the changeset viewer.