COIN-OR::LEMON - Graph Library

Changeset 311:6635b11938fe in lemon-0.x for src/work/marci/edmonds_karp.h


Ignore:
Timestamp:
04/06/04 14:00:34 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@429
Message:

gw

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/edmonds_karp.h

    r303 r311  
    1010#include <invalid.h>
    1111#include <graph_wrapper.h>
     12#include <maps.h>
    1213
    1314namespace hugo {
     
    354355
    355356      MG F;
    356       typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
    357       FilterResGW filter_res_graph(res_graph, dist);
     357      ConstMap<typename ResGW::Node, bool> true_map(true);
     358      typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
     359        DistanceMap<ResGW> > FilterResGW;
     360      FilterResGW filter_res_graph(res_graph, true_map, dist);
    358361      typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
    359362      {
     
    568571
    569572      //Subgraph containing the edges on some shortest paths
    570       typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
    571       FilterResGW filter_res_graph(res_graph, dist);
     573      ConstMap<typename ResGW::Node, bool> true_map(true);
     574      typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
     575        DistanceMap<ResGW> > FilterResGW;
     576      FilterResGW filter_res_graph(res_graph, true_map, dist);
    572577
    573578      //Subgraph, which is able to delete edges which are already
     
    592597
    593598        __augment=false;
    594         //computing blocking flow with dfs
     599        //computing blocking flow with dfs
    595600        typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
    596         DfsIterator5< ErasingResGW, BlockingReachedMap >
    597           dfs(erasing_res_graph);
     601        DfsIterator5< ErasingResGW, BlockingReachedMap >
     602          dfs(erasing_res_graph);
    598603        typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
    599604          pred(erasing_res_graph);
    600605        pred.set(s, INVALID);
    601         //invalid iterators for sources
    602 
    603         typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
     606        //invalid iterators for sources
     607
     608        typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
    604609
    605610        dfs.pushAndSetReached(s);
     
    609614                /*typename ErasingResGW::OutEdgeIt*/(dfs)))
    610615          {
    611             if (dfs.isBNodeNewlyReached()) {
     616            if (dfs.isBNodeNewlyReached()) {
    612617         
    613618              typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
     
    626631                break;
    627632              }
    628             } else {
    629               erasing_res_graph.erase(dfs);
     633            } else {
     634              erasing_res_graph.erase(dfs);
    630635            }
    631636          }
    632637        }       
    633638
    634         if (__augment) {
    635           typename ErasingResGW::Node n=t;
     639        if (__augment) {
     640          typename ErasingResGW::Node n=t;
    636641          Number augment_value=free[n];
    637642          while (erasing_res_graph.valid(pred[n])) {
     
    641646            if (res_graph.resCap(e)==0)
    642647              erasing_res_graph.erase(e);
    643           }
    644         }
     648        }
     649      }
    645650     
    646651      } //while (__augment)
Note: See TracChangeset for help on using the changeset viewer.