mcf_successive_sp.t

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

/*******************************************************************************
+
+  LEDA 4.5  
+
+
+  mcf_cap_scaling1.t
+
+
+  Copyright (c) 1995-2004
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.2 $  $Date: 2004/02/06 11:20:19 $

#include <LEDA/graph_alg.h>
#include <LEDA/node_pq22.h>
#include <LEDA/b_stack.h>
#include <LEDA/assert.h>


LEDA_BEGIN_NAMESPACE

template <class NT, class graph_t      = graph,
                    class pot_array    = node_array<NT,graph_t>,
                    class dist_array   = node_array<NT,graph_t>,
                    class pred_array   = node_array<edge,graph_t>,
                    class mark_array   = node_array<NT,graph_t>,
                    class node_pq_t    = node_pq22<NT,graph_t> >

class mcf_cap_scaling 
{
  typedef typename graph_t::node node;
  typedef typename graph_t::edge edge;
  typedef node_pq_t node_pq;
  
  float T;

node source(const graph_t& G, edge e, node t)
{ if (graph_t::category() == opposite_graph_category)
    return G.opposite(e,t);
  else
    return G.source(e);
}
  
node target(const graph_t& G, edge e, node s)
{ if (graph_t::category() == opposite_graph_category)
    return G.opposite(e,s);
  else
    return G.target(e);
}



inline void flip_sign(const NT& x) { (NT&)x = -x; }


template<class cost_array, class cap_array, class flow_array>

bool DIJKSTRA_IN_RESIDUAL(const graph_t& G, node s, node t,
                             const cost_array&   cost,
                             const cap_array&    cap,
                             const flow_array&   flow,
                             pot_array&  pi,
                             dist_array& dist,
                             pred_array& pred,
                             mark_array& mark,
                             node_pq&  PQ, int count)

{
  dist[s] = 0;
  dist[t] = MAXINT;

  PQ.insert(s,0);
  mark[s] = count;

  while (!PQ.empty())
  { 
    node u = PQ.del_min(dist);

    NT  du = dist[u];
    if (du == -count) continue;

    PQ.push(u);

    du += pi[u]; 
    pi[u] = du;

    if (u == t) break;

    dist[u] = -count;

    edge e;
    forall_out_edges(e,u) 
    { if (cap[e]-flow[e] > 0)  // e in residual graph
      { node v = target(G,e,u);
        if (dist[v] == -count) continue;

        NT c = du - pi[v] + cost[e];
    
        if (c >= dist[t]) continue;

        if ((mark[v] & 0x0fffffff) != count || c < dist[v])
        { PQ.insert(v,c); 
          dist[v] = c;
          pred[v] = e;
          mark[v] = count;
         }
       }
     }

    forall_in_edges(e,u) 
    { if (flow[e] > 0)  // e in residual graph
      { node v = source(G,e,u);
        if (dist[v] == -count) continue;

        NT c = du - pi[v] - cost[e];

        if (c >= dist[t]) continue;

        if ((mark[v] & 0x0fffffff) != count || c < dist[v])
        { PQ.insert(v,c); 
          dist[v] = c;
          pred[v] = e;
          mark[v] = (count | 0x10000000);
         }
       }
     }

   }

  NT dt = dist[t];

  /*
  node v = PQ.pop();
  while (v != 0) 
  { pi[v] -= dt;
    v = PQ.pop();
   }
   */
   if (dt < MAXINT)
      for(node* p = PQ.Top(); p != PQ.Stop(); p++) pi[*p] -= dt;

   PQ.clear(); 

  return dt < MAXINT;
}




public:


template <class cap_array,class cost_array,class flow_array>
bool run(const graph_t& G, node s, node t, NT supply,
                           const cap_array&  cap,
                           const cost_array& cost,
                           flow_array& flow)
{
  T = used_time();

  int n = G.number_of_nodes();
  int m = G.number_of_edges();

  node v;
  edge e;

  pot_array  pi;
  pi.use_node_data(G,0);

  dist_array dist;
  dist.use_node_data(G,MAXINT);

  pred_array pred;
  pred.use_node_data(G,0);

  mark_array mark;
  mark.use_node_data(G,0);


  node_pq PQ(n+m);

  int count = 0;

  forall_nodes(v, G) 
  { edge e;
    forall_out_edges(e,v) flow[e] = 0;
   }

  while (supply > 0)
  {
    if (!DIJKSTRA_IN_RESIDUAL(G,s,t,cost,cap,flow, pi,
                                    dist,pred,mark,PQ,++count)) break;

      NT f = supply;

      for(v = t; v != s; v = G.opposite(e,v))
      { e = pred[v];
        NT rc = (mark[v]&0x10000000) ? flow[e] : cap[e]-flow[e];
        if (rc < f) f = rc;
       }

      // add f units of flow along the augmenting path 

      for(v = t; v != s; v = G.opposite(e,v))
      { e = pred[v];
        if (mark[v]&0x10000000)
           flow[e] -= f;
        else
           flow[e] += f;
       }
  
       supply -= f;
   }

  
  T = used_time(T);

  return supply == 0;
}


float cpu_time() const { return T; }

};



LEDA_END_NAMESPACE