*     ************************************************************************
            
      subroutine pivot( inarc, pr, thr, rthr, depth, 
     +                  lib,  nsi,  nsj,  nbj,  pi )

*     ************************************************************************

*     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 and the vector PI containing the dual variables
*     are also updated. This last update is a special case of 
*     the linear optimization.

*     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.

*     pi      ( dble )

*       input  : vector containing the dual variables.
*                (Case of linear optimization). 
*       output : this vector is updated.

*     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
      double precision  pi(*)

*     Internal variables

      integer           tnsi, rnbj, idepth, npf,
     +                  nnc, nnr, nlr, nnt, nxtarc, oldarc
      double precision  lambda

*
*     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
      lambda = pi(nsi) - pi(nsj)
      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
      pi(nnc)   = pi(nnc) + lambda
*
*     An unvisited left sucessor remains ?
*     
 102  if( thr(nnc).eq.nlr ) go to 103
      nnc        = thr(nnc)
      pi(nnc)    = pi(nnc) + lambda
      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 right successors.
*
 104  nnc        = nnt
      pi(nnc)    = pi(nnc) + lambda
      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' 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