Subversion Repositories wimsdev

!if $wims_read_parm!=slib_header
 !goto proc
!endif

slib_author=Bernadette, Perrin-Riou

slib_example= [1,0,1,0;0,1,1,0;0,2,4,1;0,1,1,1],1,3

!exit

:proc

!distribute item $wims_read_parm into slib_GM,slib_s,slib_t
slib_GM= !declosing $slib_GM
slib_GM=!replace internal ; by $\
$ in $slib_GM
slib_n = !linecnt $slib_GM
slib_bp=100
slib_S=$slib_s

slib_precedent=!values $slib_s for x = 1 to $slib_n

!for slib_j=1 to $slib_n
   slib_L=!line $slib_s of $slib_GM
   !if $slib_j != $slib_s
     slib_u=!item $slib_j of $slib_L
     !if $slib_u=0
        slib_pi = $slib_pi,\infty
     !else
        slib_pi = $slib_pi,$slib_u
     !endif
   !else
     slib_pi = $slib_pi,0
   !endif
!next slib_j
 slib_cor = ($slib_S), ($slib_pi)
 slib_pi = !nonempty items $slib_pi

!for slib_i = 1 to $slib_n
  !if $slib_i != $slib_s
# 1. On trouve un sommet satisfaisant
    !distribute items $[($slib_bp+1)*$slib_n],0,0 into slib_x,slib_y,slib_z
    !for slib_j = 1 to $slib_n
       slib_u = !item $slib_j of $slib_pi
       !if $slib_u notsametext \infty
         !if ($slib_j notitemof $slib_S) and ($slib_u < $slib_x)
           slib_x = $slib_u
           slib_y = $slib_j
         !endif
       !else
         !if ($slib_j notitemof $slib_S) and ($slib_z=0)
           slib_z = $slib_j
         !endif
       !endif
    !next slib_j
    !if $slib_y != 0
        slib_sommet = $slib_y
    !else
        slib_sommet = $slib_z
    !endif

    slib_S = $slib_S,$slib_sommet
# 2. On modifie le vecteur pi
   !for slib_j = 1 to $slib_n
    !if $slib_j != $slib_s
     slib_u = !item $slib_j of $slib_pi
     slib_v = !item $slib_sommet of $slib_pi
     slib_L = !line $slib_sommet of $slib_GM
     slib_w = !item $slib_j of $slib_L
     slib_y = 0
     !if $slib_v notsametext \infty
        !if $slib_u notsametext \infty
          slib_x = $[min($slib_u,$[$slib_v+$slib_w])]
          !if ($slib_w != 0) and ($slib_j notitemof $slib_S)
            slib_y = 1
            !if $slib_x = $[$slib_v+$slib_w]
              slib_precedent = !replace item number $slib_j by $slib_sommet in $slib_precedent
            !endif
          !endif
        !else
          slib_x = $[$slib_v+$slib_w]
          !if ($slib_w != 0) and ($slib_j notitemof $slib_S)
            slib_y = 1
            slib_precedent =  !replace item number $slib_j by $slib_sommet in $slib_precedent
          !endif
        !endif
        !if $slib_y=1
          slib_pi = !replace item number $slib_j by $slib_x in $slib_pi
        !endif
     !endif
     !endif s
   !next slib_j
   slib_cor = $slib_cor, ($slib_S), ($slib_pi)
 !endif s
!next slib_i

path from s to t
 slib_liste = $slib_t
 slib_pit =  !item $slib_t of $slib_pi
!if $slib_pit notsametext \infty
  slib_prec = $slib_t
  !for slib_k = 1 to $slib_pit
    slib_prec = !item $slib_prec of $slib_precedent
    slib_liste =  $slib_prec,$slib_liste
  !next slib_k
!endif

slib_out=$slib_liste