* ************************************************************************ subroutine hpivot( inarc, pr, thr, rthr, depth, + lib, nsi, nsj, nbj ) * ************************************************************************ * Purpose : * --------- * This routine updates the four data structures vectors * PR, THR, RTHR and DEPTH, due to the pivoting performed * between the bounding (outgoing) basic arc whose endnodes * are NBJ and PR(NBJ), and the non-bounding (ingoing) * superbasic arc whose endnodes are NSI and NSJ. * The vector LIB containing the indices of the basic * variables is also updated. * We define the pivot's path as the path connecting the * ending node of the ingoing superbasic arc and the ending * node of the outgoing basic arc, such that it does not * include the stem node. * Parameters : * ------------ * inarc ( int ) * input : the indice of the non-bounding (ingoing) * superbasic variable. * output : unmodified. * pr ( int ) * input : the predecessor vector. The value of the ith * component is the predecessor node of node i * in the maximal basis spanning tree. * output : this vector is updated. * thr ( int ) * input : the traversal vector. The value of the ith * component is the traversal node of node i * in the maximal basis spanning tree. * output : this vector is upadated. * rthr ( int ) * input : the reverse vector. The value of the ith * component is the reverse node of node i * in the maximal basis spanning tree. * output : this vector is updated. * depth ( int ) * input : the depth vector. The value of the ith * component is the depth of node i in the * maximal basis spanning tree. * output : this vector is updated. * lib ( int ) * input : this vector contains the indices of the * basic variables composing the maximal * basis spanning tree. The ith component * corresponds to the indice of the basic * arc whose endnodes are i and PR(i). * output : this vector is updated. * nsi ( int ) * input : one of the endnodes of the non-bounding * (ingoing) superbasic arc. * output : unmodified. * nsj ( int ) * input : the other endnode of the non-bounding * (ingoing) superbasic arc. The path * connecting nodes NSJ and NBJ, is called * the pivot's path. * output : unmodified. * nbj ( int ) * input : One of the endnodes of the bounding * (outgoing) basic arc. The other endnode * of this arc is PR(NBJ). * output : unmodified. * Routine used : * -------------- * None. * Programming : * ------------- * D. Tuyttens * Remark : * -------- * This routine follows the ideas given in the paper : * Bradley, Brown and Graves, Design and implementation * of large scale transshipment algorithms. * Management science 27 (1984) 1-34. * ======================================================================== * Routine parameters. integer pr(*), thr(*), rthr(*), depth(*), + inarc, lib(*), nsi, nsj, nbj * Internal variables. integer tnsi, rnbj, idepth, npf, + nnc, nnr, nlr, nnt, nxtarc, oldarc * * Traversal node of NSI in the old basis. * tnsi = thr(nsi) * * Reverse node of NBJ in the old basis. * rnbj = rthr(nbj) * * Set first node to visit on the pivot' path. * nxtarc = inarc npf = nsi nnc = nsi nnr = nsj nlr = thr(nsj) nnt = nlr * * Visit a given node on the pivot' path. * 101 idepth = depth(npf) - depth(nnr) + 1 thr(nnc) = nnr rthr(nnr) = nnc nnc = nnr * * An unvisited left sucessor remains ? * 102 if( thr(nnc).eq.nlr ) go to 103 nnc = thr(nnc) depth(nnc) = depth(nnc) + idepth go to 102 * * An unvisited right sucessor remains ? * 103 if( depth(nnt).le.depth(nnr) ) go to 105 thr(nnc) = nnt rthr(nnt) = nnc * * Visit all the rigth successors. * 104 nnc = nnt depth(nnc) = depth(nnc) + idepth nnt = thr(nnt) if( depth(nnt).gt.depth(nnr) ) go to 104 * * Set next node to visit on the pivot's path. * 105 depth(nnr) = depth(nnr) + idepth nlr = nnr nnr = pr(nlr) pr(nlr) = npf * * We update the vector LIB containing the indices * of the basic variables. * oldarc = lib(nlr) lib(nlr) = nxtarc nxtarc = oldarc * * We test if all the nodes of the pivot' path have * been visited. * if( nlr.ne.nbj )then npf = nlr go to 101 endif * * All the nodes of the pivot's path have been visited. * We link node NNC with TNSI and node NNT with RNBJ. * if( tnsi.eq.nbj )then thr(nnc) = nnt rthr(nnt) = nnc else thr(nnc) = tnsi rthr(tnsi) = nnc thr(rnbj) = nnt rthr(nnt) = rnbj endif * return end