mw_matching.t

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

  while(it && (it != cur->child->left)) {
    traverse_tree(it, k);
    it = it->right;
  }
  if (it) traverse_tree(it, k);
 
  if (k != nil) {
    copy_key(k);
    cur->key = k;
  }
  else {
    clear_key(cur->key);
    clear_inf(cur->inf);
    std_memory.deallocate_bytes(cur, sizeof(conc_pq_node));
  }
}


void conc_pq_tree::reset() { 
  if (!root) return;
  if (cmp(minptr->key, infinity) == 0) return;
 
  // increase all priorities to infty
  conc_pq_node *cur = first_item();
  while (cur) {
    increase_prio(cur, infinity);
    cur = next_item(cur);
  }
}


void conc_pq_tree::clear() {
  if (!root) return;

  // delete tree
  traverse_tree(root);
  
  // std_memory.deallocate_list(head_leaf, tail_leaf, sizeof(conc_pq_node));
  
  head_leaf = tail_leaf = nil;
  root = minptr = nil;
}




void conc_pq_tree::print_item(conc_pq_node *it, ostream &out) const {
  if (it == nil) return;
  out << "<";
  print_key(it->key, out);
  out << ", ";
  print_inf(it->inf, out);
  out << ">";
}

void conc_pq_tree::print(ostream &out, string s, char space) const {

  out << s;
  conc_pq_node *cur = first_item();
  
  while (cur) {
    print_item(cur, out);
    out << space;
    cur = next_item(cur);
  }
  out.flush();
}



conc_pq_node* my_root(conc_pq_node *p) {
  conc_pq_node *cur = p;
  
  if (cur == nil) return nil;
    
  while (cur->parent) cur = cur->parent;
  
  return cur;
}


conc_pq_tree* my_tree(conc_pq_node *p) {
  conc_pq_node *cur = my_root(p);

  if (cur == nil) return nil;
  else return cur->tree;
}


GenPtr get_owner(conc_pq_node* it) 
{ return (it ? my_tree(it)->owner : nil); }





// ----- #include "concat_pq.h"

/*{\Manpage {concat_pq} {P, I} {Concatenable Priority Queues} {Q}}*/

typedef conc_pq_tree::item c_pq_item;

template<class P, class I>
class concat_pq : public virtual conc_pq_tree {

/*{\Mtext 
We implemented a data structure |\Mtype| supporting all needed 
operations of data type {\it concatenable \pq} as introduced in
\secref{sec: concatenable pq}.
The implementation is based on $(a,b)$--trees; we chose $a=2$ and $b=16$.
|concat| and |split_at_item| are essentially realized as discussed
at the end of \secref{sec: concatenable pq}. 
We do not intend to 
go into the implementation details. Instead, the specification of all 
operations needed in the subsequent sections is given.


In \secref{sec: survey} we outlined the idea of using a {\it union--find} data
structure with {\it split} operation to handle the surface graph. 
The method we use in our implementation is different. Since a concatenable \pq\ 
will be assigned to each surface blossom, we decided to extend the functionality 
of |\Mtype| such that it also enables the maintenance of the surface graph.
We use the underlying $(a,b)$--trees to identify a setable object (which will 
be the surface blossom) of a given item (which will correspond to a vertex).
The way this is achieved is as follows. 
Each root of an $(a,b)$--tree stores a pointer to the object representing 
that tree. 
Traversing from an item |it| towards the root, we can identify the 
$(a,b)$--tree object containing the item |it|. 
Moreover, each $(a,b)$--tree object has a generic pointer |owner| (a generic
pointer is of type |void*|) which is setable by the user; see operation 
|set_owner|. Consequently, the |owner| of any item |it| can be 
identified (operation |get_owner|) in time $O(\log n)$, where $n$ denotes the 
number of items in the $(a,b)$--tree.
}*/


  /*{\Mdefinition
    An instance |\Mvar| of the parameterized data type |\Mname| is a collection of items
    (type |c_pq_item|). 
    Every item contains a priority from a linearly ordered type $P$ and an information from 
    an arbitrary type $I$. We use $\Litem{p,i}$ to denote a |c_pq_item| with priority $p$ 
    and information $i$.
    \ignore{|P| is called the priority type and |I| the information type of |\Mvar|.}
    The data structure requires a designated element |infinity| of |P|, with
    $|infinity| \geq p$ for all $p \in P$ and equality holds only if |p=infinity|.
    An item $\Litem{p,i}$ with |p=infinity| is {\it irrelevant} to |\Mvar|. 
    The number of items in |\Mvar| is called the |size| of |\Mvar|. |\Mvar| is {\it empty} 
    when all its items are irrelevant, or when |\Mvar| has size zero. 
    A setable generic pointer |owner| (type |void*|) is associated with |\Mvar|. 
  }*/
  
  const leda_cmp_base<P>* cmp_ptr;

  int (*cmp_ptr1)(const P&, const P&);
  
  int cmp(GenPtr x, GenPtr y)  const { 
    if (cmp_ptr1)
      return LEDA_CALL2(*cmp_ptr1, P, x, y);
    else
      return LEDA_CALL2(*cmp_ptr, P, x, y);
  }

  int  ktype_id;
  int  key_type_id() const  { return ktype_id; }  

  void clear_key(GenPtr &x) const { LEDA_CLEAR(P, x); }
  void clear_inf(GenPtr &x) const { LEDA_CLEAR(I, x); }
  void copy_key(GenPtr &x)  const { LEDA_COPY(P, x); }
  void copy_inf(GenPtr &x)  const { LEDA_COPY(I, x); }
  void print_key(GenPtr &x, ostream &out = cout)  const { LEDA_PRINT(P, x, out); }
  void print_inf(GenPtr &x, ostream &out = cout)  const { LEDA_PRINT(I, x, out); }


public:

/* {\Mtypes 5} */ 

  typedef c_pq_item item;
  /* {\Mtypemember   the item type.} */

  typedef P prio_type;  
  /* {\Mtypemember   the priority type.} */  

  typedef I inf_type;
  /* {\Mtypemember   the information type.} */ 

// was 5.5
/*{\Mcreation Q 6.2}*/

  concat_pq(const leda_cmp_base<P>& cmp, P infty) : conc_pq_tree() {
    cmp_ptr  = &cmp; 
    cmp_ptr1 = 0; 
    ktype_id = UNKNOWN_TYPE_ID; 
    conc_pq_tree::infinity = leda_cast(infty);
    conc_pq_tree::owner = this;
  }

  concat_pq() : conc_pq_tree() {    
    cmp_ptr1 = compare;
    ktype_id = LEDA_TYPE_ID(P);    
    conc_pq_tree::infinity = leda_cast(MAX_VALUE(P));
    conc_pq_tree::owner = this;
  }
  /*{\Mcreate   creates an instance |\Mvar| of type |\Mname| based on the linear
    order defined by the global compare function |compare(const P&, const P&)| 
    and initializes it with the empty priority queue. |infinity| is set to the 
    maximum value of type |P|.}*/

  concat_pq(P p, I i) : conc_pq_tree(leda_cast(p), leda_cast(i)) {
    cmp_ptr1 = compare;
    ktype_id = LEDA_TYPE_ID(P); 
    conc_pq_tree::infinity = leda_cast(MAX_VALUE(P));
    conc_pq_tree::owner = this;
  }

  concat_pq(int (*cmp)(const P&, const P&), P infty) : conc_pq_tree() {
    cmp_ptr1 = cmp;
    ktype_id = UNKNOWN_TYPE_ID; 
    conc_pq_tree::infinity = leda_cast(infty);
    conc_pq_tree::owner = this;
  }
  /* {\Mcreate   creates an instance |\Mvar| of type |\Mname| based on the linear order
    defined by the compare function |cmp| and sets the designated element |infinity| 
    to |infty|. |\Mvar| is initialized with the empty priority queue.
    \precond |cmp| must define a linear order on |P| and |infty| satisfies the conditions
    stated above, i.e.~$|cmp|(|infty|, p) \geq 0$ for all $p \in P$.} */


  ~concat_pq() { conc_pq_tree::clear(); }


// was 1.8 3.7
/*{\Moperations 1.8 4.4}*/   

  P& infinity() { return LEDA_ACCESS(P, conc_pq_tree::infinity); }
  /* {\Mop   returns a reference to the value of |infinity|.} */

  c_pq_item init(P p, I i) {
    return conc_pq_tree::init(leda_cast(p), leda_cast(i));
  }
  /*{\Mop   initializes |\Mvar| to the priority queue containing 
    only the item $\Litem{p, i}$ and returns that item.}*/

  virtual const P& prio(c_pq_item it) const { 
    return LEDA_CONST_ACCESS(P, conc_pq_tree::key(it)); 
  }
  /*{\Mop   returns the priority of item $it$.
    \precond $it$ is an item in |\Mvar|.}*/

  virtual I& inf(c_pq_item it) {
    return LEDA_ACCESS(I, conc_pq_tree::inf(it)); 
  }

  virtual const I& inf(c_pq_item it) const { 
    return LEDA_CONST_ACCESS(I, conc_pq_tree::inf(it)); 
  }
  /*{\Mop   returns the information of item $it$.
    \precond $it$ is an item in |\Mvar|.}*/

  virtual c_pq_item insert(P p, I i) {
    return conc_pq_tree::insert(leda_cast(p), leda_cast(i));
  }
  /* {\Mop   adds a new item $\Litem{p, i}$ to |\Mvar| and returns it. All items in
    |\Mvar| precede $\Litem{p, i}$.} */


  void concat(concat_pq<P,I> &pq, int dir = leda::after) {
    conc_pq_tree::conc(pq);
  }
  /*{\Mop   concatenates |\Mvar| with |pq|. The items in |\Mvar| precede (succeed)   
    the items of |pq|, when $|dir|=|after|$ ($|dir|=|before|$). |pq| is 
    made empty, i.e.~contains no items thereafter.}*/

  void split_at_item(c_pq_item it, concat_pq<P,I> &pq1, concat_pq<P,I> &pq2) { 
    conc_pq_tree::split_at_item(it, pq1, pq2); 
  }
  /*{\Mopl  splits |\Mvar| at item |it| into |pq1| and |pq2| such that |it| is 
    the last item of |pq1|. 
    In case $|it|=|nil|$, |pq2| becomes |\Mvar| and |pq1| becomes empty.
    The instance |\Mvar| is empty thereafter, unless it is given as one
    of the arguments.}*/

  virtual c_pq_item find_min() const { return conc_pq_tree::find_min(); }
  /*{\Mop   returns an item with minimal priority (|nil| if |\Mvar| is empty).}*/

  virtual P del_min() { 
    P x = prio(find_min()); 
    conc_pq_tree::del_min(); 
    return x; 
  }
  /*{\Mop   makes the item $|it|=|\Mvar.find_min|()$ irrelevant to |\Mvar| by
    setting its priority to |infinity|. The former priority is returned.}*/
     
  virtual void del_item(c_pq_item it) { conc_pq_tree::del_item(it); }
  /*{\Mopl   makes the item $it$ irrelevant to |\Mvar|.
    \precond |it| is an item in |\Mvar|.}*/

  virtual bool decrease_p(c_pq_item it, const P& x) { 
    return conc_pq_tree::decrease_key(it, leda_cast(x)); 
  }
  /*{\Mopl   makes $x$ the new priority of item $it$. The function returns |true| iff
    the operation was successful, i.e.~|\Mvar.prio(it)| was larger than $x$.}*/

  virtual bool increase_p(c_pq_item it, const P& x) { 
    return conc_pq_tree::increase_key(it, leda_cast(x)); 
  }
  /*{\Mopl   makes $x$ the new priority of item $it$. The function returns |true| iff
    the operation was successful, i.e.~|\Mvar.prio(it)| was smaller than $x$.}*/

  virtual const I& operator[](c_pq_item it) const
  { return LEDA_CONST_ACCESS(I, conc_pq_tree::inf(it)); }

  
  virtual I& operator[](c_pq_item it) 
  { return LEDA_ACCESS(I, conc_pq_tree::inf(it)); }
  /* {\Marrop   returns a reference to the information of item $it$.
    \precond $it$ is an item in |\Mvar|.} */


  int  size() const { return conc_pq_tree::size(); }
  /*{\Mop   returns the size of |\Mvar|.}*/


  bool empty() const { return conc_pq_tree::empty(); }
  /*{\Mop   returns |true|, if |\Mvar| is empty, and |false| otherwise.}*/


  void reset() { conc_pq_tree::reset(); }
  /*{\Mop   makes |\Mvar| the empty priority queue by setting all priorities to |infinity|.}*/


  void clear() { conc_pq_tree::clear(); }
  /*{\Mop   makes |\Mvar| the empty priority queue by deleting all items. }*/


  void set_owner(GenPtr pt) { conc_pq_tree::set_owner(pt); }
  /*{\Mop   sets |owner| of |\Mvar| to the object pointed to by the 
            generic pointer |pt| (type |void*|).}*/


/*{\Mtext \mansection{Friend Functions}}*/

/*
  friend GenPtr get_owner(c_pq_item it);
*/
  /*{\Mfunc returns the generic pointer |owner| of the instance containing item |it|.}*/


/*{\Mtext \mansection{Iteration}

{\bf forall\_items}($it, Q$)       
$\{$ ``the items of $Q$ are successively assigned to $it$'' $\}$

{\bf forall}($i, Q$)       
$\{$ ``the information parts of the items of $Q$ are successively assigned to $i$'' $\}$ 
}*/


};

c_pq_item my_root(c_pq_item it);
/* {\Mfunc   returns the root of item |it|.} */


template<class P, class I> 
inline c_pq_item create_concat_pq(P p, I i) {
  concat_pq<P, I> *pq = new concat_pq<P, I>;
  return pq->init(p, i);
}

template<class P, class I> 
inline c_pq_item create_concat_pq(P p, I i, concat_pq<P, I>* &pq) {
  pq = new concat_pq<P, I>;
  return pq->init(p, i);
}

template<class P, class I> 
inline void my_concat_pq(c_pq_item it, concat_pq<P, I>* &pq) {
  pq = (concat_pq<P, I>*)(my_tree(it)->owner);
}
/* {\Mfunc   returns a pointer to the instance of type |\Mname| that contains 
  item |it| in |pq|.} */



/*{\Mimplementation
  All access operations take time O(1). 
  |concat| and |split_at_item| take time $O(\log n)$, where $n$ is the (maximum) number of 
  elements in the priority queue(s). Operations |clear| and |reset| take time $O(n)$.
  All other operations take time (at most) $O(\log n)$.
}*/         


// ----- #include "greedy.t"


#if defined(_CHECK) 
#undef _CHECK
#endif


template<class NT>
__temp_func_inline
int greedy_matching(const graph &G, const edge_array<NT> &w, 
                    node_array<NT> &pot, node_array<node> &mate, 
                    bool perfect) {
#ifdef _INFO
  cout << "\t\tCREATING greedy matching..." << flush;
  float t = used_time();
#endif

  
  edge e;
  node u, v;
  pot.init(G, -MAX_VALUE(NT));

  forall_nodes(u, G)
    if (degree(u) == 0) pot[u] = 0;

  forall_edges(e, G) {
    u = source(e);
    v = target(e);
    pot[u] = leda_max(pot[u], (w[e]/2));
    pot[v] = leda_max(pot[v], (w[e]/2));
  }
  
  int free = G.number_of_nodes();
  mate.init(G, nil);

  forall_edges(e, G) {
    u = source(e);
    v = target(e);
    if ((pot[u] + pot[v] == w[e]) &&
         (mate[u] == nil) && (mate[v] == nil)) {
      mate[v] = u;
      mate[u] = v;
  #ifdef MW_MATCHING_DEBUG
      if (debug) cout << "(" << index(u) << ", " << index(v) << ")" << endl;
  #endif
      free -= 2;
    }    
  }
  
  if (perfect) {
    forall_nodes(u, G) {
      if (!mate[u]) {
        NT slack = MAX_VALUE(NT);
        forall_inout_edges(e, u) {
          v = opposite(u, e);
          slack = leda_min(pot[u] + pot[v] - w[e], slack);
        }
        pot[u] -= slack;
      }
    }
  }
#ifdef _CHECK
  cout << "\t\tCHECK FEASIBILITY..." << flush;
  check_feasibility(G, w, pot, mate, perfect);
  cout << "OK!" << endl;
#endif
#ifdef _INFO
  printf("ready! %d free vertices. TIME: %3.2f sec.\n", free, used_time(t));
#endif

  return free;
}





extern bool debug;

void alternate_cycle(node u, node_array<node> &mate, 
                     node_array<node> &pred) {

  node cur1 = pred[u];  
  while (cur1 != u) {
    mate[pred[cur1]] = cur1;
    mate[cur1] = pred[cur1];
    node h = pred[cur1];
    pred[cur1] = nil;
    cur1 = h;
    h = pred[cur1];
    pred[cur1] = nil;
    cur1 = h;
  }
  pred[u] = nil; 
}

void alternate_path(node u, node_array<int> &label,
                    node_array<node> &mate, node_array<node> &pred) {

  node cur = u;
  node pre = nil, nxt;
  
  while (cur) {
    if (label[cur] == even) {
      nxt = mate[cur];