You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
97 lines
2.7 KiB
97 lines
2.7 KiB
import matrix
|
|
|
|
|
|
|
|
|
|
class Noderank:
|
|
def __init__(self, source):
|
|
self.node_pos = []
|
|
self.node_cpu = []
|
|
self.node_matrix = []
|
|
self.ranks = {}
|
|
|
|
with open(source) as f:
|
|
for i in f:
|
|
d = i.split(',')
|
|
if len(d) > 1:
|
|
self.node_pos.append([float(d[0]), float(d[1])])
|
|
self.node_cpu.append(float(d[2]))
|
|
a = []
|
|
for j in d[3:]:
|
|
a.append(float(j))
|
|
self.node_matrix.append(a)
|
|
temp = []
|
|
for i in self.node_rank():
|
|
temp.append([len(temp), i[0]])
|
|
temp.sort(key = lambda a: a[1], reverse=True)
|
|
self.ranks = []
|
|
for i in temp:
|
|
self.ranks.append(i[0])
|
|
|
|
def H(self, u):
|
|
return self.node_cpu[u] * sum(self.node_matrix[u])
|
|
|
|
def sum_H(self):
|
|
sum_h = 0.0
|
|
for u in range(len(self.node_matrix)):
|
|
sum_h += self.H(u)
|
|
return sum_h
|
|
|
|
def nbr_H_sum(self, u):
|
|
ret = 0.0
|
|
for i in range(len(self.node_matrix[u])):
|
|
if self.node_matrix[u][i] > 0:
|
|
ret += self.H(i)
|
|
return ret
|
|
|
|
def pf(self, u,v):
|
|
return self.H(v) / self.nbr_H_sum(u)
|
|
|
|
def pj(self, u,v):
|
|
return self.H(v) / self.sum_H()
|
|
|
|
def T(self):
|
|
puj = 0.015
|
|
puf = 0.085
|
|
|
|
|
|
m_pjuv = []
|
|
for i in range(len(self.node_matrix)):
|
|
a = []
|
|
for j in range(len(self.node_matrix[i])):
|
|
a.append(self.pj(i,j))
|
|
m_pjuv.append(a)
|
|
|
|
m_pfuv = []
|
|
for i in range(len(self.node_matrix)):
|
|
a = []
|
|
for j in range(len(self.node_matrix[i])):
|
|
if i == j:
|
|
a.append(0)
|
|
else:
|
|
a.append(self.pf(i,j))
|
|
m_pfuv.append(a)
|
|
T1 = matrix.mm(m_pjuv, matrix.diag(puj, len(self.node_matrix)))
|
|
T2 = matrix.mm(m_pfuv, matrix.diag(puf, len(self.node_matrix)))
|
|
return matrix.ma(T1, T2)
|
|
|
|
def node_rank(self):
|
|
NR = []
|
|
sum_h = self.sum_H()
|
|
for u in range(len(self.node_matrix)):
|
|
NR.append([self.H(u) / sum_h])
|
|
e = 0.0001
|
|
#print("Iterative, e={}".format(e))
|
|
for i in range(50):
|
|
NR_t = matrix.mm(self.T(), NR)
|
|
d = matrix.m_delta(NR_t, NR)
|
|
#print(d)
|
|
NR = NR_t
|
|
if d < e:
|
|
return NR
|
|
print("ERROR: node_rank could not stop after 50 iterations")
|
|
return NR
|
|
|
|
if __name__ == "__main__":
|
|
n = Noderank("DOOAB4.txt")
|
|
print(n.ranks)
|