max_flow0.t

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

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

// $Revision: 1.4 $  $Date: 2004/02/06 11:20:08 $

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 450450
#include <LEDA/PREAMBLE.h>
#endif

//-----------------------------------------------------------------------------
//
// MAX_FLOW
//
// preflow-push + highest level + gap heuristic 
//
//-----------------------------------------------------------------------------


/*
#include <LEDA/graph.h>
*/
#include <LEDA/std/assert.h>

LEDA_BEGIN_NAMESPACE


template <class graph, class succ_array>
class node_level_queue {

typedef typename graph::node node;
typedef typename graph::edge edge;

node*  T;
node*  head;
node*  max;

succ_array& NEXT;

public:

node_level_queue(const graph& G, succ_array& succ) : NEXT(succ)
{ int sz = G.number_of_nodes();
  T = new node[sz+1];
  for(node* p = T+sz; p >= T;  p--) *p = nil; 
  head = T+1;
  max = T;
 }

~node_level_queue() { delete[] T; }

void set_max(int i) { max = head + i; }

void insert(node v, int i)
{ // insert on level i
  node* h = head + i;
  if (h > max) max = h;
  NEXT[v] = *h;
  *h = v;
 }


void insert_non_max(node v, int i)
{ // do not update max pointer
  node* h = head + i;
  NEXT[v] = *h;
  *h = v;
 }


void insert_max(node v, int i)
{ // new max at level i
  max = head + i;
  *max = v;
  NEXT[v] = 0;
 }

node del_max() 
{ while (*max == nil) max--;
  node v = *max;
  *max = NEXT[v];
  return v; 
}


void clear() { while (max >= T) *max-- =  nil; }

};



template<class NT, class graph,
#if !defined(_MSC_VER)
         class succ_array   = node_array<typename graph::node,graph>,
#else
         class succ_array   = node_array<graph::node,graph>,
#endif
         class excess_array = node_array<NT, graph>,
         class dist_array   = node_array<int,graph> >
class max_flow  
{
  const int node_slots;
  const int edge_slots;

  typedef typename graph::node node;
  typedef typename graph::edge edge;


  float h;

  NT fval;

  // statistics (phase 1, 2, and sum)

  int num_pushes[3];
  int num_relabels[3];
  int num_updates[3];
  int num_gap_nodes[3]; 
  int num_inspections[3];

  float cputime[3];
  float update_time;
  float gap_time;

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

public:

max_flow() : node_slots(3), edge_slots(0), h(5.0),fval(0)
{ reset_counters(); }

int pushes(int i=0)      { return num_pushes[i]; }
int relabels(int i=0)    { return num_relabels[i]; }
int updates(int i=0)     { return num_updates[i]; }
int gap_nodes(int i=0)   { return num_gap_nodes[i]; }
int inspections(int i=0) { return num_inspections[i]; }

float cpu_time(int i=0) { return cputime[i]; }

void set_heuristic(float hh) { h = hh; }


NT flow() { return fval; }


void reset_counters()
{ for(int i=0; i<3; i++) 
  { num_pushes[i] = 0;
    num_relabels[i] = 0;
    num_updates[i] = 0;
    num_gap_nodes[i] = 0;
    num_inspections[i] = 0;
    cputime[i] = 0;
    update_time = 0;
    gap_time = 0;
   }
}




void compute_dist0(const graph& G, node s, node t,
                   excess_array& excess,
                   succ_array& succ,
                   dist_array& dist,
                   node_level_queue<graph,succ_array>& U, int* count)
{ 
  // compute exact distance values by a "backward" bfs in the
  // residual network starting at t

  float T = used_time();

  num_updates[1]++;

  int n = G.number_of_nodes();

  for(int i=0; i<n; i++) count[i] = 0;

  if (h < 0)
  { U.insert(t,0);
    node v;
    forall_nodes(v,G)
    { dist[v] = 0;
      if (v != t && excess[v] > 0) U.insert(v,0);
     }
    count[0] = n-1;
    dist[s] = n;
    return;
   }


  dist.init(G,n);

  excess[t] += 1;

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

  node v = t;
  node level_last = t;
  node queue_last = t;


  int d = 0;
  int level_sz = 0;

  for(;;)
  { 
    level_sz++;

    edge e;
    forall_in_edges(e,v)
    { node u = source(G,e,v); 
      int& du = dist[u];
      if (du == n)
      { du = d+1;
        succ[queue_last] = u;
        queue_last = u;
       }
    }

    node next = succ[v];

    if (excess[v] > 0) U.insert(v,d);

    if (v == level_last)             
    { // finish level d
      count[d++] = level_sz;
      level_sz = 0;
      if (queue_last == level_last) break; // no level d+1: stop
      level_last = queue_last;
     }
    v = next;
  }

 dist[s] = n;
 excess[t] -= 1;

 update_time += used_time(T);
}




template<class cap_array, class flow_array, class n_level_queue>
void compute_dist1(const graph& G, node s, node t,
                   const cap_array& cap,
                   const flow_array& flow,
                   excess_array& excess,
                   succ_array& succ,
                   dist_array& dist,
                   n_level_queue& U,
                   int* count)
{ 
  // compute exact distance values by a "backward" bfs in the
  // residual network starting at t

  float T = used_time();

  num_updates[1]++;

  int n = G.number_of_nodes();
  dist.init(G,n);

  dist[t] = 0;
  excess[t] += 1; // we want t to be in U (the only node on level 0)

  node v = t;
  node level_last = t;
  node queue_last = t;


  int d = 0;
  int level_sz = 0;

  for(;;)
  { 
    level_sz++;

    edge e;
    forall_out_edges(e,v)
    { if (flow[e] == 0) continue;
      node u = target(G,e,v); 
      int& du = dist[u];
      if (du == n)
      { du = d+1;
        succ[queue_last] = u;
        queue_last = u;
       }
     }

    forall_in_edges(e,v)
    { if (cap[e] == flow[e]) continue;
      node u = source(G,e,v); 
      int& du = dist[u];
      if (du == n)
      { du = d+1;
        succ[queue_last] = u;
        queue_last = u;
       }
    }

    node next = succ[v];

    if (excess[v] > 0) U.insert(v,d);

    if (v == level_last)             
    { // finish level d
      count[d++] = level_sz;
      level_sz = 0;
      if (queue_last == level_last) break; // no level d+1: stop
      level_last = queue_last;
     }
    v = next;
  }

 while (d < n) count[d++] = 0;

 assert(dist[s] == n);

 excess[t] -= 1;

 update_time += used_time(T);
}



template<class flow_array, class n_level_queue>
void compute_dist2(const graph& G, node s, node t,
                   const flow_array& flow,
                   const excess_array& excess,
                   succ_array& succ,
                   dist_array& dist,
                   n_level_queue& U)
{ 
  float T = used_time();

  num_updates[2]++;

  int n = G.number_of_nodes();

  dist.init(G,n);

  node v = s;
  node level_last = s;
  node queue_last = s;
  dist[s] = 0;

  U.insert(t,0);

  int d = 0;

  for(;;)
  { 
    edge e;
    forall_out_edges(e,v)
    { if (flow[e] == 0) continue;
      node u = target(G,e,v); 
      int& du = dist[u];
      if (du == n)
      { du = d+1;
        succ[queue_last] = u;
        queue_last = u;
       }
     }

    node next = succ[v];

    if (excess[v] > 0 && v != t) U.insert(v,d);

    if (v == level_last)             
    { if (queue_last == level_last) break;
      level_last = queue_last;
      d++;
     }
    v = next;
  }

 update_time +=  used_time(T);
}




void handle_gap(const graph& G, node v, dist_array& dist, succ_array& succ, int* count)
{

  float T = used_time();

  int gap_nodes = 0;

  int n  = G.number_of_nodes();
  int dv = dist[v];
  for (int i = dv; i < n && count[i] > 0; i++) count[i] = 0;

  dist[v] = n;

  node queue_last = v;
  succ[v] = v;

  do { gap_nodes++;

       v = succ[v];

       edge e;
       forall_out_edges(e,v)
       { node u = target(G,e,v);
         int& du = dist[u];
         if (du < n && du > dv)
         { succ[queue_last] = u;
           queue_last = u; 
           du = n;
          }
       }

       forall_in_edges(e,v)
       { node u = source(G,e,v);
         int& du = dist[u];
         if (du < n && du > dv)
         { succ[queue_last] = u;
           queue_last = u;
           du = n;
          }
        }

   } while (v != queue_last);

 num_gap_nodes[1] += gap_nodes;

 gap_time += used_time(T);
}



template<class cap_array, class flow_array>