-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathGraph.py
186 lines (153 loc) · 6.6 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
import DFS
import copy
class Graph(object):
#type of graph: adjacency list
def __init__(self, graph=list(), name = "G"):
self.__graph = graph
self.__graph_copy = copy.deepcopy(graph)
self.__name = name
#for faster access
self.__vertices = self.get_vertices()
self.__edges = self.get_edges(only_once=False)
self.__GRAPH_DEBUG = list()
def isEmpty(self):
return len(self.__graph) == 0
def getElem(self, idx1, idx2):
return self.__graph[idx1][idx2]
def get_vertices_count(self):
return len(self.__graph)
def get_edges_count(self):
cnt = 0
for i in range(0, len(self.__graph)):
cnt += len(self.__graph[i])-1
return cnt/2
def exists_vertex(self, v):
return (v in self.__vertices)
def exists_edge(self, v1, v2):
if not self.exists_vertex(v1):
self.__GRAPH_DEBUG.append("[Graph.exists_edge]: vertex [" + str(v1) + "]")
return False
if not self.exists_vertex(v2):
self.__GRAPH_DEBUG.append("[Graph.exists_edge]: vertex [" + str(v2) + "]")
return False
v1_idx = self.get_vertex_index_by_name(v1)
for i in range(0, len(self.__graph[v1_idx])):
if self.__graph[v1_idx][i] == v2:
return True
def get_vertices(self):
tmp = list()
for i in range(0, len(self.__graph)):
tmp.append(self.__graph[i][0])
return tmp
def get_edges(self, only_once=False):
tmp = list()
for i in range(0, len(self.__graph)):
v1 = self.__graph[i][0]
for j in range(1, len(self.__graph[i])):
v2 = self.__graph[i][j]
if [v1, v2] in tmp or [v2, v1] in tmp:
continue
tmp.append([v1, v2])
return tmp
def get_vertex_index_by_name(self, vertex):
for i in range(0, len(self.__vertices)):
if (self.__vertices[i] == vertex):
return i
self.__GRAPH_DEBUG.append("[Graph.get_vertex_index_by_name]: vertex [" + str(vertex) + "] does not exist")
return -1
def get_vertex_name_by_index(self, index):
if len(self.__vertices) <= index:
self.__GRAPH_DEBUG.append("[Graph.get_vertex_name_by_index]: index out of range")
return ""
return self.__vertices[index]
def add_vertex(self, vertex):
if self.exists_vertex(vertex):
self.__GRAPH_DEBUG.append("[Graph.add_vertex]: vertex [" + str(vertex) + "] still exists")
return False
self.__graph.append(list())
self.__graph[len(self.__graph)-1].append(vertex)
self.__vertices.append(vertex)
return True
def remove_vertex(self, vertex):
if not self.exists_vertex(vertex):
self.__GRAPH_DEBUG.append("[Graph.remove_vertex]: vertex [" + str(vertex) + "] does not exist")
return False
for i in range(0, len(self.__graph)):
if self.__graph[i][0] == vertex:
self.__graph.pop(i)
self.__vertices.pop(i)
break
for i in range(0, len(self.__graph)):
for j in range(1, len(self.__graph[i])):
if self.__graph[i][j] == vertex:
self.__graph[i].pop(j)
break
return True
def delete_vertices(self, to_delete):
for i in to_delete:
self.remove_vertex(i)
def delete_edges(self, to_delete):
for i in range(0, len(to_delete)):
self.remove_edge(to_delete[i][0], to_delete[i][1])
def add_edge(self, v1, v2):
if v1 not in self.__vertices:
self.__GRAPH_DEBUG.append("[Graph.add_edge]: cannot create edge: vertex [" + str(v1) + "] does not exist")
return False
elif v2 not in self.__vertices:
self.__GRAPH_DEBUG.append("[Graph.add_edge]: cannot create edge: vertex [" + str(v2) + "] does not exist")
return False
elif self.exists_edge(v1, v2):
self.__GRAPH_DEBUG.append("[Graph.add_edge]: edge [" + str(v1) + ", " + str(v2) + "] still exists")
return False
else:
for i in range(0, len(self.__graph)):
if(self.__graph[i][0] == v1):
self.__graph[i].append(v2)
break
for i in range(0, len(self.__graph)):
if(self.__graph[i][0] == v2):
self.__graph[i].append(v1)
return True
return True
def remove_edge(self, v1, v2):
if not self.exists_edge(v1, v2):
self.__GRAPH_DEBUG.append("[Graph.remove_edge]: edge [" + str(v1) + ", " + str(v2) + "] does not exist")
for i in range(0, len(self.__graph)):
if self.__graph[i][0] == v1:
for j in range(1, len(self.__graph[i])):
if self.__graph[i][j] == v2:
self.__graph[i].pop(j)
break
break
for i in range(0, len(self.__graph)):
if self.__graph[i][0] == v2:
for j in range(1, len(self.__graph[i])):
if self.__graph[i][j] == v1:
self.__graph[i].pop(j)
break
break
if [v1, v2] in self.__edges:
self.__edges.pop(self.__edges.index([v1,v2]))
return True
def get_incident_edges(self, vertex):
tmp = list()
if (vertex in self.get_vertices()):
for i in range(0, len(self.__graph)):
if (self.__graph[i][0] == vertex):
for j in range(1, len(self.__graph[i])):
tmp.append([self.__graph[i][0], self.__graph[i][j]])
else:
self.__GRAPH_DEBUG.append("[Graph.get_incident_edges]: vertex [" + str(vertex) + "] does not exist")
return []
return tmp
def get_components_DFS(self):
tmp = DFS.DFS(copy.deepcopy(self))
return tmp.DFS_components()
def get_graph_as_list(self):
return self.__graph
def vertices(self):
return self.__vertices
def edges(self):
return self.get_edges()
def graphtype(self):
return "boost_graph_undirected"