Changeset 263:f24f276e0b6b in lemon-0.x for src/work
- Timestamp:
- 03/30/04 09:07:44 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@369
- Location:
- src/work
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/edmonds_karp.h
r259 r263 314 314 } 315 315 316 // template<typename MutableGraph> bool augmentOnBlockingFlow() { 317 // bool _augment=false; 318 319 // AugGraph res_graph(*G, *flow, *capacity); 320 321 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 322 // BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); 323 324 // bfs.pushAndSetReached(s); 325 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 326 // while ( !bfs.finished() ) { 327 // AugOutEdgeIt e=bfs; 328 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 329 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 330 // } 331 332 // ++bfs; 333 // } //computing distances from s in the residual graph 334 335 // MutableGraph F; 336 // typename AugGraph::NodeMap<typename MutableGraph::Node> 337 // res_graph_to_F(res_graph); 338 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 339 // res_graph_to_F.set(n, F.addNode()); 340 // } 341 342 // typename MutableGraph::Node sF=res_graph_to_F.get(s); 343 // typename MutableGraph::Node tF=res_graph_to_F.get(t); 344 345 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 346 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 347 348 // //Making F to the graph containing the edges of the residual graph 349 // //which are in some shortest paths 350 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 351 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 352 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 353 // original_edge.update(); 354 // original_edge.set(f, e); 355 // residual_capacity.update(); 356 // residual_capacity.set(f, res_graph.free(e)); 357 // } 358 // } 359 360 // bool __augment=true; 361 362 // while (__augment) { 363 // __augment=false; 364 // //computing blocking flow with dfs 365 // typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 366 // DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); 367 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 368 // pred.set(sF, typename MutableGraph::Edge(INVALID)); 369 // //invalid iterators for sources 370 371 // typename MutableGraph::NodeMap<Number> free(F); 372 373 // dfs.pushAndSetReached(sF); 374 // while (!dfs.finished()) { 375 // ++dfs; 376 // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 377 // if (dfs.isBNodeNewlyReached()) { 378 // typename MutableGraph::Node v=F.aNode(dfs); 379 // typename MutableGraph::Node w=F.bNode(dfs); 380 // pred.set(w, dfs); 381 // if (F.valid(pred.get(v))) { 382 // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 383 // } else { 384 // free.set(w, residual_capacity.get(dfs)); 385 // } 386 // if (w==tF) { 387 // __augment=true; 388 // _augment=true; 389 // break; 390 // } 391 392 // } else { 393 // F.erase(typename MutableGraph::OutEdgeIt(dfs)); 394 // } 395 // } 396 // } 397 398 // if (__augment) { 399 // typename MutableGraph::Node n=tF; 400 // Number augment_value=free.get(tF); 401 // while (F.valid(pred.get(n))) { 402 // typename MutableGraph::Edge e=pred.get(n); 403 // res_graph.augment(original_edge.get(e), augment_value); 404 // n=F.tail(e); 405 // if (residual_capacity.get(e)==augment_value) 406 // F.erase(e); 407 // else 408 // residual_capacity.set(e, residual_capacity.get(e)-augment_value); 409 // } 410 // } 411 412 // } 413 414 // return _augment; 415 // } 416 417 template<typename GraphWrapper> 418 class DistanceMap { 419 protected: 420 GraphWrapper gw; 421 typename GraphWrapper::NodeMap<int> dist; 422 public: 423 DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } 424 //NodeMap(const ListGraph& _G, T a) : 425 //G(_G), container(G.node_id, a) { } 426 void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; } 427 int get(const typename GraphWrapper::Node& n) const { return dist[n]; } 428 bool get(const typename GraphWrapper::Edge& e) const { 429 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); 430 } 431 //typename std::vector<T>::reference operator[](Node n) { 432 //return container[/*G.id(n)*/n.node->id]; } 433 //typename std::vector<T>::const_reference operator[](Node n) const { 434 //return container[/*G.id(n)*/n.node->id]; 435 }; 436 316 437 template<typename MutableGraph> bool augmentOnBlockingFlow() { 317 438 bool _augment=false; … … 320 441 321 442 typedef typename AugGraph::NodeMap<bool> ReachedMap; 322 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);443 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); 323 444 324 445 bfs.pushAndSetReached(s); 325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 446 //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 447 DistanceMap<AugGraph> dist(res_graph); 326 448 while ( !bfs.finished() ) { 327 449 AugOutEdgeIt e=bfs; … … 329 451 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 330 452 } 331 332 453 ++bfs; 333 454 } //computing distances from s in the residual graph 334 455 456 // MutableGraph F; 457 // typename AugGraph::NodeMap<typename MutableGraph::Node> 458 // res_graph_to_F(res_graph); 459 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 460 // res_graph_to_F.set(n, F.addNode()); 461 // } 462 463 // typename MutableGraph::Node sF=res_graph_to_F.get(s); 464 // typename MutableGraph::Node tF=res_graph_to_F.get(t); 465 466 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 467 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 468 469 // //Making F to the graph containing the edges of the residual graph 470 // //which are in some shortest paths 471 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 472 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 473 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 474 // original_edge.update(); 475 // original_edge.set(f, e); 476 // residual_capacity.update(); 477 // residual_capacity.set(f, res_graph.free(e)); 478 // } 479 // } 480 335 481 MutableGraph F; 482 typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph; 483 FilterResGraph filter_res_graph(res_graph, dist); 336 484 typename AugGraph::NodeMap<typename MutableGraph::Node> 337 485 res_graph_to_F(res_graph); … … 364 512 //computing blocking flow with dfs 365 513 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 366 DfsIterator5< TrivGraphWrapper<MutableGraph> /*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);514 DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F); 367 515 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 368 516 pred.set(sF, typename MutableGraph::Edge(INVALID)); … … 414 562 return _augment; 415 563 } 564 416 565 template<typename MutableGraph> bool augmentOnBlockingFlow1() { 417 566 bool _augment=false; … … 421 570 //bfs for distances on the residual graph 422 571 typedef typename AugGraph::NodeMap<bool> ReachedMap; 423 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);572 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); 424 573 bfs.pushAndSetReached(s); 425 574 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's -
src/work/marci/graph_wrapper.h
r259 r263 92 92 93 93 public: 94 typedef typename GraphWrapper::BaseGraph BaseGraph;94 //typedef typename GraphWrapper::BaseGraph BaseGraph; 95 95 96 96 typedef typename GraphWrapper::Node Node; … … 106 106 GraphWrapperSkeleton(GraphWrapper _gw) : gw(_gw) { } 107 107 108 void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }109 BaseGraph& getGraph() const { return gw.getGraph(); }108 //void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); } 109 //BaseGraph& getGraph() const { return gw.getGraph(); } 110 110 111 111 template<typename I> I& first(I& i) const { return gw.first(i); } … … 343 343 }; 344 344 345 //Subgraph on the same node-set and partial edge-set 346 template<typename GraphWrapper, typename EdgeFilterMap> 347 class SubGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> { 348 protected: 349 EdgeFilterMap* filter_map; 350 public: 351 typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node; 352 typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt; 353 typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge; 354 typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt; 355 typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt; 356 typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt; 357 358 SubGraphWrapper(GraphWrapper _gw, EdgeFilterMap& _filter_map) : 359 GraphWrapperSkeleton<GraphWrapper>(_gw), filter_map(&_filter_map) { } 360 361 template<typename I> I& first(I& i) const { 362 gw.first(i); 363 while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } 364 return i; 365 } 366 template<typename I, typename P> I& first(I& i, const P& p) const { 367 gw.first(i, p); 368 while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } 369 return i; 370 } 371 372 //template<typename I> I getNext(const I& i) const { 373 // return gw.getNext(i); 374 //} 375 template<typename I> I& next(I &i) const { 376 gw.next(i); 377 while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); } 378 return i; 379 } 380 381 template< typename It > It first() const { 382 It e; this->first(e); return e; } 383 384 template< typename It > It first(const Node& v) const { 385 It e; this->first(e, v); return e; } 386 }; 345 387 346 388 // template<typename GraphWrapper> … … 858 900 // } 859 901 }; 902 903 //FIXME This is just for having InEdgeIt 904 typedef void InEdgeIt; 860 905 861 906 class EdgeIt : public Edge { … … 1006 1051 return ((e.out_or_in) ? gw.bNode(e.out) : gw.bNode(e.in)); } 1007 1052 1053 int nodeNum() const { return gw.nodeNum(); } 1054 //FIXME 1055 //int edgeNum() const { return gw.edgeNum(); } 1056 1057 1008 1058 int id(Node v) const { return gw.id(v); } 1009 1059
Note: See TracChangeset
for help on using the changeset viewer.