COIN-OR::LEMON - Graph Library

Changeset 635:933f593824c2 in lemon-0.x for src/work/athos/mincostflow.h


Ignore:
Timestamp:
05/13/04 19:42:23 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@826
Message:

Started mincostflow.

File:
1 edited

Legend:

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

    r633 r635  
    3737  ///
    3838  ///\author Attila Bernath
    39   template <typename Graph, typename LengthMap, typename SupplyMap>
     39  template <typename Graph, typename LengthMap, typename SupplyDemandMap>
    4040  class MinCostFlow {
    4141
     
    4343
    4444
    45     typedef typename SupplyMap::ValueType Supply;
     45    typedef typename SupplyDemandMap::ValueType SupplyDemand;
    4646   
    4747    typedef typename Graph::Node Node;
     
    8585    const Graph& G;
    8686    const LengthMap& length;
    87     const SupplyMap& supply;//supply or demand of nodes
     87    const SupplyDemandMap& supply_demand;//supply or demand of nodes
    8888
    8989
     
    9595    typename Graph::template NodeMap<Length> potential;
    9696    //To store excess-deficit values
    97     SupplyMap excess;
     97    SupplyDemandMap excess_deficit;
    9898   
    9999
     
    104104
    105105
    106     MinCostFlow(Graph& _G, LengthMap& _length, SupplyMap& _supply) : G(_G),
    107       length(_length), supply(_supply), flow(_G), potential(_G){ }
     106    MinCostFlow(Graph& _G, LengthMap& _length, SupplyDemandMap& _supply_demand) : G(_G),
     107      length(_length), supply_demand(_supply_demand), flow(_G), potential(_G){ }
    108108
    109109   
     
    111111
    112112    ///Runs the algorithm.
    113     ///Returns k if there are at least k edge-disjoint paths from s to t.
    114     ///Otherwise it returns the number of found edge-disjoint paths from s to t.
     113
    115114    ///\todo May be it does make sense to be able to start with a nonzero
    116115    /// feasible primal-dual solution pair as well.
     
    118117
    119118      //Resetting variables from previous runs
    120       total_length = 0;
     119      //total_length = 0;
     120
     121      typedef typename Graph::template NodeMap<int> HeapMap;
     122      typedef Heap<Node, SupplyDemand, typename Graph::template NodeMap<int>,
     123        std::greater<SupplyDemand> >    HeapType;
     124
     125      //A heap for the excess nodes
     126      HeapMap excess_nodes_map(G,-1);
     127      HeapType excess_nodes(excess_nodes_map);
     128
     129      //A heap for the deficit nodes
     130      HeapMap deficit_nodes_map(G,-1);
     131      HeapType deficit_nodes(deficit_nodes_map);
     132
    121133     
    122134      FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
     
    125137
    126138      //Initial value for delta
    127       Supply delta = 0;
    128      
     139      SupplyDemand delta = 0;
     140
    129141      FOR_EACH_LOC(typename Graph::NodeIt, n, G){
    130         if (delta < abs(supply[e])){
    131           delta = abs(supply[e]);
    132         }
    133         excess.set(n,supply[e]);
     142        excess_deficit.set(n,supply_demand[n]);
     143        //A supply node
     144        if (excess_deficit[n] > 0){
     145          excess_nodes.push(n,excess_deficit[n]);
     146        }
     147        //A demand node
     148        if (excess_deficit[n] < 0){
     149          deficit_nodes.push(n, - excess_deficit[n]);
     150        }
     151        //Finding out starting value of delta
     152        if (delta < abs(excess_deficit[n])){
     153          delta = abs(excess_deficit[n]);
     154        }
    134155        //Initialize the copy of the Dijkstra potential to zero
    135156        potential.set(n,0);
    136157      }
    137      
    138 
     158
     159      //It'll be allright as an initial value, though this value
     160      //can be the maximum deficit here
     161      SupplyDemand max_excess = delta;
    139162     
    140163      //We need a residual graph which is uncapacitated
     
    148171
    149172
    150       int i;
    151       for (i=0; i<k; ++i){
    152         dijkstra.run(s);
    153         if (!dijkstra.reached(t)){
    154           //There are no k paths from s to t
    155           break;
    156         };
     173      while (max_excess > 0){
     174
    157175       
    158         //We have to copy the potential
    159         FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){
    160           potential[n] += dijkstra.distMap()[n];
     176        //Merge and stuff
     177
     178        Node s = excess_nodes.top();
     179        SupplyDemand max_excess = excess_nodes[s];
     180        Node t = deficit_nodes.top();
     181        if (max_excess < dificit_nodes[t]){
     182          max_excess = dificit_nodes[t];
     183        }
     184
     185
     186        while(max_excess > ){
     187
     188         
     189          //s es t valasztasa
     190
     191          //Dijkstra part       
     192          dijkstra.run(s);
     193
     194          /*We know from theory that t can be reached
     195          if (!dijkstra.reached(t)){
     196            //There are no k paths from s to t
     197            break;
     198          };
     199          */
     200         
     201          //We have to change the potential
     202          FOR_EACH_LOC(typename ResGraphType::NodeIt, n, res_graph){
     203            potential[n] += dijkstra.distMap()[n];
     204          }
     205
     206
     207          //Augmenting on the sortest path
     208          Node n=t;
     209          ResGraphEdge e;
     210          while (n!=s){
     211            e = dijkstra.pred(n);
     212            n = dijkstra.predNode(n);
     213            res_graph.augment(e,delta);
     214            /*
     215            //Let's update the total length
     216            if (res_graph.forward(e))
     217              total_length += length[e];
     218            else
     219              total_length -= length[e];           
     220            */
     221          }
     222
     223          //Update the excess_nodes heap
     224          if (delta >= excess_nodes[s]){
     225            if (delta > excess_nodes[s])
     226              deficit_nodes.push(s,delta - excess_nodes[s]);
     227            excess_nodes.pop();
     228           
     229          }
     230          else{
     231            excess_nodes[s] -= delta;
     232          }
     233          //Update the deficit_nodes heap
     234          if (delta >= deficit_nodes[t]){
     235            if (delta > deficit_nodes[t])
     236              excess_nodes.push(t,delta - deficit_nodes[t]);
     237            deficit_nodes.pop();
     238           
     239          }
     240          else{
     241            deficit_nodes[t] -= delta;
     242          }
     243          //Dijkstra part ends here
    161244        }
    162245
    163246        /*
    164         {
    165 
    166           typename ResGraphType::NodeIt n;
    167           for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
    168               potential[n] += dijkstra.distMap()[n];
    169           }
    170         }
     247         * End of the delta scaling phase
    171248        */
    172249
    173         //Augmenting on the sortest path
    174         Node n=t;
    175         ResGraphEdge e;
    176         while (n!=s){
    177           e = dijkstra.pred(n);
    178           n = dijkstra.predNode(n);
    179           res_graph.augment(e,delta);
    180           //Let's update the total length
    181           if (res_graph.forward(e))
    182             total_length += length[e];
    183           else
    184             total_length -= length[e];     
    185         }
    186 
     250        //Whatever this means
     251        delta = delta / 2;
     252
     253        /*This is not necessary here
     254        //Update the max_excess
     255        max_excess = 0;
     256        FOR_EACH_LOC(typename Graph::NodeIt, n, G){
     257          if (max_excess < excess_deficit[n]){
     258            max_excess = excess_deficit[n];
     259          }
     260        }
     261        */
     262        //Reset delta if still too big
     263        if (8*number_of_nodes*max_excess <= delta){
     264          delta = max_excess;
    187265         
    188       }
     266        }
     267         
     268      }//while(max_excess > 0)
    189269     
    190270
Note: See TracChangeset for help on using the changeset viewer.