-
Notifications
You must be signed in to change notification settings - Fork 0
/
pageRank_graph.py
69 lines (65 loc) · 2.25 KB
/
pageRank_graph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#Page Rank
#nodes= [“A”,”B”,”C”,”D”]
#graph of form {“A”:[[incoming edges],[#outgoing edges]]}
from random import randrange
graph={}
nodes=[]
no_vertices=int(input(“Please enter the number of vertices in the graph : “))
for I in range(no_vertices):
print(“Vertex “,I,end=” : “)
nodes.append(input())
for I in nodes:
incoming=[]
print(“”.center(80,”-“))
print(“For vertex “,i)
print(“”.center(80,”*”))
incoming_edges = []
outgoing_edges = []
in_count=int(input(“Please enter the number of incoming edges :”))
out_count = int(input(“Please enter the number of outgoing edges :”))
print(“”.center(80,”*”))
while in_count>0:
val =input(“Please enter the incoming edges of Vertex : “)
while True:
if val not in nodes:
print(“Please enter any node belonging to the graph.........”)
val =input(“Please enter the incoming edges of Vertex : “)
else:
break
incoming_edges.append(val)
in_count = in_count – 1
while out_count>0:
val =input(“Please enter the outgoing edges of Vertex : “)
while True:
if val not in nodes:
print(“Please enter any node belonging to the graph.........”)
val =input(“Please enter the outgoing edges of Vertex : “)
else:
break
outgoing_edges.append(val)
out_count = out_count – 1
print(“”.center(80,”*”))
graph[i]=[]
graph[i].append(incoming_edges)
graph[i].append(outgoing_edges)
print(graph)
#damping factor
d=0.85
pageRank={}
#initiliazing Pank rank to 1 initially
for I in nodes:
pageRank[i] = 1
#randomly choose a starting node to begin with
PRDone=[]
for I in range(no_vertices):
while True:
nodePR = nodes[randrange(0,no_vertices)]
if nodePR not in PRDone:
PRDone.append(nodePR)
break
incomingNodes = graph[nodePR][0]
val_sum=0
for I in incomingNodes:
val_sum = val_sum + pageRank[i]/len(graph[i][1])
pageRank[nodePR] = (1-d) + (d*(val_sum))
print(“Page rank of the vertices is “,pageRank)