📄 mw_matching0.t
字号:
/*******************************************************************************++ LEDA 4.5 +++ mw_matching0.t+++ Copyright (c) 1995-2004+ by Algorithmic Solutions Software GmbH+ All rights reserved.+ *******************************************************************************/// $Revision: 1.1 $ $Date: 2004/02/11 13:24:26 $#if !defined(LEDA_ROOT_INCL_ID)#define LEDA_ROOT_INCL_ID 450467#include <LEDA/PREAMBLE.h>#endif
// Guido Sch鋐er, 11/2003 made some modifications
// to the algorithm given in mw_matching.t
// This algorithm is claimed to be more efficient
// this is not yet tested
#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>
float check_t, total_t;
#ifdef _STAT
int adj_c, alternate_c, grow_c, shrink_c, expand_c, augment_c,
destroy_c, scan_c;
float alternate_t, grow_t, shrink_t, expand_t, augment_t,
destroy_t, scan_t;
float conc_pq_del_t;
float heur_t, init_t, alg_t, extract_t, clean_t;
int potential_updates, nodes_in_trees, blossoms_in_trees,
max_nodes_in_trees, max_blossoms_in_trees;
#endif
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, `get_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;
}
// GSchange
// ~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;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -