/
modify.py
129 lines (103 loc) · 3.92 KB
/
modify.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
import copy
from graphic_items import Edge, Node
class Graph:
def __init__(self, nodeList, adjacencyList):
self.nodeList = nodeList
self.adjacencyList = adjacencyList
def addNode(self):
adj = self.adjacencyList
nodes = self.nodeList
newNode = Node(len(nodes))
nodes.append(newNode)
newList = []
adj.append(newList)
def addEdge(self, edge, directed = False):
adj = self.adjacencyList
nodes = self.nodeList
toNode = edge.toNode
fromNode = edge.fromNode
adj[fromNode.key].append(edge)
if(directed == False):
newReverseEdge = Edge(toNode,fromNode)
adj[toNode.key].append(newReverseEdge)
def removeEdge(self, edge, directed = False):
toNode = edge.toNode
fromNode = edge.fromNode
self.removeEdgeFromList(fromNode, toNode)
if(directed == False):
self.removeEdgeFromList(toNode, fromNode)
def removeEdgeFromList(self, fromNode, toNode):
adj = self.adjacencyList[fromNode.key]
newAdj = []
for i in range(len(adj)):
if(adj[i].toNode.key != toNode.key):
newAdj.append(adj[i])
self.adjacencyList[fromNode.key] = newAdj
def removeNode(self, node):
newIndex = [-1 for i in range(len(self.nodeList))]
indexCounter = 0
for i in range(len(self.nodeList)):
if(i != node.key):
newIndex[i] = indexCounter
indexCounter = indexCounter + 1
#create modified adjacency list
adj = []
currentSize = 0
for i in range(len(self.adjacencyList)):
if(i != node.key):
currentSize = currentSize + 1
adj.append([])
for j in range(len(self.adjacencyList[i])):
tempEdge = self.adjacencyList[i][j]
if(tempEdge.toNode.key != node.key):
# modifiedEdge = copy.deepcopy(self.adjacencyList[i][j])
modifiedEdge = Edge(tempEdge.fromNode, tempEdge.toNode, tempEdge.color)
modifiedEdge.fromNode.key = newIndex[modifiedEdge.fromNode.key]
modifiedEdge.toNode.key = newIndex[modifiedEdge.toNode.key]
adj[currentSize - 1].append(modifiedEdge)
#create modified nodeList
nodes = []
for i in range(len(self.nodeList)):
if(self.nodeList[i].key != node.key):
modifiedNode = self.nodeList[i]
modifiedNode = newIndex[modifiedNode.key]
nodes.append(modifiedNode)
self.adjacencyList = adj
self.nodeList = nodes
def printAdjList(self):
for i in range(len(self.adjacencyList)):
print('adj - ' + str(i) + ':', end = ' ')
for j in range(len(self.adjacencyList[i])):
print(self.adjacencyList[i][j].toNode.key,end = ' ')
print()
# def test():
# g = Graph()
# g.addNode() # 1
# # print(len(g.adjacencyList[0]))
# # print(len(g.nodeList))
# g.addNode() # 2
# # print(len(g.nodeList))
# g.addNode() # 3
# g.addNode() # 4
# g.addNode() # 5
# g.addEdge(g.nodeList[0],g.nodeList[1])
# g.addEdge(g.nodeList[1],g.nodeList[2])
# g.addEdge(g.nodeList[1],g.nodeList[3])
# g.addEdge(g.nodeList[4],g.nodeList[2])
# g.addEdge(g.nodeList[3],g.nodeList[2])
# # g.addEdge(g.nodeList[2],g.nodeList[1])
# # print(len(g.nodeList))
# # for i in range(len(g.nodeList)):
# # print(g.nodeList[i].key)
# g.printAdjList()
# print()
# print()
# print()
# g.removeEdge(g.nodeList[1],g.nodeList[0])
# g.printAdjList()
# print()
# print()
# print()
# g.removeEdge(g.nodeList[1],g.nodeList[2])
# g.printAdjList()
# test()