-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGraph.py
More file actions
124 lines (111 loc) · 4.15 KB
/
Copy pathGraph.py
File metadata and controls
124 lines (111 loc) · 4.15 KB
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
# 大于任何float类型的值
inf = float("inf")
class GraphError(SyntaxError):
pass
# 邻接矩阵实现图类
class Graph:
def __init__(self, mat, unconn=inf, vi2vi=0):
"""
:param mat: 初始的邻接矩阵对
:param unconn: 无关联（边）情况的值，默认为inf
:param vi2vi: 给出顶点到自身的默认值，默认为0
"""
vnum = len(mat)
for x in mat:
if len(x) != vnum: #检查是否为方阵
raise ValueError("Argument for 'Graph'.")
self._vnum = vnum
self._out_edges = [0] * vnum #0表示没有计算过
self._vi2vi = vi2vi
self._unconn = unconn
self._mat = [mat[i][:] for i in range(vnum)]
def vertex_num(self):
return self._vnum
def _invalid(self,v):
return 0 > v or v >= self._vnum
def add_vertex(self,row,col):
if len(row) != self._vnum or len(col) != self._vnum: # 检查是否有n个元素
raise ValueError("need list of old-vnum-weights")
for i in range(self._vnum):
self._mat[i].append(col[i])
row1 = row[:]
row1.append(self._vi2vi)
self._mat.append(row1)
self._vnum += 1
self._out_edges.append(0)
def add_edge(self,vi,vj,val=1):
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + "or" + str(vj) +
"is not a valid vertex.")
self._mat[vi][vj] = val
def get_edge(self,vi,vj):
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + "or" + str(vj) +
"is not a valid vertex.")
return self._mat[vi][vj]
def out_edges(self,vi):
if self._invalid(vi):
raise GraphError(str(vi) + "is not a valid vertex.")
if self._out_edges[vi] == 0:
self._out_edges[vi] = self._out_edges_method(self._mat[vi],self._unconn,vi)
return self._out_edges[vi] # 可能重复计算没有邻接边的顶点
@staticmethod
def _out_edges_method(row,unconn,vi):
edges = []
for i in range(len(row)):
if row[i] != unconn and i != vi:
edges.append((i,row[i])) # 边的终点和边的信息
return edges
def __str__(self):
return "[\n" +\
",\n".join(map(str,self._mat)) +\
"\n]" + "\nUnconnected:" + str(self._unconn)
class GraphAL(Graph):
def __init__(self, mat, unconn=inf, vi2vi=0):
vnum = len(mat)
for x in mat:
if len(x) != vnum: #检查是否为方阵
raise ValueError("Argument for 'GraphAL'.")
self._vnum = vnum
self._vi2vi = vi2vi
self._unconn = unconn
self._mat = [Graph._out_edges_method(mat[i],unconn,i)
for i in range(vnum)]
def add_vertex(self,row,col):
self._mat.append([])
vnum = self._vnum
self._vnum += 1
for i in range(vnum):
if col[i] < inf:
self.add_edge(i,vnum,col[i])
if row[i] < inf:
self._mat[vnum].append((i,row[i]))
return self._vnum - 1
def add_edge(self,vi,vj,val=1):
if self._vnum == 0:
raise GraphError("Cannot add edge to empty graph")
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + " or " + str(vj) +
"is not a valid vertex.")
row = self._mat[vi]
i = 0
while i < len(row):
if row[i][0] == vj:
self._mat[vi][i] = (vj,val)
return
if row[i][0] > vj:
break
i += 1
self._mat[vi].insert(i,(vj,val))
def get_edge(self,vi,vj):
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + "or" + str(vj) +
"is not a valid vertex.")
for i, val in self._mat[vi]:
if i == vj:
return val
return self._unconn
def out_edges(self,vi):
if self._invalid(vi):
raise GraphError(str(vi) + "is not a valid vertex.")
return self._mat[vi]