-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraph.py
195 lines (172 loc) · 6.32 KB
/
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
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
"""
@version: python3.6
@author: Fieldhunter
@contact: [email protected]
@time: 2020-05-03
"""
import functools
"""
preprocessing operation for adding data in two graph
representation methods, decorator function
"""
def start_end_process(func):
@functools.wraps(func)
def process(self, start, end):
start, end = str(start), str(end)
if start not in self.__mapping:
self.__mapping.append(start)
start_num = len(self.__mapping) - 1
else:
start_num = self.__mapping.index(start)
if end not in self.__mapping:
self.__mapping.append(end)
end_num = len(self.__mapping) - 1
else:
end_num = self.__mapping.index(end)
func(self, start_num, end_num)
return process
"""
Check if the code used to access the graph information,Decorator function.
The purpose of simply adding code is to prevent graph from
being tampered with maliciously and to provide the API for developers.
"""
def check_code(func):
@functools.wraps(func)
def check(self, code):
if code != 'adsf;{h3096j34ka`fd>&/edgb^45:6':
raise Exception('code is wrong!')
result = func(self, code)
return result
return check
# based on directed graph
class Adjacency_matrix():
"""
Initialize to a matrix of 10 * 10
Self.__mapping is used to record the correspondence
between nodes and their ordinal numbers.
"""
def __init__(self):
self.__mapping = []
self.__size = 10
self.__data = []
for _ in range(10):
new_list = []
for _ in range(10):
new_list.append(0)
self.__data.append(new_list)
@start_end_process
def add_data(self, start_num, end_num):
self.__data[start_num][end_num] = 1
"""
If the number of nodes is close to the size of the matrix,
the matrix is expanded.
"""
if self.__size - len(self.__mapping) < 2:
for i in self.__data:
for _ in range(10):
i.append(0)
for _ in range(10):
new_list = []
for _ in range(10):
new_list.append(0)
self.__data.append(new_list)
self.__size += 10
@check_code
def return_basic_information(self, code):
return self.__data, self.__mapping, self.__size
class Adjacency_list():
"""
Self.__mapping is used to record the correspondence between
nodes and their ordinal numbers.
In self.__data, using node ordinal express pointing relation.
"""
def __init__(self):
self.__data = {}
self.__mapping = []
@start_end_process
def add_data(self, start_num, end_num):
if not self.__data.get(start_num, False):
new_list = [end_num]
self.__data[start_num] = new_list
else:
if end_num in self.__data[start_num]:
print("data is in list")
else:
self.__data[start_num].append(end_num)
def BFS(self, start, end):
start, end = str(start), str(end)
if start not in self.__mapping or end not in self.__mapping:
print("No data in need")
else:
"""
The queue array is a queue to store the currently traversed vertices.
The visited array is used to record the visited vertices. It is used to
avoid repeated access of vertices.
The prev array is used to record search path.
"""
start_num, end_num = self.__mapping.index(start), self.__mapping.index(end)
queue = [start_num]
visited = [False] * len(self.__mapping)
prev = [-1] * len(self.__mapping)
find = False
while len(queue) > 0 and find == False:
focus = queue[0]
del queue[0]
visited[focus] = True
if self.__data.get(focus, False):
for i in self.__data[focus]:
if visited[i] != True:
queue.append(i)
prev[i] = focus
if i == end_num:
find = True
break
if find:
pointer = end_num
prev_way = []
while pointer != -1:
prev_way.insert(0, pointer)
pointer = prev[pointer]
print(prev_way)
else:
print("No way from start to end")
def DFS(self, start, end):
def recursion_found(pointer, end_num, visited, prev, find):
if find == True:
return visited, prev, find
if self.__data.get(pointer, False):
for i in self.__data[pointer]:
if find:
break
if visited[i] != True:
visited[i] = True
prev[i] = pointer
if i == end_num:
find = True
break
visited, prev, find = recursion_found(i, end_num, visited, prev, find)
return visited, prev, find
start, end = str(start), str(end)
if start not in self.__mapping or end not in self.__mapping:
print("No data in need")
else:
# visited, prev array has the same function as BFS
start_num, end_num = self.__mapping.index(start), self.__mapping.index(end)
visited = [False] * len(self.__mapping)
prev = [-1] * len(self.__mapping)
find = False
pointer = start_num
visited[start_num] = True
visited, prev, find = recursion_found(pointer, end_num, visited, prev, find)
if find:
index = end_num
prev_way = []
while index != -1:
prev_way.insert(0, index)
index = prev[index]
print(prev_way)
else:
print("No way from start to end")
@check_code
def return_basic_information(self, code):
return self.__data, self.__mapping