Algorithm/diameter_distance.py at master · ghostwolfs/Algorithm · GitHub

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import numpy as np
import time
from functools import wraps

def timethis(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.perf_counter()
        r = func(*args, **kwargs)
        end = time.perf_counter()
        print('{} {}: {}'.format(func.__name__, ' cost', end - start))
        return r
    return wrapper

# initiate network data
with open('/Users/baozi/Desktop/complex network/ARPA.txt', 'r') as f:
	line_list = f.readlines()

node = []
links = len(line_list)
for line in line_list:
	line = line.rstrip().split(' ')
	# initiate node list
	if int(line[0]) not in node:
		node.append(int(line[0]))
	if int(line[1]) not in node:
		node.append(int(line[1]))

# node.sort()
node_lenth = max(node)
# print(node_lenth)

@timethis
def diameter_floyd():
	links_matrix = np.full((node_lenth, node_lenth), 1000)
	links_matrix.astype(np.int64)
	for line in line_list:
		line = line.rstrip().split(' ')
		node_one = int(line[0]) - 1
		node_two = int(line[1]) - 1
		links_matrix[node_one][node_two] = 1
		links_matrix[node_two][node_one] = 1

	for index in range(node_lenth):
		links_matrix[index][index] = 0

	# print(links_matrix)
	# print(links_matrix[13][15])
	''' Floyd '''

	distance_matrix = np.copy(links_matrix)
	for k in range(0, node_lenth):
		for i in range(0, node_lenth):
			for j in range(0, node_lenth):
				distance_matrix[i][j] = min(distance_matrix[i][j], distance_matrix[i][k]+distance_matrix[k][j])

	diameter = 0
	for i in range(node_lenth):
		for j in range(node_lenth):
			if distance_matrix[i][j] > diameter and distance_matrix[i][j] != 1000:
				diameter = distance_matrix[i][j]

	print('the diameter computed by floyd algorthim: ', diameter)
diameter_floyd()

@timethis
def diameter_korder():
	links_matrix = np.full((node_lenth, node_lenth), 0)
	links_matrix.astype(np.int8)
	for line in line_list:
		line = line.rstrip().split(' ')
		node_one = int(line[0]) - 1
		node_two = int(line[1]) - 1
		links_matrix[node_one][node_two] = 1
		links_matrix[node_two][node_one] = 1

	for index in range(node_lenth):
		links_matrix[index][index] = 0

	distance_matrix = np.copy(links_matrix) # C1
	k_distance_matrix = np.copy(links_matrix) # D
	temp_matrix = np.copy(links_matrix) # C2
	# print(k_distance_matrix)

	for k in range(1, node_lenth+1):
		temp_matrix = temp_matrix.dot(distance_matrix)
		current_matrix = np.zeros((node_lenth, node_lenth), dtype=np.int64)
		for i in range(0, node_lenth):
			for j in range(0, node_lenth):
				if k_distance_matrix[i][j] > 0:
					current_matrix[i][j] = k_distance_matrix[i][j]
				elif (k_distance_matrix[i][j] == 0) and (temp_matrix[i][j] > 0) and (i != j):
					current_matrix[i][j] = k+1

		# print(k_distance_matrix)
		# print(temp_matrix)
		# print(current_matrix)
		if (current_matrix == k_distance_matrix).all():
			print('the daimeter computed by k-order-distance matrix: ',k)
			break
		else:
			del k_distance_matrix
			k_distance_matrix = np.copy(current_matrix)
diameter_korder()


# print(distance_matrix)