开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_tree_collect.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：12k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_tree_collect.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _tree_collect.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. // dyna_trees.c
  16. #include <LEDA/tree_collection.h>
  18. #define BIG MAXFLOAT
  21. void dyna_trees::splay(d_vertex x) {
  22.      d_vertex y, z, zz, a, b, c, d;
  23.      double   mincost_a,
  24.       mincost_b,
  25.       mincost_c,
  26.       mincost_d,
  27.       mincost_x,
  28.       mincost_y,
  29.       mincost_z,
  30.       
  31.       cost_x,
  32.       cost_y,
  33.       cost_z;
  35.      
  36.      while (x->parent) {
  37.   // splay-step : 
  39.   y=x->parent; // Vater von x
  40.   z=y->parent; // Grossvater von x (oder 0)
  41.   zz = (z==0) ? 0 : z->parent; // Urgrossvater von z (oder 0)
  43.   // 1.Fall: x hat Vater, aber keinen Grossvater
  45.   if (z==0){ 
  46. if (y->left==x) { 
  47.     // x wurzel des linken unterbaums  (1)
  48.     a=x->left;
  49.     b=x->right;
  50.     c=y->right;
  51.     x->parent=0;
  52.     x->right=y;
  53.     y->parent=x;
  54.     y->left=b;
  55.     if (b) b->parent=y;
  57.     x->successor=y->successor;
  58.     y->successor=0;
  60.     mincost_a = (a) ? a->dmin + x->dmin + y->dmin : BIG;
  61.     mincost_b = (b) ? b->dmin + x->dmin + y->dmin : BIG;
  62.     mincost_c = (c) ? c->dmin + y->dmin : BIG;
  63.     mincost_x = x->dmin + y->dmin;
  64.     mincost_y = y->dmin;
  65.     cost_x = x->dcost + mincost_x;
  66.     cost_y = y->dcost + mincost_y;
  67.     
  68.     mincost_x = mincost_y;
  69.     mincost_y = (mincost_b <= mincost_c) ? mincost_b : mincost_c;
  70.     if (cost_y <= mincost_y) mincost_y = cost_y;
  71.     x->dcost = cost_x - mincost_x;
  72.     y->dcost = cost_y - mincost_y;
  73.     x->dmin  = mincost_x;
  74.     y->dmin  = mincost_y - mincost_x;
  75.     if (a) a->dmin  = mincost_a - mincost_x;
  76.     if (b) b->dmin  = mincost_b - mincost_y;
  77.     if (c) c->dmin  = mincost_c - mincost_y;
  78. }
  79. else {
  80.     // x wurzel des rechten unterbaums (2)
  81.     a=y->left;
  82.     b=x->left;
  83.     c=x->right;
  84.     x->parent=0;
  85.     x->left=y;
  86.     y->parent=x;
  87.     y->right=b;
  88.     if (b) b->parent=y;
  89.     
  90.     x->successor=y->successor;
  91.     y->successor=0;
  92.     
  93.     mincost_a = (a) ? a->dmin + y->dmin : BIG;
  94.     mincost_b = (b) ? b->dmin + x->dmin + y->dmin : BIG;
  95.     mincost_c = (c) ? c->dmin + x->dmin + y->dmin : BIG;
  96.     mincost_x = x->dmin + y->dmin;
  97.     mincost_y = y->dmin;
  98.     cost_x = x->dcost + mincost_x;
  99.     cost_y = y->dcost + mincost_y;
  100.     
  101.     mincost_x = mincost_y;
  102.     mincost_y = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  103.     if (cost_y <= mincost_y) mincost_y = cost_y;
  104.     x->dcost = cost_x - mincost_x;
  105.     y->dcost = cost_y - mincost_y;
  106.     x->dmin  = mincost_x;
  107.     y->dmin  = mincost_y - mincost_x;
  108.     if (a) a->dmin  = mincost_a - mincost_y;
  109.     if (b) b->dmin  = mincost_b - mincost_y;
  110.     if (c) c->dmin  = mincost_c - mincost_x;        
  111. }
  112. continue;
  113.   }
  115.   
  116.   // 2.Fall: x hat also Grossvater, x und parGenPtr(x) linke (rechte)
  117.   //    Soehne.
  118.   // Linke Soehne:
  120.   if ((z->left==y)&&(y->left==x)){   //  (3)
  121. a=x->left;
  122. b=x->right;
  123. c=y->right;
  124. d=z->right;
  125. y->left=b;
  126. if (b) b->parent=y;
  127. z->left=c;
  128. if (c) c->parent=z;
  129. x->right=y;
  130. y->parent=x;
  131. y->right=z;
  132. z->parent=y;
  133. if (zz) {
  134.     if (zz->left==z){
  135.  zz->left=x;
  136.     }
  137.     else{
  138.  zz->right=x;
  139.     }
  140. }
  141. else {  //  z is solid-tree-root
  142.     x->successor=z->successor;
  143.     z->successor=0;
  144. } 
  145. x->parent=zz;
  147. mincost_a = (a) ? a->dmin + x->dmin + y->dmin + z->dmin : BIG;
  148. mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  149. mincost_c = (c) ? c->dmin + y->dmin + z->dmin : BIG;
  150. mincost_d = (d) ? d->dmin + z->dmin : BIG;
  151. mincost_x =  x->dmin + y->dmin + z->dmin;
  152. mincost_y =  y->dmin + z->dmin;
  153. mincost_z =  z->dmin;
  154. cost_x  = mincost_x + x->dcost;
  155. cost_y  = mincost_y + y->dcost;
  156. cost_z  = mincost_z + z->dcost;
  158. mincost_x = mincost_z;
  159. mincost_z = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  160. if (cost_z <= mincost_z) mincost_z = cost_z;
  161. mincost_y = (mincost_b <= mincost_z) ? mincost_b : mincost_z;
  162. if (cost_y <= mincost_y) mincost_y = cost_y;
  163. x->dcost = cost_x - mincost_x;
  164. y->dcost = cost_y - mincost_y;
  165. z->dcost = cost_z - mincost_z;
  166. x->dmin = mincost_x;
  167. y->dmin = mincost_y - mincost_x;
  168. z->dmin = mincost_z - mincost_y;
  169. if (a) a->dmin = mincost_a - mincost_x;
  170. if (b) b->dmin = mincost_b - mincost_y;
  171. if (c) c->dmin = mincost_c - mincost_z;
  172. if (d) d->dmin = mincost_d - mincost_z;
  174. continue;
  175.   }
  177.   
  178.   // Rechte Soehne:   (4)
  179.   
  180.   if ((z->right==y)&&(y->right==x)){
  181. a=z->left;
  182. b=y->left;
  183. c=x->left;
  184. d=x->right;
  185. z->right=b;
  186. if (b) b->parent=z;
  187. z->parent=y;
  188. y->left=z;
  189. y->right=c;
  190. if (c) c->parent=y;
  191. y->parent=x;
  192. x->left=y;
  193. if (zz) {
  194.     if (zz->left==z){
  195.  zz->left=x;
  196.     }
  197.     else{
  198.  zz->right=x;
  199.     }
  200. }
  201. else { 
  202.     x->successor=z->successor;
  203.     z->successor=0;
  204. }
  205. x->parent=zz;
  207. mincost_a = (a) ? a->dmin + z->dmin : BIG;
  208. mincost_b = (b) ? b->dmin + y->dmin + z->dmin : BIG;
  209. mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  210. mincost_d = (d) ? d->dmin + x->dmin + y->dmin + z->dmin : BIG;
  211. mincost_x =  x->dmin + y->dmin + z->dmin;
  212. mincost_y =  y->dmin + z->dmin;
  213. mincost_z =  z->dmin;
  214. cost_x  = mincost_x + x->dcost;
  215. cost_y  = mincost_y + y->dcost;
  216. cost_z  = mincost_z + z->dcost;
  218. mincost_x = mincost_z;
  219. mincost_z = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  220. if (cost_z <= mincost_z) mincost_z = cost_z;
  221. mincost_y = (mincost_c <= mincost_z) ? mincost_c : mincost_z;
  222. if (cost_y <= mincost_y) mincost_y = cost_y;
  223. x->dcost = cost_x - mincost_x;
  224. y->dcost = cost_y - mincost_y;
  225. z->dcost = cost_z - mincost_z;
  226. x->dmin = mincost_x;
  227. y->dmin = mincost_y - mincost_x;
  228. z->dmin = mincost_z - mincost_y;
  229. if (a) a->dmin = mincost_a - mincost_z;
  230. if (b) b->dmin = mincost_b - mincost_z;
  231. if (c) c->dmin = mincost_c - mincost_y;
  232. if (d) d->dmin = mincost_d - mincost_x;
  234. continue;
  235.   }
  236.   
  238.   // 3.Fall: x linkes, p(x) rechtes Kind (oder umgekehrt)
  239.   // Zuerst x links, p(x) rechts:
  240.   
  241.   if ((z->right==y)&&(y->left==x)){   // (5)
  242. a=z->left;
  243. b=x->left;
  244. c=x->right;
  245. d=y->right;
  246. z->right=b;
  247. if (b) b->parent=z;
  248. z->parent=x;
  249. x->left=z;
  250. y->left=c;
  251. if (c) c->parent=y;
  252. y->parent=x;
  253. x->right=y;
  254. if (zz) {
  255.     if (zz->left==z){
  256.  zz->left=x;
  257.     }
  258.     else{
  259.  zz->right=x;
  260.     }
  261. } 
  262. else {
  263.     x->successor=z->successor;
  264.     z->successor=0;
  265. }
  266. x->parent=zz;
  268. mincost_a = (a) ? a->dmin + z->dmin : BIG;
  269. mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  270. mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  271. mincost_d = (d) ? d->dmin + y->dmin + z->dmin : BIG;
  272. mincost_x =  x->dmin + y->dmin + z->dmin;
  273. mincost_y =  y->dmin + z->dmin;
  274. mincost_z =  z->dmin;
  275. cost_x  = mincost_x + x->dcost;
  276. cost_y  = mincost_y + y->dcost;
  277. cost_z  = mincost_z + z->dcost;
  279. mincost_x = mincost_z;
  280. mincost_z = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  281. if (cost_z <= mincost_z) mincost_z = cost_z;
  282. mincost_y = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  283. if (cost_y <= mincost_y) mincost_y = cost_y;
  284. x->dcost = cost_x - mincost_x;
  285. y->dcost = cost_y - mincost_y;
  286. z->dcost = cost_z - mincost_z;
  287. x->dmin = mincost_x;
  288. y->dmin = mincost_y - mincost_x;
  289. z->dmin = mincost_z - mincost_x;
  290. if (a) a->dmin = mincost_a - mincost_z;
  291. if (b) b->dmin = mincost_b - mincost_z;
  292. if (c) c->dmin = mincost_c - mincost_y;
  293. if (d) d->dmin = mincost_d - mincost_y;
  295. continue;
  296.   }
  298.   
  299.   // Nun x rechts, p(x) links:
  300.   
  301.   if ((z->left==y)&&(y->right==x)){ // (6)
  302. a=y->left;
  303. b=x->left;
  304. c=x->right;
  305. d=z->right;
  306. y->right=b;
  307. if (b) b->parent=y;
  308. y->parent=x;
  309. x->left=y;
  310. z->left=c;
  311. if (c) c->parent=z;
  312. z->parent=x;
  313. x->right=z;
  314. if (zz) {
  315.     if (zz->left==z){
  316.  zz->left=x;
  317.     }
  318.     else{
  319.  zz->right=x;
  320.     }
  321. }
  322. else {
  323.     x->successor=z->successor;
  324.     z->successor=0;
  325. }
  326. x->parent=zz;
  328. mincost_a = (a) ? a->dmin + y->dmin + z->dmin : BIG;
  329. mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  330. mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  331. mincost_d = (d) ? d->dmin + z->dmin : BIG;
  332. mincost_x =  x->dmin + y->dmin + z->dmin;
  333. mincost_y =  y->dmin + z->dmin;
  334. mincost_z =  z->dmin;
  335. cost_x  = mincost_x + x->dcost;
  336. cost_y  = mincost_y + y->dcost;
  337. cost_z  = mincost_z + z->dcost;
  339. mincost_x = mincost_z;
  340. mincost_z = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  341. if (cost_z <= mincost_z) mincost_z = cost_z;
  342. mincost_y = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  343. if (cost_y <= mincost_y) mincost_y = cost_y;
  344. x->dcost = cost_x - mincost_x;
  345. y->dcost = cost_y - mincost_y;
  346. z->dcost = cost_z - mincost_z;
  347. x->dmin = mincost_x;
  348. y->dmin = mincost_y - mincost_x;
  349. z->dmin = mincost_z - mincost_x;
  350. if (a) a->dmin = mincost_a - mincost_y;
  351. if (b) b->dmin = mincost_b - mincost_y;
  352. if (c) c->dmin = mincost_c - mincost_z;
  353. if (d) d->dmin = mincost_d - mincost_z;
  355.   }
  356.      }
  357. }
  360. d_vertex dyna_trees::assemble(d_vertex u, d_vertex v, d_vertex w)
  361. {
  362.      double mincost_u,
  363.     mincost_v,
  364.     mincost_w,
  365.     cost_v;
  367.      v->left=u;
  368.      v->right=w;
  369.      if (u) u->parent=v;
  370.      if (w) w->parent=v;
  371.      
  372.      mincost_u = (u) ? u->dmin : BIG;
  373.      mincost_v =       v->dmin;
  374.      mincost_w = (w) ? w->dmin : BIG;
  375.      cost_v = mincost_v + v->dcost;
  376.      
  377.      mincost_v = (mincost_u <= mincost_w) ? mincost_u : mincost_w;
  378.      if (cost_v < mincost_v) mincost_v = cost_v;
  379.      v->dcost = cost_v - mincost_v;
  380.      v->dmin = mincost_v;
  381.      if (u) u->dmin = mincost_u - mincost_v;
  382.      if (w) w->dmin = mincost_w - mincost_v;
  384.      return v;
  385. }
  388. void   dyna_trees::disassemble(d_vertex v, d_vertex& v1, d_vertex& v2) {
  389.      double mincost_v1,
  390.     mincost_v2;
  393.      v1=v->left;
  394.      v2=v->right;
  395.      if (v1) v1->parent=0;
  396.      if (v2) v2->parent=0;
  397.      v->left=0;
  398.      v->right=0;
  400.      mincost_v1 = (v1) ? v1->dmin + v->dmin : BIG;
  401.      mincost_v2 = (v2) ? v2->dmin + v->dmin : BIG;
  403.      if (v1) v1->dmin = mincost_v1;
  404.      if (v2) v2->dmin = mincost_v2;
  405.      
  406.      v->dmin += v->dcost;
  407.      v->dcost = 0;
  408. }
  411. d_vertex dyna_trees::makepath(void* i)
  412. {
  413.      if (first==0) {
  414.   first=last=new d_node(i);
  415.      }
  416.      else {
  417.   last->next=new d_node(i);
  418.   last=last->next;
  419.      }
  420.      return last;
  421. }
  424. d_vertex dyna_trees::findpath(d_vertex v)
  425. {
  426.      splay(v);
  427.      return v;
  428. }
  432. d_vertex dyna_trees::findpathcost(d_path p, double& d)
  433. {
  434.      d_vertex w;
  435.      w=p;
  436.      
  437.      while( !( (w->dcost==0) && ( (w->right==0)||(w->right->dmin>0) ) ) ) {
  438.   if (w->right) {
  439. if (w->right->dmin == 0) {
  440.      w=w->right;
  441. } else {
  442.      if (w->dcost>0) w=w->left;
  443. }  
  444.   }
  445.   else {
  446. if (w->dcost>0) w=w->left;
  447.   }
  448.      }
  449.      splay(w);
  450.      d=w->dmin;
  451.      return w;
  452. }
  456. d_vertex dyna_trees::findtail(d_path p)
  457. {
  458.      d_vertex w;
  459.      w=p;
  460.      
  461.      while(w->right) {
  462.   w=w->right;
  463.      }
  464.      splay(w);
  465.      return w;
  466. }
  470. void dyna_trees::addpathcost(d_path p, double x)
  471. {
  472.      p->dmin += x;
  473. }
  477. d_vertex dyna_trees::join(d_path p, d_path v, d_path q)
  478. {
  479.      return assemble(p, v, q);
  480. }
  484. void dyna_trees::split(d_vertex v, d_vertex& v1, d_vertex& v2)
  485. {
  486.      splay(v);
  487.      disassemble(v, v1, v2);
  488. }
  492. d_path dyna_trees::expose(d_vertex v)
  493. {
  494.      d_path   p,
  495.       q,
  496.       r;
  497.      d_vertex w;
  498.      
  499.      p=0;
  500.      while (v) {
  501.   w=findpath(v)->successor;
  502.   split(v,q,r);
  503.   if (q) q->successor=v;
  504.   p=join(p, v, r);
  505.   v=w;
  506.      }
  507.      p->successor=0;
  508.      return p;
  509. }
  512. d_vertex dyna_trees::maketree(void* i)
  513. {
  514.      copy_inf(i);
  516.      d_vertex v;
  517.      v=makepath(i);
  518.      v->successor=0;
  519.      return v;
  520. }
  523. d_vertex dyna_trees::findroot(d_vertex v)
  524. {
  525.      return findtail(expose(v));
  526. }
  530. d_vertex dyna_trees::findcost(d_vertex v, double& d)
  531. {
  532.      return findpathcost(expose(v),d);
  533. }
  537. void dyna_trees::addcost(d_vertex v, double x)
  538. {
  539.      addpathcost(expose(v),x);
  540. }
  544. void dyna_trees::link(d_vertex v, d_vertex w)
  545. {
  546.      join( (d_vertex) 0, expose(v), expose(w) )->successor=0;
  547. }
  551. void dyna_trees::cut(d_vertex v) 
  552. {
  553.      d_path p,q;
  554.      
  555.      expose(v);
  556.      split(v,p,q);
  557.      v->successor=q->successor=0;
  558. }
  562. dyna_trees::~dyna_trees()
  563. {
  564.      d_node *x, 
  565.     *y;
  566.   
  567.      x=first;
  568.      while(x) {
  569.   y=x->next;
  570.   delete x;
  571.   x=y;
  572.      }
  573. }
  574.