mw_matching.t

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

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

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

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

#include <LEDA/mw_matching.h>

#include <LEDA/array.h>
#include <LEDA/tuple.h>
#include <LEDA/slist.h>
#include <LEDA/graph.h>
#include <LEDA/graph_misc.h>
#include <LEDA/graph_alg.h>
#include <LEDA/p_queue.h>
#include <LEDA/node_slist.h>
#include <LEDA/node_pq.h>

#include <LEDA/map.h> // only for debug
#include <LEDA/h_array.h>

#include <LEDA/std/stdio.h>
#include <LEDA/std/limits.h>
#include <LEDA/std/float.h>
#include <LEDA/std/assert.h>



LEDA_BEGIN_NAMESPACE

inline char   get_max_val(const char*)   { return CHAR_MAX;  }
inline short  get_max_val(const short*)  { return SHRT_MAX;  }
inline int    get_max_val(const int*)    { return INT_MAX;   }
inline long   get_max_val(const long*)   { return LONG_MAX;  }
inline float  get_max_val(const float*)  { return FLT_MAX; }
inline double get_max_val(const double*) { return DBL_MAX; }

template<class NT> inline NT get_max_val(const NT*) 
{ error_handler(1, "Sorry, `max_val' not specified for that type."); }

#define MAX_VALUE(T) get_max_val((T*)0)


typedef enum {even, odd, unlabeled} LABEL;



// ----- #include "checker.t"

template<class NT> 
__temp_func_inline
void check_feasibility(const graph &G, 
		       const edge_array<NT> &w, 
		       node_array<NT> &pot,
		       node_array<node> &mate, 
		       bool perfect ) {

  edge e;
  node u, v;

  forall_edges(e, G) {
    u = source(e);
    v = target(e);   
    assert(pot[u] + pot[v] >= w[e]);
    assert(((pot[u] + pot[v] - w[e]) % 2) == 0);
  }

  if (!perfect) forall_nodes(u, G) assert(pot[u] >= 0);

  forall_edges(e, G) {
    u = source(e);
    v = target(e);
    
    if (mate[source(e)]) 
      assert(mate[mate[source(e)]] == source(e));
    if (mate[target(e)])
      assert(mate[mate[target(e)]] == target(e));
  }

  node_array<bool> matched(G, false);

  forall_edges(e, G) {
    u = source(e);
    v = target(e);

    if (mate[u] && (mate[u] == v) &&
	mate[v] && (mate[v] == u)) {

      assert(!matched[u]);
      assert(!matched[v]);
    
      matched[u] = matched[v] = true;
    }
  }
}

// ----- #include "conc_pq_tree.h"


// ----------------------------------------------------------------------
//  Class `conc_pq_node'
// ----------------------------------------------------------------------

class conc_pq_tree;

class conc_pq_node {  

  friend class conc_pq_tree;
  friend conc_pq_node* my_root(conc_pq_node* p);
  friend conc_pq_tree* my_tree(conc_pq_node* p);

  conc_pq_tree* tree;     // pointer to the tree containing this node

  int height;      // height (!depth) of tree rooted at this
  int leaves;      // number of leaves in tree rooted at this
  int children;    // number of children

  GenPtr key;      // key  stored in conc_pq_node
  GenPtr inf;      // info stored in conc_pq_node

  
  conc_pq_node *succ;   // pointer to succ leaf
  conc_pq_node *pred;   // pointer to pred leaf
  conc_pq_node *left;   // pointer to left sibbling
  conc_pq_node *right;  // pointer to right sibbling
  conc_pq_node *parent; // pointer to parent node
  conc_pq_node *child;  // pointer to leftmost child


public:

  conc_pq_node(GenPtr k, GenPtr i, conc_pq_tree* p) {
    tree = p;
    height = 0;
    leaves = 1;
    children = 0;
    key  = k;
    inf  = i;
    succ = pred  = nil;
    left = right = this;
    parent = child = nil;
  }

  ~conc_pq_node() {}

  LEDA_MEMORY(conc_pq_node);

};



// ----------------------------------------------------------------------
//  Declaration of Class `conc_pq_tree'
// ----------------------------------------------------------------------

class conc_pq_tree {

private:

  // list of leaves
  conc_pq_node *head_leaf, *tail_leaf;
  
  int a;
  int b;

  GenPtr tree_inf;      // information associated with the tree 
                        // (not realized yet)

  conc_pq_node *root;   // pointer to the root node 
  conc_pq_node *minptr; // pointer to the min. leaf


  conc_pq_node* new_conc_pq_node(GenPtr k, GenPtr i) 
  { return new conc_pq_node(k, i, this); }

  conc_pq_node* locate_min(conc_pq_node *p) const;

  void decrease_prio(conc_pq_node *p, GenPtr k);
  conc_pq_node* increase_prio(conc_pq_node *p, GenPtr k);

  conc_pq_node* split_node(conc_pq_node* p);
  void delete_node(conc_pq_node *p); 

  void add_leaves(conc_pq_node *p, int leaves);
  void print_tree(conc_pq_node *local_root, int blancs) const; 
  void traverse_tree(conc_pq_node* cur, GenPtr k = nil);

  conc_pq_node* conc(conc_pq_node* r1, conc_pq_node* r2);


  virtual int cmp(GenPtr, GenPtr) const { return 0; }
  
  virtual void clear_key(GenPtr&) const {}
  virtual void clear_inf(GenPtr&) const {}
  virtual void copy_key(GenPtr&)  const {}
  virtual void copy_inf(GenPtr&)  const {}
  virtual void print_key(GenPtr&, ostream &out = cout)  const {}
  virtual void print_inf(GenPtr&, ostream &out = cout)  const {}

  virtual int key_type_id() const { return UNKNOWN_TYPE_ID; }

public:

  GenPtr infinity;                // max value of key type

  typedef conc_pq_node* item;

  conc_pq_tree(int _a=2, int _b=16);  
  conc_pq_tree(GenPtr p, GenPtr i, int _a = 2, int _b = 16);

  conc_pq_tree(const conc_pq_tree& pq);                        // not realized
  conc_pq_tree& operator=(const conc_pq_tree& pq);             // not realized

  conc_pq_node* init(GenPtr p, GenPtr i);

  virtual ~conc_pq_tree() { clear(); }

  const GenPtr& key(conc_pq_node *p) const { return p->key; }
  GenPtr&       key(conc_pq_node *p) { return p->key; }
  GenPtr&       inf(conc_pq_node *p) const { return p->inf; }
  
  conc_pq_node* insert(GenPtr p, GenPtr i) ;
  
  void conc(conc_pq_tree &pq, int dir = leda::after);  
  void split_at_item(conc_pq_node *p, conc_pq_tree &pq1, conc_pq_tree &pq2);

  conc_pq_node* find_min() const { return minptr; }

  void del_min() { del_item(minptr); }
  void del_item(conc_pq_node *p);

  //  void decrease_key(conc_pq_node *p, GenPtr k);
  bool decrease_key(conc_pq_node *p, GenPtr k);

  // mod. 15/01, added new funtion (needed for multiple search tree approach)
  bool increase_key(conc_pq_node *p, GenPtr k);

  int  size()   const { return (root ? root->leaves : 0); }
  bool empty()  const 
  { return ((root == nil) || (cmp(minptr->key, infinity) == 0)); }
  
  virtual void reset();
  virtual void clear();

  void *owner;     // pointer to the owner of the tree

  // GenPtr get_owner(conc_pq_node* it) { return (it ? my_tree(it)->owner : nil); }
  virtual void set_owner(GenPtr p) { owner = p; }

  int  height() const { return (root ? root->height : -1); }

  void print() const { print_tree(root, 0); } 

  conc_pq_node* first_item() const { return head_leaf; }
  conc_pq_node* last_item()  const { return tail_leaf; }
  conc_pq_node* next_item(conc_pq_node *p) const { return (p ? p->succ : nil); }
  conc_pq_node* pred_item(conc_pq_node *p) const { return (p ? p->pred : nil); }

  conc_pq_node* stl_pred_item(conc_pq_node *p) const {  
    error_handler(1,"conc_pq_tree::stl_pred_item not implemented."); 
    return nil; 
  }   
  conc_pq_node* stl_next_item(conc_pq_node *p) const 
  { return (p ? p->succ : head_leaf); }


  void print_item(conc_pq_node *it, ostream &out = cout) const;
  virtual void print(ostream &out, string s, char space = ' ') const;

  friend ostream& operator<<(ostream &out, const conc_pq_tree &p) 
  { p.print(out, ""); return out; }

  
  //  LEDA_MEMORY(conc_pq_tree);

};

  


// ----------------------------------------------------------------------
//  Realization of Class `conc_pq_tree'
// ----------------------------------------------------------------------


conc_pq_tree::conc_pq_tree(int _a, int _b) {  
  if (_a >= 2 && _b >= 2*_a-1) {
    head_leaf = tail_leaf = nil;
    root = minptr = nil;
    a = _a;
    b = _b;
  }
  else 
    error_handler(1, "conc_pq_tree::conc_pq_tree(int _a, int _b): invalid arguments for _a and _b.");
}

conc_pq_tree::conc_pq_tree(GenPtr p, GenPtr i, int _a, int _b) {  
  if (_a >= 2 && _b >= 2*_a-1) {
    copy_key(p);
    copy_inf(i);
    conc_pq_node* new_r = new_conc_pq_node(p, i);
    head_leaf = tail_leaf = new_r;
    root = new_r;
    minptr = root;    
    a = _a;
    b = _b;
  }
  else 
    error_handler(1, "conc_pq_tree::conc_pq_tree(GenPtr p, GenPtr i, int _a, int _b): invalid arguments for _a and _b.");
}


conc_pq_node* conc_pq_tree::init(GenPtr p, GenPtr i) {
  clear();
  copy_key(p);
  copy_inf(i);
  conc_pq_node* new_r = new_conc_pq_node(p, i);
  head_leaf = tail_leaf = new_r;
  root = new_r;
  minptr = root;

  return new_r;
}


conc_pq_node* conc_pq_tree::insert(GenPtr p, GenPtr i) { 
  conc_pq_tree cur(a, b);
  conc_pq_node *x = cur.init(p, i);
  conc(cur);
  return x;
}


conc_pq_tree::conc_pq_tree(const conc_pq_tree& pq) {
  error_handler(1, "conc_pq_tree::conc_pq_tree(const conc_pq_tree& pq): not implemented yet.");
}


conc_pq_tree& conc_pq_tree::operator=(const conc_pq_tree& pq) {
  error_handler(1, "conc_pq_tree::operator=(...): not implemented yet.");
  return *this;
}


conc_pq_node* conc_pq_tree::split_node(conc_pq_node* p) {
  // in case that p has more than b children, p is split into
  // two nodes r and l having half of the children of p each. 
  // it returns the highest (with max. height) node considered.

  if (p->children <= b) return p;

  conc_pq_node *l = p, *f = p->parent;

  // create new node r (to the right of l)
  GenPtr new_key = l->key;
  copy_key(new_key);  
  conc_pq_node *r = new_conc_pq_node(new_key, nil);
  r->height = l->height;  

  // determine node cur: all children of f up to 
  // cur (inclusive) stay children of r and the others
  // become children of r. determine the min. key of
  // left half
  conc_pq_node *cur = l->child;
  GenPtr minkey = cur->key;

  int cnt = 0;
  while (cnt < p->children / 2) {
    cnt++;
    cur = cur->right;
    if (cmp(minkey, cur->key) > 0) 
      minkey = cur->key;
  }

  // adjust children counter
  r->children = l->children - (cnt+1);
  l->children = cnt+1;
  
  // split sibblings list
  r->child = cur->right;
  cur->right = l->child;
  r->child->left = l->child->left;
  l->child->left->right = r->child;
  l->child->left = cur;

  // (possibly) correct key of l
  if (cmp(l->key, minkey) != 0) {
    copy_key(minkey);
    l->key = minkey;
  }
    
  // set parent information for all (new) children of r
  // and determine the (possibly new) min of all children. 
  // keep track of the number of leaves of all children of r
  cur = r->child;
  minkey = cur->key;
  int leaves_cnt = cur->leaves;
  cur->parent = r;
  cur = cur->right;
  
  while (cur != r->child) {
    leaves_cnt += cur->leaves; 
    cur->parent = r;    
    if (cmp(minkey, cur->key) > 0)
      minkey = cur->key;
    cur = cur->right;
  }

  // compute new number of leaves for l and r
  l->leaves -= leaves_cnt;
  r->leaves  = leaves_cnt;

  // (possibly) correct key of r
  if (cmp(r->key, minkey) != 0) {
    copy_key(minkey);
    r->key = minkey;
  }

  // create new root node (when l's parent is nil)
  // with key = min{l->key, r->key} and only child l
  if (f == nil) {
    minkey = r->key;
    if (cmp(minkey, l->key) > 0) 
      minkey = l->key;
    copy_key(minkey);
    f = new_conc_pq_node(minkey, nil);
    f->child = l;
    f->children = 1;
    f->height = l->height + 1;
    f->leaves = l->leaves + r->leaves;
    l->parent = f;
  }

  // INVARIANT: l is child of f
  // make r a new child of f (to the right of l)
  r->parent = f;
  r->right = l->right;
  r->left  = l;
  l->right->left = r;
  l->right = r;

  f->children += 1;

  // recursively split f
  if (f->children > b) return split_node(f);
  else return f;
}



void conc_pq_tree::add_leaves(conc_pq_node *p, int leaves) {
  // traverses the path from p up to the root and sets
  // for each node cur on that path:
  // cur.leaves += leaves

  conc_pq_node* cur = p;

  while (cur) {
    cur->leaves += leaves;
    cur = cur->parent;
  }
}



conc_pq_node* conc_pq_tree::conc(conc_pq_node* r1, conc_pq_node* r2) {
  // concatenates the two trees rooted at r1 and r2 and 
  // returns the root of the concatenated trees.
  // minptr and list of leaves are NOT maintained here

  if (r1 == nil) return r2;
  if (r2 == nil) return r1;

  int h1 = r1->height;
  int h2 = r2->height;

  conc_pq_node *cur, *f;

  if (h1 >= h2) {
    // seek rightmost node cur in tree rooted at r1 
    // with height h2 and let f be the father of cur
    cur = r1;
    while (cur->height != h2) cur = cur->child->left;
    f = cur->parent;