11 r=(order*)calloc(1,
sizeof(order));
12 if (!r) ExitProc(OutOfSpc,info);
17 ierr=iAlloc(nn0,info,&r->adjn);
if(ierr)
return 1;
18 ierr=iAlloc(nnod,info,&r->rbeg);
if(ierr)
return 1;
19 ierr=iAlloc(nnod,info,&r->rexs);
if(ierr)
return 1;
20 ierr=iAlloc(nnod,info,&r->rlen);
if(ierr)
return 1;
21 ierr=iAlloc(nnod,info,&r->rend);
if(ierr)
return 1;
22 ierr=iAlloc(nnod,info,&r->pres);
if(ierr)
return 1;
23 ierr=iAlloc(nnod,info,&r->succ);
if(ierr)
return 1;
28 void OdFree(order **od)
46 void OdInit(order *od,
57 for(i=1; i<od->nnod; ++i) {
62 od->rbeg[i]=od->rbeg[i-1]+od->rlen[i-1];
68 od->raft=od->rbeg[n-1]+nnzi[n-1];
71 ExitProc(OutOfSpc,
"InitMmd");
75 static void OdSet(order *od,
87 int i,n,deg,*rbeg,*rexs,*rend;
110 if (!allow_eli||deg) {
123 void OdIndex(order *od,
128 od->adjn[od->rbeg[i]++]=j;
129 od->adjn[od->rbeg[j]++]=i;
133 static void OdArriv(order *od,
143 int *visited,i,n,y,z,l,s,t,f,stopt,
144 stops,*adjn,*rbeg,*rexs,*rend;
160 for(t=rbeg[x], stopt=rbeg[x]+rend[x]; t<stopt; ++t) {
163 if (node_status[y]!=0) {
168 for(s=rbeg[y], stops=rbeg[y]+rexs[y]; s<stops; ++s) {
171 if (node_status[z]!=0) {
184 for(t=f, stopt=rbeg[x]+rexs[x]; t<stopt; ++t) {
199 iZero(*rsze,visited,rchset);
200 iZero(n-l,visited,rchset+l);
204 *xdeg = *rsze+isize[x];
205 for(i=0; i<*rsze; ++i)
206 *xdeg+=isize[rchset[i]];
210 static void OdRenew(order *od,
223 for(c=x; ilink[c]!=n; c=ilink[c]) {
230 static void OdCheck(order *od,
233 int f,i,t,stopt,rnew,z,previous,n,*adjn,
234 *rbeg,*rexs,*rlen,*rend,*pres,*succ;
247 for(i=od->head; i!=n; i=succ[i]) {
248 if (node_status[i]!=0) {
251 for(t=rbeg[i], stopt=rbeg[i]+rend[i]; t<stopt; ++t) {
253 if (node_status[z]==3)
259 for(stopt=rbeg[i]+rexs[i]; t<stopt; ++t) {
261 if (node_status[z]!=0)
285 od->raft=rbeg[previous]+rexs[previous];
291 static void OdAdd(order *od,
296 int n,*adjn,*rbeg,*rexs,*rlen,*pres,*succ;
309 if (od->raft+newsze>od->nn0)
310 OdCheck(od,node_status);
312 if (od->raft+newsze>od->nn0)
313 ExitProc(OutOfSpc,
"OdAdd");
316 rlen[pres[x]]+=rlen[x];
318 iCopy(rexs[x],adjn+rbeg[x],adjn+od->raft);
334 succ[pres[x]]=succ[x];
338 pres[succ[x]]=pres[x];
349 static int OdComb(order *od,
358 int i,n,rnew,rlen,x,icur;
369 for(i=1; i<xsize; ++i)
370 rlen+=1+isize[xset[i]];
375 for(icur=rnew; ilink[icur]!=n; icur=ilink[icur]);
378 for(i=1; i<xsize; ++i) {
386 for(icur=x; ilink[icur]!=n; icur=ilink[icur]);
395 static int OdSelect(order *od,
412 int absorp,old,i,j,n,esze,y,z,l,f,t,stopt,s,
413 o,stops,indsze,xdeg,e0,ssze,*slist,tsze,
414 *tlist,sze,*adjn,*rbeg,*rexs,*rlen,*rend;
425 OdArriv(od,node_status,marker,isize,x,&xdeg,rsze,&esze,rchset);
429 OdRenew(od,ilink,x,xdeg,e,p);
431 for(i=n-esze; i<n; ++i) {
432 node_status[rchset[i]]=0;
433 marker[rchset[i]]=TRUE;
437 iSet(*rsze,TRUE,marker,rchset);
443 if (node_status[y]==0||node_status[y]==3)
444 ExitProc(SysError,NULL);
447 for(t=f, stopt=f+rend[y]; t<stopt; ++t) {
449 if (node_status[z]==3) {
460 for(stopt=rbeg[y]+rexs[y]; t<stopt; ++t) {
469 OdRenew(od,ilink,y,xdeg-(*e-e0),e,p);
474 iSwap(i,*rsze,rchset);
478 if (rexs[y]>=rlen[y])
479 ExitProc(SysError,NULL);
482 adjn[rbeg[y]+rexs[y]]=adjn[rbeg[y]+rend[y]];
486 adjn[rbeg[y]+rend[y]]=x;
493 iSet(ssze,FALSE,mask2,slist);
506 OdAdd(od,node_status,x,*rsze);
509 iCopy(*rsze,rchset,adjn+rbeg[x]);
513 for(i=0; i<ssze; ++i){
524 for(t=f, stopt=f+rexs[y]; t<stopt; ++t) {
526 if (node_status[z]!=0) {
534 for(s=rbeg[z],stops=rbeg[z]+rexs[z];
535 s<stops &&marker[adjn[s]]; ++s);
539 iSwap(l,indsze,slist);
555 z=OdComb(od,node_status,marker,
557 n-indsze,slist+indsze);
562 for(j=l; j<indsze; ++j) {
568 osize[z]=max(osize[z],sze);
577 iSet(tsze,FALSE,mask2,tlist);
580 marker[x]=(node_status[x]==0);
582 for(t=0; t<*rsze; ++t) {
584 marker[z]=(node_status[z]==0);
590 static int OdOrder(order *od,
599 OdArriv(od,node_status,marker,isize,
600 x,°,&rsze,&esze,ibuf1);
605 static void OdModf(order *od,
618 for(i=0; i<rsze; ++i) {
620 if (node_status[x]==2)
621 if (node_status[oinfo[x]]==0||node_status[oinfo[x]]==3)
624 if (node_status[x]==1) {
625 deg=OdOrder(od,node_status,marker,isize,x,ibuf1);
626 XtPut(elist,x,deg-isize[x]);
634 void OdProc(order *od,
650 int *mask2,total_fillin,use_mtmd=TRUE,*marker=bbuf1,
651 *node_status,i,n,e,x,y,rsze,deg,mindeg,xsize,sze,
652 j,*isize,*ilink,*oinfo,*osize,*rchset,*dependent,
669 OdSet(od,TRUE,elist,node_status,marker,
670 isize,ilink,oinfo,osize,&e,p);
674 iSet(n,0,dependent,NULL);
677 for(; e<n && !total_fillin;) {
681 if (!XtGet(elist,&y,&mindeg)) {
682 printf(
"\n No new nodes e=%d n=%d",e,n);
683 printf(
" Node status: ");
686 if (node_status[i]==1)
688 else if (node_status[i]==2)
689 printf(
"\n O%d: rlen=%d oinfo=%d\n",
690 i,isize[i],oinfo[i]);
692 ExitProc(SysError,NULL);
697 if (!XtGet(elist,&x,°)||deg>mindeg)
700 if (node_status[x]!=1)
707 total_fillin = OdSelect(od,elist,node_status,marker,
708 isize,ilink,oinfo,osize,x,
709 &rsze,rchset,ibuf8,ibuf9,mask2,
716 for(i=0; i<rsze; ++i) {
725 if (!use_mtmd)
break;
732 for(j=0; j<xsize; ++j) {
734 if (dependent[y]==1 && node_status[y]!=0)
739 OdModf(od,elist,node_status,marker,
740 isize,oinfo,sze,slist,ibuf8);
748 if (node_status[i]==2||node_status[i]==1)
751 x = OdComb(od,node_status,marker,isize,ilink,osize,
754 OdRenew(od,ilink,x,n-e-1,&e,p);
759 int GetOrder(order *od,
762 int ierr=0,bbufs=2,*bbuf[2]={0},
763 ibufs=9,*ibuf[9]={0},
769 ierr=XtAlloc(n,n+1,
"xt, GetOrder",&xt);
if(ierr)
return FALSE;
770 ierr=iAlloc(n,
"ibuf21, GetOrder",&iwmd);
if(ierr)
return FALSE;
772 IptAlloc(ibufs,n,ibuf,
"ibuf, GetOrder");
773 IptAlloc(bbufs,n,bbuf,
"bbuf, GetOrder");
775 OdProc(od,xt,ibuf[0],ibuf[1],ibuf[2],ibuf[3],ibuf[4],ibuf[5],
776 ibuf[6],ibuf[7],ibuf[8],iwmd,bbuf[0],bbuf[1],p);