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