max_flow_book.t

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

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

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


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

#include <LEDA/max_flow.h>
#include <LEDA/queue.h>
#include <LEDA/string.h>
#include <LEDA/std/assert.h>


#include <LEDA/b_queue.h>
#include <LEDA/array.h>
#include <LEDA/list.h>

LEDA_BEGIN_NAMESPACE

class fifo_set{

  list<node> L;

public:

  fifo_set(){}

  node del() { if (!L.empty()) return L.pop(); else return nil; }
 
  void insert(node v, int)  { L.append(v); }
  void insert0(node v, int) { L.append(v); }

  bool empty() { return L.empty(); }

  void clear() { L.clear(); }

  ~fifo_set(){}
};

class mfifo_set{

  list<node> L;

public:

  mfifo_set(){}

  node del() { if ( !L.empty() ) return L.pop(); else return nil; }
 
  void insert(node v, int) { L.push(v); }
  void insert0(node v, int){ L.append(v); }

  bool empty() { return L.empty(); }

  void clear() { L.clear(); }

  ~mfifo_set(){}
};


class hl_set{

  int max, max_lev;
  array<list<node> > A;

public:

  hl_set(int max_level):A(max_level+1)
  { max = -1; max_lev = max_level;}

  node del()
  { while (max >= 0 && A[max].empty()) max--;
    if (max >= 0) return A[max].pop(); else return nil; 
  }
 
  void insert(node v, int d)
  { A[d].push(v);
    if (d > max) max = d;
  }

  void insert0(node v, int d) { A[d].append(v); }

  bool empty()
  { while (max >= 0 && A[max].empty()) max--;
    return ( max < 0 ); 
  }

  ~hl_set(){}

  void clear()
  { for (int i = 0; i <= max_lev; i++) A[i].clear();  
    max = -1;
  }
};



template <class NT>
__temp_func_inline
bool CHECK_MAX_FLOW_T(const graph& G, node s, node t,
                      const edge_array<NT>& cap, const edge_array<NT>& f)
{ node v; edge e;
  string loc = "CHECK_MAX_FLOW_T: ";
  bool res = true;

  forall_edges(e,G) 
    res = res && leda_assert(f[e] >= 0 && f[e] <= cap[e], 
              loc + string("illegal flow value for edge %d",index(e)),1);
  
  node_array<NT> excess(G,0);
  forall_edges(e,G) 
  { node v = G.source(e); node w = G.target(e);
    excess[v] -= f[e]; excess[w] += f[e];
  }
  forall_nodes(v,G)
    res = res && leda_assert(v == s || v == t || excess[v] == 0,
                 loc + string("node %d has non-zero excess",index(v)),1);
  
  node_array<bool> reached(G,false);
  queue<node> Q;
  
  Q.append(s); reached[s] = true;
  while ( !Q.empty() )
  { node v = Q.pop(); 
    forall_out_edges(e,v) 
    { node w = G.target(e);
      if ( f[e] < cap[e] && !reached[w] ) 
      { reached[w] = true; Q.append(w); }
    }
    forall_in_edges(e,v) 
    { node w = G.source(e);
      if ( f[e] > 0 && !reached[w] ) 
      { reached[w] = true; Q.append(w); }
    }
  }
  res = res && leda_assert(!reached[t],"t is reachable in G_f",1);
  return res;
}
  


template<class NT, class SET>
__temp_func_inline
NT MAX_FLOW_BASIC_T(const graph& G, node s, node t, 
                    const edge_array<NT>& cap, edge_array<NT>& flow,
                    SET& U,
                    int& num_pushes, int& num_edge_inspections, 
                    int& num_relabels)
{ if (s == t) error_handler(1,"MAXFLOW: source == sink");

  
  
  flow.init(G,0);
  //if (G.outdeg(s) == 0) return 0;
  if (G.first_adj_edge(s) == nil) return 0;

  int n = G.number_of_nodes(); int max_level = 2*n - 1;
  int m = G.number_of_edges(); 

  node_array<NT>  excess(G,0);

  // saturate all edges leaving s

  edge e;
  forall_out_edges(e,s) 
  { NT c = cap[e];
    if (c == 0) continue;
    node v = target(e);
    flow[e] = c;
    excess[s] -= c;
    excess[v] += c;
   } 


  
  node_array<int> dist(G,0); dist[s] = n;
  node v;
  forall_nodes(v,G) 
   if ( excess[v] > 0 ) U.insert(v,dist[v]);


  
  num_relabels = num_pushes = num_edge_inspections = 0;



  
  for(;;) 
  {
    node v = U.del();
   
    if (v == nil) break;
    if (v == t) continue;

    NT  ev = excess[v]; // excess of v 
    int dv = dist[v];   // level of v
    edge e;

    
    for (e = G.first_adj_edge(v); e; e = G.adj_succ(e))
    { num_edge_inspections++;
      NT& fe = flow[e];
      NT  rc = cap[e] - fe;
      if (rc == 0) continue;
      node w = target(e);
      int dw = dist[w];
      if ( dw < dv ) // equivalent to ( dw == dv - 1 )
      { num_pushes++;
        NT& ew = excess[w];
        if (ew == 0) U.insert0(w,dw); 
        if (ev <= rc) 
        { ew += ev; fe += ev;
          ev = 0;   // stop: excess[v] exhausted
          break;
        }
        else
        { ew += rc; fe += rc;
          ev -= rc;
        }
      }
    }

    if ( ev > 0 )
    { 
      for (e = G.first_in_edge(v); e; e = G.in_succ(e))
      { num_edge_inspections++;
        NT& fe = flow[e];
        if (fe == 0) continue;
        node w = source(e);
        int dw = dist[w];
        if ( dw < dv ) // equivalent to ( dw == dv - 1 )
        { num_pushes++;
          NT& ew = excess[w];
          if (ew == 0) U.insert0(w,dw); 
          if (ev <= fe) 
          { fe -= ev; ew += ev;
            ev = 0;   // stop: excess[v] exhausted
            break;
          }
          else
          { ew += fe; ev -= fe;
            fe = 0;
          }
        }
      }
 }

    excess[v] = ev;

    if (ev > 0) 
    { dist[v]++; 
      num_relabels++;
      U.insert(v,dist[v]);
    }
  } 
    

#ifdef TEST
  assert(CHECK_MAX_FLOW_T(G,s,t,cap,flow));
#endif

  return excess[t];
}



template<class NT, class SET>
__temp_func_inline
NT MAX_FLOW_LH_T(const graph& G, node s, node t, 
                  const edge_array<NT>& cap, 
                  edge_array<NT>& flow,
                  SET& U,
                  int& num_pushes, 
                  int& num_edge_inspections,
                  int& num_relabels)
{ if (s == t) error_handler(1,"MAXFLOW: source == sink");

  
  
  flow.init(G,0);
  //if (G.outdeg(s) == 0) return 0;
  if (G.first_adj_edge(s) == nil) return 0;

  int n = G.number_of_nodes(); int max_level = 2*n - 1;
  int m = G.number_of_edges(); 

  node_array<NT>  excess(G,0);

  // saturate all edges leaving s

  edge e;
  forall_out_edges(e,s) 
  { NT c = cap[e];
    if (c == 0) continue;
    node v = target(e);
    flow[e] = c;
    excess[s] -= c;
    excess[v] += c;
   } 


  
  node_array<int> dist(G,0); dist[s] = n;
  node v;
  forall_nodes(v,G) 
   if ( excess[v] > 0 ) U.insert(v,dist[v]);


  
  num_relabels = num_pushes = num_edge_inspections = 0;



  
  for(;;) 
  {
    node v = U.del();
   
    if (v == nil) break;
    if (v == t) continue;

    NT  ev = excess[v]; // excess of v 
    int dv = dist[v];   // level of v
    edge e;

    if ( dist[v] < n )
    { 
      for (e = G.first_adj_edge(v); e; e = G.adj_succ(e))
      { num_edge_inspections++;
        NT& fe = flow[e];
        NT  rc = cap[e] - fe;
        if (rc == 0) continue;
        node w = target(e);
        int dw = dist[w];
        if ( dw < dv ) // equivalent to ( dw == dv - 1 )
        { num_pushes++;
          NT& ew = excess[w];
          if (ew == 0) U.insert0(w,dw); 
          if (ev <= rc) 
          { ew += ev; fe += ev;
            ev = 0;   // stop: excess[v] exhausted
            break;
          }
          else
          { ew += rc; fe += rc;
            ev -= rc;
          }
        }
      }
 }
    if ( ev > 0 )
    { 
      for (e = G.first_in_edge(v); e; e = G.in_succ(e))
      { num_edge_inspections++;
        NT& fe = flow[e];
        if (fe == 0) continue;
        node w = source(e);
        int dw = dist[w];
        if ( dw < dv ) // equivalent to ( dw == dv - 1 )
        { num_pushes++;
          NT& ew = excess[w];
          if (ew == 0) U.insert0(w,dw); 
          if (ev <= fe) 
          { fe -= ev; ew += ev;
            ev = 0;   // stop: excess[v] exhausted
            break;
          }
          else
          { ew += fe; ev -= fe;
            fe = 0;
          }
        }
      }
 }

    excess[v] = ev;

    if (ev > 0) 
    { dist[v]++; 
      num_relabels++;
      U.insert(v,dist[v]);
    }
  }

#ifdef TEST
  assert(CHECK_MAX_FLOW_T(G,s,t,cap,flow));
#endif

  return excess[t];
}



template<class NT, class SET>
__temp_func_inline
NT MAX_FLOW_LRH_T(const graph& G, node s, node t, 
                  const edge_array<NT>& cap, 
                  edge_array<NT>& flow,
                  SET& U,
                  int& num_pushes, 
                  int& num_edge_inspections,
                  int& num_relabels)
{ if (s == t) error_handler(1,"MAXFLOW: source == sink");

  
  
  flow.init(G,0);
  //if (G.outdeg(s) == 0) return 0;
  if (G.first_adj_edge(s) == nil) return 0;

  int n = G.number_of_nodes(); int max_level = 2*n - 1;
  int m = G.number_of_edges(); 

  node_array<NT>  excess(G,0);

  // saturate all edges leaving s

  edge e;
  forall_out_edges(e,s) 
  { NT c = cap[e];
    if (c == 0) continue;
    node v = target(e);
    flow[e] = c;
    excess[s] -= c;
    excess[v] += c;
   } 


  
  node_array<int> dist(G,0); dist[s] = n;
  node v;
  forall_nodes(v,G) 
   if ( excess[v] > 0 ) U.insert(v,dist[v]);


  
  num_relabels = num_pushes = num_edge_inspections = 0;



  
  for(;;) 
  {
    node v = U.del();
   
    if (v == nil) break;