import numpy as np

ITER = 50	# Iterationen fuer Page Rank

d = 0.95	# damping factor

names = [
    "Mohamed Atta",				# 0
    "Ziad Jarrah",				# 1
    "Marwan Al-Shehhi",				# 2
    "Mamoun Darkazanli",			# 3
    "Zakariya Essabar",				# 4
    "Said Bahaji",				# 5
    "Mounir El Motassadeq",			# 6
    "Zacarias Moussaoui",			# 7
    "Ramzi Bin al-Shibh",			# 8
    "Agus Budiman",				# 9
    "Ahmed Khalil Ibrahim Samir Al-Ani",	# 10
    "Lotfi Raissi",				# 11
    "Salem Alhazmi",				# 12
    "Hani Hanjour",				# 13
    "Rayed Mohammed Abdullah",			# 14
    "Bandar Alhazmi",				# 15
    "Faisal Al Salmi",				# 16
    "Majed Moqed",				# 17
    "Khalid Al-Mihdhar",			# 18
    "Osama Awadallah",				# 19
    "Abdussattar Shaikh",			# 20
    "Nawaf Alhazmi",				# 21
    "Mohamed Abdi",				# 22
    "Ahmed Al Haznawi",				# 23
    "Ahmed Alnami",				# 24
    "Hamza Alghamdi",				# 25
    "Saeed Alghamdi",				# 26
    "Ahmed Alghamdi",				# 27
    "Nabil al-Marabh",				# 28
    "Raed Hijazi",				# 29
    "Mohand Alshehri",				# 30
    "Fayez Ahmed",				# 31
    "Mustafa Ahmed al-Hisawi",			# 32
    "Abdul Aziz Al-Omari",			# 33
    "Waleed Alsheri",				# 34
    "Wail Alsheri",				# 35
    "Satam Suqami"				# 36
]

N = len(names)

links = [
    [ 21, 1, 2, 32, 33, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13 ],	# 0 Mohamed Atta
    [ 12, 23, 2, 4, 5, 0, 8, 9, 11, 13 ],			# 1 Ziad Jarrah
    [ 31, 32, 33, 3, 4, 5, 6, 8, 9, 0, 11, 1, 13, 12 ],		# 2 Marwan Al-Shehhi
    [ 0, 2, 5 ],						# 3 Mamoun Darkazanli
    [ 0, 1, 2, 5, 8 ],						# 4 Zakariya Essabar
    [ 0, 1, 2, 4, 3, 6, 8 ],					# 5 Said Bahaji
    [ 0, 2, 5, 8 ],						# 6 Mounir El Motassadeq
    [ 0, 8 ],							# 7 Zacarias Moussaoui
    [ 0, 1, 2, 4, 5, 6, 7, 9 ],					# 8 Ramzi Bin al-Shibh
    [ 0, 1, 2, 8 ],						# 9 Agus Budiman
    [ 0 ],					# 10 Ahmed Khalil Ibrahim Samir Al-Ani
    [ 0, 1, 2, 13, 14 ],					# 11 Lotfi Raissi
    [ 1, 2, 21 ],						# 12 Salem Alhazmi
    [ 18, 21, 2, 1, 0, 11, 14, 15, 16, 17 ],			# 13 Hani Hanjour
    [ 13, 11, 15, 16 ],					# 14 Rayed Mohammed Abdullah
    [ 13, 14 ],							# 15 Bandar Alhazmi
    [ 13, 14 ],							# 16 Faisal Al Salmi
    [ 13 ],							# 17 Majed Moqed
    [ 20, 21, 13, 19 ], 					# 18 Khalid Al-Mihdhar
    [ 20, 21, 18 ],						# 19 Osama Awadallah
    [ 21, 18, 19 ], 						# 20 Abdussattar Shaikh
    [ 0, 22, 24, 25, 26, 12, 13, 18, 19, 20 ],			# 21 Nawaf Alhazmi
    [ 21 ],							# 22 Mohamed Abdi
    [ 1, 26, 25 ],						# 23 Ahmed Al Haznawi
    [ 26, 25, 21 ],						# 24 Ahmed Alnami
    [ 27, 26, 30, 23, 21, 24 ],					# 25 Hamza Alghamdi
    [ 29, 28, 23, 21, 25, 24 ],					# 26 Saeed Alghamdi
    [ 28, 25 ],							# 27 Ahmed Alghamdi
    [ 36, 29, 26, 27 ],						# 28 Nabil al-Marabh
    [ 36, 28, 26 ],						# 29 Raed Hijazi
    [ 31, 25 ],							# 30 Mohand Alshehri
    [ 32, 2, 30 ],						# 31 Fayez Ahmed
    [ 34, 0, 2, 31 ],					# 32 Mustafa Ahmed al-Hisawi
    [ 34, 0, 2 ],						# 33 Abdul Aziz Al-Omari
    [ 35, 36, 33, 32 ],						# 34 Waleed Alsheri
    [ 36, 34 ],							# 35 Wail Alsheri
    [ 35, 34, 29, 28 ]						# 36 Satam Suqami
]

A = np.zeros((N,N))
for j in range(N):
    for k in range(len(links[j])):
        i = links[j][k]
        A[i][j] = 1.0/len(links[j])

p = np.ones(N) / N

for i in range(ITER):
    q = np.dot(A,p)
    p = (1-d)/N + d * q
	
snames = sorted(zip(p, names), reverse=True)

for pp, name in snames:
    print(f'{name}, {pp * 100}')