COIN-OR::LEMON - Graph Library

Changeset 657:531fc5f575ef in lemon-0.x


Ignore:
Timestamp:
05/24/04 12:43:44 (15 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@860
Message:

Not ready yet.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/mincostflow.h

    r645 r657  
    1111#include <hugo/maps.h>
    1212#include <vector>
     13#include <list>
    1314#include <for_each_macros.h>
     15#include <hugo/union_find.h>
    1416
    1517namespace hugo {
     
    119121
    120122      typedef typename Graph::template NodeMap<int> HeapMap;
    121       typedef Heap<Node, SupplyDemand, typename Graph::template NodeMap<int>,
     123      typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
    122124        std::greater<SupplyDemand> >    HeapType;
    123125
     
    130132      HeapType deficit_nodes(deficit_nodes_map);
    131133
     134      //A container to store nonabundant arcs
     135      list<Edge> nonabundant_arcs;
    132136     
    133137      FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
    134138        flow.set(e,0);
     139        nonabundant_arcs.push_back(e);
    135140      }
    136141
    137142      //Initial value for delta
    138143      SupplyDemand delta = 0;
     144
     145      typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
     146
     147      //A union-find structure to store the abundant components
     148      UFE::MapType abund_comp_map(G);
     149      UFE abundant_components(abund_comp_map);
     150
     151
    139152
    140153      FOR_EACH_LOC(typename Graph::NodeIt, n, G){
     
    154167        //Initialize the copy of the Dijkstra potential to zero
    155168        potential.set(n,0);
     169        //Every single point is an abundant component initially
     170        abundant_components.insert(n);
    156171      }
    157172
     
    172187      while (max_excess > 0){
    173188
     189        //Reset delta if still too big
     190        if (8*number_of_nodes*max_excess <= delta){
     191          delta = max_excess;
     192         
     193        }
     194
    174195        /*
    175196         * Beginning of the delta scaling phase
    176197        */
    177        
    178198        //Merge and stuff
     199        {
     200          SupplyDemand buf=8*number_of_nodes*delta;
     201          list<Edge>::iterator i = nonabundant_arcs.begin();
     202          while ( i != nonabundant_arcs.end() ){
     203            if (flow[i]>=buf){
     204              Node a = abundant_components.find(res_graph.head(i));
     205              Node b = abundant_components.find(res_graph.tail(i));
     206              //Merge
     207              if (a != b){
     208                //Find path and augment
     209                //!!!
     210                //Find path and augment
     211                abundant_components.join(a,b);
     212              }
     213              //What happens to i?
     214              nonabundant_arcs.erase(i);
     215            }
     216            else
     217              ++i;
     218          }
     219        }
     220
    179221
    180222        Node s = excess_nodes.top();
     
    262304        }
    263305        */
    264         //Reset delta if still too big
    265         if (8*number_of_nodes*max_excess <= delta){
    266           delta = max_excess;
    267          
    268         }
     306
    269307         
    270308      }//while(max_excess > 0)
Note: See TracChangeset for help on using the changeset viewer.