program pagerank_s
  ! Il programma calcola il pagerank data una matrice di link
  ! la matrice sara` contenuta nel file matrice.spa che e`
  ! un file di testo con il seguente formato:
  ! - la prima riga e` fatta da due interi che sono la dimensione della
  !   matrice e il numero di elementi non nulli
  ! - le succesive righe contengono gli indici di riga e di colonna
  !   il cui elemento corrispondente e` non nullo
  implicit none

  type casella
     integer :: i,j
     real(kind(0.d0)) :: valore
  end type casella

  integer :: ios,n,nonnulli,k,h,r,c,maxiter=100
  real(kind(0.d0)),allocatable,dimension(:) :: v,w
  type(casella),allocatable,dimension(:) :: matrice
  character(11) :: filename="matrice.spa"

  open(unit=1,iostat=ios,file=filename,status="old",action="read")
  if (ios/=0) then
     write(*,*) "File inesistente" 
     stop
  endif

  ! Leggo la dimensione della matrice e il numero di elementi non nulli
  ! poi alloco e leggo i singoli elementi
  read(1,*) n,nonnulli

  allocate(matrice(nonnulli))
  do k=1,nonnulli
     read(1,*) matrice(k)%i,matrice(k)%j
     matrice(k)%valore=1.0
  end do
  
!!$  ! Visualizza matrice
!!$  mostramatrice: do k=1,nonnulli
!!$     write(*,'(a,i1,i2,a,f10.6)') "(",matrice(k)%i,matrice(k)%j,")",matrice(k)%valore
!!$  end do mostramatrice

  ! Calcolo la matrice stocastica
  allocate(v(n)) ! v conterra` la somma per riga
  v=0
  sommaperriga: do k=1,nonnulli
     v(matrice(k)%i)=v(matrice(k)%i)+1
  end do sommaperriga
  rendestocastica: do k=1,nonnulli
     matrice(k)%valore=matrice(k)%valore/v(matrice(k)%i)
  end do rendestocastica

  ! Metodo delle potenze
  allocate(w(n))
  v=1
  potenze: do k=1,maxiter

     w=0
     nuovovett : do h=1,nonnulli
        r=matrice(h)%i;c=matrice(h)%j
        w(c)=w(c)+v(r)*matrice(h)%valore
     end do nuovovett
     
     w=w/sum(w)
     if (sum(abs(v-w))<1.d-8) exit
     v=w
  end do potenze

write(*,*) v
end program pagerank_s
