COIN-OR::LEMON - Graph Library

Changeset 331:f5461f8bc59b in lemon-0.x


Ignore:
Timestamp:
04/15/04 19:03:44 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@449
Message:

Elkezdtem atirni a preflow_push-t. Csinaltam egy backupot graph wrapper nelkul (without gw, azaz wogw)

Location:
src/work/athos
Files:
1 added
1 deleted
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/makefile

    r322 r331  
    77INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
    88#LEDAINCLUDE ?= -I$(LEDAROOT)/incl
    9 CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     9CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
    1010
    1111#LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
  • src/work/athos/pf_demo.cc

    r201 r331  
    33#include <string>
    44
    5 #include "list_graph.hh"
    6 #include "marci_graph_traits.hh"
     5#include "list_graph.h"
     6//#include "marci_graph_traits.hh"
    77//#include "marci_property_vector.hh"
    88#include "preflow_push.hh"
     
    1414{
    1515
    16  
    17   typedef ListGraph::NodeIt NodeIt;
    18   typedef ListGraph::EdgeIt EdgeIt;
    19   /*
    20   typedef ListGraph::EachNodeIt EachNodeIt;
    21   typedef ListGraph::EachEdgeIt EachEdgeIt;
    22   typedef ListGraph::OutEdgeIt OutEdgeIt;
    23   typedef ListGraph::InEdgeIt InEdgeIt;
    24   typedef ListGraph::SymEdgeIt SymEdgeIt;
    25   */
    26   ListGraph flowG;
     16  typedef ListGraph::Node Node;
     17  typedef ListGraph::Edge Edge;
     18
     19  ListGraph graph;
    2720
    2821  /*
     
    3023
    3124
    32   NodeIt s=flowG.addNode();
    33   NodeIt v1=flowG.addNode();
    34   NodeIt v2=flowG.addNode();
    35   NodeIt v3=flowG.addNode();
    36   NodeIt v4=flowG.addNode();
    37   NodeIt t=flowG.addNode();
     25  NodeIt s=graph.addNode();
     26  NodeIt v1=graph.addNode();
     27  NodeIt v2=graph.addNode();
     28  NodeIt v3=graph.addNode();
     29  NodeIt v4=graph.addNode();
     30  NodeIt t=graph.addNode();
    3831 
    3932
    40   EdgeIt s_v1=flowG.addEdge(s, v1);
    41   EdgeIt s_v2=flowG.addEdge(s, v2);
    42   EdgeIt v1_v2=flowG.addEdge(v1, v2);
    43   EdgeIt v2_v1=flowG.addEdge(v2, v1);
    44   EdgeIt v1_v3=flowG.addEdge(v1, v3);
    45   EdgeIt v3_v2=flowG.addEdge(v3, v2);
    46   EdgeIt v2_v4=flowG.addEdge(v2, v4);
    47   EdgeIt v4_v3=flowG.addEdge(v4, v3);
    48   EdgeIt v3_t=flowG.addEdge(v3, t);
    49   EdgeIt v4_t=flowG.addEdge(v4, t);
     33  EdgeIt s_v1=graph.addEdge(s, v1);
     34  EdgeIt s_v2=graph.addEdge(s, v2);
     35  EdgeIt v1_v2=graph.addEdge(v1, v2);
     36  EdgeIt v2_v1=graph.addEdge(v2, v1);
     37  EdgeIt v1_v3=graph.addEdge(v1, v3);
     38  EdgeIt v3_v2=graph.addEdge(v3, v2);
     39  EdgeIt v2_v4=graph.addEdge(v2, v4);
     40  EdgeIt v4_v3=graph.addEdge(v4, v3);
     41  EdgeIt v3_t=graph.addEdge(v3, t);
     42  EdgeIt v4_t=graph.addEdge(v4, t);
    5043
    51   ListGraph::EdgeMap<int> cap(flowG);
     44  ListGraph::EdgeMap<int> length(graph);
    5245
    53   cap.set(s_v1, 16);
    54   cap.set(s_v2, 13);
    55   cap.set(v1_v2, 10);
    56   cap.set(v2_v1, 4);
    57   cap.set(v1_v3, 12);
    58   cap.set(v3_v2, 9);
    59   cap.set(v2_v4, 14);
    60   cap.set(v4_v3, 7);
    61   cap.set(v3_t, 20);
    62   cap.set(v4_t, 4);
     46  length.set(s_v1, 16);
     47  length.set(s_v2, 13);
     48  length.set(v1_v2, 10);
     49  length.set(v2_v1, 4);
     50  length.set(v1_v3, 12);
     51  length.set(v3_v2, 9);
     52  length.set(v2_v4, 14);
     53  length.set(v4_v3, 7);
     54  length.set(v3_t, 20);
     55  length.set(v4_t, 4);
    6356  */
    6457
     
    6659  //Ahuja könyv példája
    6760
    68   NodeIt s=flowG.addNode();
    69   NodeIt v2=flowG.addNode();
    70   NodeIt v3=flowG.addNode();
    71   NodeIt v4=flowG.addNode();
    72   NodeIt v5=flowG.addNode();
    73   NodeIt t=flowG.addNode();
     61  Node s=graph.addNode();
     62  Node v2=graph.addNode();
     63  Node v3=graph.addNode();
     64  Node v4=graph.addNode();
     65  Node v5=graph.addNode();
     66  Node t=graph.addNode();
    7467
    75   EdgeIt s_v2=flowG.addEdge(s, v2);
    76   EdgeIt s_v3=flowG.addEdge(s, v3);
    77   EdgeIt v2_v4=flowG.addEdge(v2, v4);
    78   EdgeIt v2_v5=flowG.addEdge(v2, v5);
    79   EdgeIt v3_v5=flowG.addEdge(v3, v5);
    80   EdgeIt v4_t=flowG.addEdge(v4, t);
    81   EdgeIt v5_t=flowG.addEdge(v5, t);
     68  Edge s_v2=graph.addEdge(s, v2);
     69  Edge s_v3=graph.addEdge(s, v3);
     70  Edge v2_v4=graph.addEdge(v2, v4);
     71  Edge v2_v5=graph.addEdge(v2, v5);
     72  Edge v3_v5=graph.addEdge(v3, v5);
     73  Edge v4_t=graph.addEdge(v4, t);
     74  Edge v5_t=graph.addEdge(v5, t);
    8275 
    8376  //Kis modositas
    84   //edge_iterator v2_s=flowG.add_edge(v2, s);
     77  //edge_iterator v2_s=graph.add_edge(v2, s);
    8578
    86   ListGraph::EdgeMap<int> cap(flowG);
     79  ListGraph::EdgeMap<int> length(graph);
    8780
    88   cap.set(s_v2, 10);
    89   cap.set(s_v3, 10);
    90   cap.set(v2_v4, 5);
    91   cap.set(v2_v5, 8);
    92   cap.set(v3_v5, 5);
    93   cap.set(v4_t, 8);
    94   cap.set(v5_t, 8);
     81  length.set(s_v2, 10);
     82  length.set(s_v3, 10);
     83  length.set(v2_v4, 5);
     84  length.set(v2_v5, 8);
     85  length.set(v3_v5, 5);
     86  length.set(v4_t, 8);
     87  length.set(v5_t, 8);
    9588
    9689  //Kis modositas
    97   //cap.put(v2_s, 100);
    98  
     90  //length.put(v2_s, 100);
    9991
    10092
    10193
    102   /*Egyszerû példa
    103   NodeIt s=flow_test.add_node();
    104   NodeIt v1=flow_test.add_node();
    105   NodeIt v2=flow_test.add_node();
    106   NodeIt t=flow_test.add_node();
    107  
    108   node_property_vector<list_graph, std::string> node_name(flow_test);
    109   node_name.put(s, "s");
    110   node_name.put(v1, "v1");
    111   node_name.put(v2, "v2");
    112   node_name.put(t, "t");
    113 
    114   edge_iterator s_v1=flow_test.add_edge(s, v1);
    115   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
    116   edge_iterator v2_t=flow_test.add_edge(v2, t);
    117 
    118   edge_property_vector<list_graph, int> cap(flow_test);
    119    
    120   cap.put(s_v1, 16);
    121   cap.put(v1_v2, 10);
    122   cap.put(v2_t, 4);
    123   */
    124 
    12594  std::cout << "preflow-push algorithm test..." << std::endl;
    12695
    127   /*
    128   std::cout << "on directed graph graph" << std::endl; //<< flow_test;
    129   std::cout << "names and capacity values" << std::endl;
    130   for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
    131     std::cout << node_name.get(i) << ": ";
    132     std::cout << "out edges: ";
    133     for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
    134       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
    135     std::cout << "in edges: ";
    136     for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
    137       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
    138     std::cout << std::endl;
    139   }
    140   */
    14196 
    142   //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
    143   //  std::cout << i << " ";
    144   //}
    145  
    146   preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
     97  preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length);
    14798  cout << preflow_push_test.run()<<endl;
    14899
     
    152103  return 0;
    153104}
    154 
    155 
    156 
    157 
    158 
    159 
    160 
    161 
    162 
  • src/work/athos/preflow_push.hh

    r119 r331  
    1 #ifndef PREFLOW_PUSH_HH
    2 #define PREFLOW_PUSH_HH
    3 
    4 #include <algorithm>
     1#ifndef HUGO_PREFLOW_PUSH_HH
     2#define HUGO_PREFLOW_PUSH_HH
     3
     4//#include <algorithm>
    55#include <list>
    66#include <vector>
     7#include <queue>
    78//#include "pf_hiba.hh"
    89//#include <marci_list_graph.hh>
    910//#include <marci_graph_traits.hh>
    10 
    11 #include <reverse_bfs.hh>
     11#include <invalid.h>
     12#include <graph_wrapper.h>
     13//#include <reverse_bfs.hh>
    1214
    1315using namespace std;
     
    1517namespace hugo {
    1618
    17   template <typename graph_type, typename T>
     19  template <typename Graph, typename T>
    1820  class preflow_push {
    1921
    20     //Hasznos typedef-ek
    21     typedef typename graph_type::NodeIt NodeIt;
    22     typedef typename graph_type::EdgeIt EdgeIt;
    23     typedef typename graph_type::EachNodeIt EachNodeIt;
    24     typedef typename graph_type::EachEdgeIt EachEdgeIt;
    25     typedef typename graph_type::OutEdgeIt OutEdgeIt;
    26     typedef typename graph_type::InEdgeIt InEdgeIt;
    27     typedef typename graph_type::SymEdgeIt SymEdgeIt;
    28 
    29 
    30 
    31     /*
    32     typedef graph_traits<graph_type>::node_iterator node_iterator;
    33     typedef graph_traits<graph_type>::EdgeIt EdgeIt;
    34     typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
    35     typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
    36     typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
    37     typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
    38     typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
    39     */
     22    //Useful typedefs
     23    typedef typename Graph::Node Node;
     24    typedef typename Graph::NodeIt NodeIt;
     25    typedef typename Graph::Edge Edge;
     26    typedef typename Graph::OutEdgeIt OutEdgeIt;
     27    typedef typename Graph::InEdgeIt InEdgeIt;
     28
    4029
    4130    //---------------------------------------------
     
    5645  private:
    5746    //input
    58     graph_type& G;
    59     NodeIt s;
    60     NodeIt t;
    61     typename graph_type::EdgeMap<T> &capacity;
    62     //typename graph_type::EdgeMap<T>  &capacity;
     47    Graph& G;
     48    Node s;
     49    Node t;
     50    typename Graph::EdgeMap<T> &capacity;
     51
    6352    //output
    64     //typename graph_type::EdgeMap<T> 
    65     typename graph_type::EdgeMap<T> preflow;
     53    typename Graph::EdgeMap<T> preflow;
    6654    T maxflow_value;
    6755 
    6856    //auxiliary variables for computation
     57    //The number of the nodes
    6958    int number_of_nodes;
    70    
    71    
    72     typename graph_type::NodeMap<int> level;
    73     typename graph_type::NodeMap<T> excess;
    74     //node_property_vector<graph_type, int> level;
    75     //node_property_vector<graph_type, T> excess;
     59    //A nodemap for the level
     60    typename Graph::NodeMap<int> level;
     61    //A nodemap for the excess
     62    typename Graph::NodeMap<T> excess;
    7663   
    7764    //Number of nodes on each level
     
    7966   
    8067    //For the FIFO implementation
    81     list<NodeIt> fifo_nodes;
     68    list<Node> fifo_nodes;
    8269    //For 'highest label' implementation
    8370    int highest_active;
    8471    //int second_highest_active;
    85     vector< list<NodeIt> > active_nodes;
     72    vector< list<Node> > active_nodes;
    8673
    8774  public:
     
    8976    //Constructing the object using the graph, source, sink and capacity vector
    9077    preflow_push(
    91                       graph_type& _G,
    92                       NodeIt _s,
    93                       NodeIt _t,
    94                       typename graph_type::EdgeMap<T> & _capacity)
     78                      Graph& _G,
     79                      Node _s,
     80                      Node _t,
     81                      typename Graph::EdgeMap<T> & _capacity)
    9582      : G(_G), s(_s), t(_t),
    9683        capacity(_capacity),
     
    115102      switch(implementation){
    116103      case impl_highest_label :{
     104        active_nodes.clear();
    117105        active_nodes.resize(2*number_of_nodes-1);
    118         active_nodes.clear();
     106       
    119107        break;
    120108      }
     
    128116    T run();
    129117 
    130     typename graph_type::EdgeMap<T>  getmaxflow(){
     118    typename Graph::EdgeMap<T>  getmaxflow(){
    131119      return preflow;
    132120    }
     
    136124    //For testing purposes only
    137125    //Lists the node_properties
    138     void write_property_vector(typename graph_type::NodeMap<T> a,
    139                                //node_property_vector<graph_type, T> a,
     126    void write_property_vector(typename Graph::NodeMap<T> a,
     127                               //node_property_vector<Graph, T> a,
    140128                               char* prop_name="property"){
    141       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
    142         cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
     129      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
     130        cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl;
    143131      }
    144132      cout<<endl;
     
    146134
    147135    //Modifies the excess of the node and makes sufficient changes
    148     void modify_excess(const NodeIt& a ,T v){
    149         T old_value=excess.get(a);
    150         excess.set(a,old_value+v);
     136    void modify_excess(const Node& a ,T v){
     137      //T old_value=excess[a];
     138      excess[a] += v;
    151139    }
    152140 
     
    155143    //and maintain the excess on the head and tail
    156144    //Here we do not check whether this is possible or not
    157     void modify_preflow(EdgeIt j, const T& v){
    158 
    159       //Auxiliary variable
    160       T old_value;
    161        
     145    void modify_preflow(Edge j, const T& v){
     146
    162147      //Modifiyng the edge
    163       old_value=preflow.get(j);
    164       preflow.set(j,old_value+v);
     148      preflow[j] += v;
    165149
    166150
     
    175159    //Gives the active node to work with
    176160    //(depending on the implementation to be used)
    177     NodeIt get_active_node(){
     161    Node get_active_node(){
    178162     
    179163
     
    181165      case impl_highest_label : {
    182166
    183         //First need to find the highest label for which there"s an active node
     167        //First need to find the highest label for which there's an active node
    184168        while( highest_active>=0 && active_nodes[highest_active].empty() ){
    185169          --highest_active;
     
    189173         
    190174
    191           NodeIt a=active_nodes[highest_active].front();
     175          Node a=active_nodes[highest_active].front();
    192176          active_nodes[highest_active].pop_front();
    193177         
     
    195179        }
    196180        else {
    197           return NodeIt();
     181          return INVALID;
    198182        }
    199183       
     
    204188
    205189        if( ! fifo_nodes.empty() ) {
    206           NodeIt a=fifo_nodes.front();
     190          Node a=fifo_nodes.front();
    207191          fifo_nodes.pop_front();
    208192          return a;
    209193        }
    210194        else {
    211           return NodeIt();
     195          return INVALID;
    212196        }
    213197        break;
     
    215199      }
    216200      //
    217       return NodeIt();
     201      return INVALID;
    218202    }
    219203
    220204    //Puts node 'a' among the active nodes
    221     void make_active(const NodeIt& a){
     205    void make_active(const Node& a){
    222206      //s and t never become active
    223207      if (a!=s && a!= t){
    224208        switch(implementation){
    225209        case impl_highest_label :
    226           active_nodes[level.get(a)].push_back(a);
     210          active_nodes[level[a]].push_back(a);
    227211          break;
    228212        case impl_fifo :
     
    234218
    235219      //Update highest_active label
    236       if (highest_active<level.get(a)){
    237         highest_active=level.get(a);
     220      if (highest_active<level[a]){
     221        highest_active=level[a];
    238222      }
    239223
     
    241225
    242226    //Changes the level of node a and make sufficent changes
    243     void change_level_to(NodeIt a, int new_value){
    244       int seged = level.get(a);
     227    void change_level_to(Node a, int new_value){
     228      int seged = level[a];
    245229      level.set(a,new_value);
    246230      --num_of_nodes_on_level[seged];
     
    258242      //Setting starting preflow, level and excess values to zero
    259243      //This can be important, if the algorithm is run more then once
    260       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
     244      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
    261245        level.set(i,0);
    262246        excess.set(i,0);
    263         for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)
     247        for(OutEdgeIt j=G.template first<OutEdgeIt>(i); G.valid(j); G.next(j))
    264248          preflow.set(j, 0);
    265249      }
     
    274258      //This is the only part that uses BFS
    275259      //------------------------------------
     260
     261      /*Reverse_bfs from t, to find the starting level.*/
     262      //Copyright: Jacint
     263      change_level_to(t,0);
     264
     265      std::queue<Node> bfs_queue;
     266      bfs_queue.push(t);
     267
     268      while (!bfs_queue.empty()) {
     269
     270        Node v=bfs_queue.front();       
     271        bfs_queue.pop();
     272        int l=level[v]+1;
     273
     274        InEdgeIt e;
     275        for(G.first(e,v); G.valid(e); G.next(e)) {
     276          Node w=G.tail(e);
     277          if ( level[w] == number_of_nodes && w != s ) {
     278            bfs_queue.push(w);
     279            //Node first=level_list[l];
     280            //if ( G.valid(first) ) left.set(first,w);
     281            //right.set(w,first);
     282            //level_list[l]=w;
     283            change_level_to(w, l);
     284            //level.set(w, l);
     285          }
     286        }
     287      }
     288      change_level_to(s,number_of_nodes);
     289      //level.set(s,number_of_nodes);
     290
     291      /*
    276292      //Setting starting level values using reverse bfs
    277       reverse_bfs<graph_type> rev_bfs(G,t);
     293      reverse_bfs<Graph> rev_bfs(G,t);
    278294      rev_bfs.run();
    279295      //write_property_vector(rev_bfs.dist,"rev_bfs");
    280       for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
     296      for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) {
    281297        change_level_to(i,rev_bfs.dist(i));
    282298        //level.put(i,rev_bfs.dist.get(i));
    283299      }
     300      */
    284301      //------------------------------------
    285302      //This is the only part that uses BFS
     
    293310     
    294311      //we push as much preflow from s as possible to start with
    295       for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
    296         modify_preflow(j,capacity.get(j) );
     312      for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){
     313        modify_preflow(j,capacity[j] );
    297314        make_active(G.head(j));
    298         int lev=level.get(G.head(j));
     315        int lev=level[G.head(j)];
    299316        if(highest_active<lev){
    300317          highest_active=lev;
     
    307324    //If the preflow is less than the capacity on the given edge
    308325    //then it is an edge in the residual graph
    309     bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
    310 
    311       if (capacity.get(j)>preflow.get(j)){
    312         if(level.get(G.tail(j))==level.get(G.head(j))+1){
     326    bool is_admissible_forward_edge(Edge j, int& new_level){
     327
     328      if (capacity[j]>preflow[j]){
     329        if(level[G.tail(j)]==level[G.head(j)]+1){
    313330          return true;
    314331        }
    315332        else{
    316           if (level.get(G.head(j)) < new_level)
    317             new_level=level.get(G.head(j));
     333          if (level[G.head(j)] < new_level)
     334            new_level=level[G.head(j)];
    318335        }
    319336      }
     
    323340    //If the preflow is greater than 0 on the given edge
    324341    //then the edge reversd is an edge in the residual graph
    325     bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
    326      
    327       if (0<preflow.get(j)){
    328         if(level.get(G.tail(j))==level.get(G.head(j))-1){
     342    bool is_admissible_backward_edge(Edge j, int& new_level){
     343     
     344      if (0<preflow[j]){
     345        if(level[G.tail(j)]==level[G.head(j)]-1){
    329346         
    330347          return true;
    331348        }
    332349        else{
    333           if (level.get(G.tail(j)) < new_level)
    334             new_level=level.get(G.tail(j));
     350          if (level[G.tail(j)] < new_level)
     351            new_level=level[G.tail(j)];
    335352        }
    336353       
     
    342359  };  //class preflow_push 
    343360
    344   template<typename graph_type, typename T>
    345     T preflow_push<graph_type, T>::run() {
     361  template<typename Graph, typename T>
     362    T preflow_push<Graph, T>::run() {
     363   
     364    //We need a residual graph
     365    ResGraphType res_graph(G, preflow, capacity);
    346366   
    347367    preprocess();
    348368    //write_property_vector(level,"level");
    349369    T e,v;
    350     NodeIt a;
    351     while (a=get_active_node(), a.valid()){
    352      
    353       //cout<<G.id(a)<<endl;
    354       //write_property_vector(excess,"excess");
    355       //write_property_vector(level,"level");
    356 
    357 
     370    Node a;
     371    while (a=get_active_node(), G.valid(a)){
     372     
    358373      bool go_to_next_node=false;
    359       e = excess.get(a);
     374      e = excess[a];
    360375      while (!go_to_next_node){
     376
    361377        //Initial value for the new level for the active node we are dealing with
    362378        int new_level=2*number_of_nodes;
    363         //write_property_vector(excess,"excess");
    364         //write_property_vector(level,"level");
    365         //cout<<G.id(a)<<endl;
     379
     380
    366381        //Out edges from node a
    367382        {
    368383          OutEdgeIt j=G.template first<OutEdgeIt>(a);
    369           while (j.valid() && e){
     384          while (G.valid(j) && e){
    370385
    371386            if (is_admissible_forward_edge(j,new_level)){
    372               v=min(e,capacity.get(j) - preflow.get(j));
     387              v=min(e,capacity[j] - preflow[j]);
    373388              e -= v;
    374389              //New node might become active
    375               if (excess.get(G.head(j))==0){
     390              if (excess[G.head(j)]==0){
    376391                make_active(G.head(j));
    377392              }
    378393              modify_preflow(j,v);
    379394            }
    380             ++j;
     395            G.next(j);
    381396          }
    382397        }
     
    384399        {
    385400          InEdgeIt j=G.template first<InEdgeIt>(a);
    386           while (j.valid() && e){
     401          while (G.valid(j) && e){
    387402            if (is_admissible_backward_edge(j,new_level)){
    388               v=min(e,preflow.get(j));
     403              v=min(e,preflow[j]);
    389404              e -= v;
    390405              //New node might become active
    391               if (excess.get(G.tail(j))==0){
     406              if (excess[G.tail(j)]==0){
    392407                make_active(G.tail(j));
    393408              }
    394409              modify_preflow(j,-v);
    395410            }
    396             ++j;
     411            G.next(j);
    397412          }
    398413        }
     
    411426         
    412427          //Level remains empty
    413           if (num_of_nodes_on_level[level.get(a)]==1){
     428          if (num_of_nodes_on_level[level[a]]==1){
    414429            change_level_to(a,number_of_nodes);
    415430            //go_to_next_node=True;
     
    438453      }
    439454    }
    440     maxflow_value = excess.get(t);
     455    maxflow_value = excess[t];
    441456    return maxflow_value;
    442457  }//run
Note: See TracChangeset for help on using the changeset viewer.