-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.py
221 lines (157 loc) · 7.94 KB
/
main.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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
from graph import DoubleDictGraph
class Menu:
def __init__(self):
self.filename = "graph1k.txt"
self.running = True
def exit(self):
self.running = False
def print_graph(self):
for node in self.graph.get_vertices():
line = str(node) + ":"
for neighbour in self.graph.get_outbound_neighbours_of_vertex_X(node):
line += str(neighbour) + " "
print(line)
def print_menu(self):
print("""
1. get the number of vertices;
2. parse (iterate) the set of vertices;
3. given two vertices, find out whether there is an edge from the first one to the second one, and retrieve the Edge_id if there is an edge (the latter is not required if an edge is represented simply as a pair of vertex identifiers);
4. get the in degree and the out degree of a specified vertex;
5. parse (iterate) the set of outbound edges of a specified vertex (that is, provide an iterator). For each outbound edge, the iterator shall provide the Edge_id of the curren edge (or the target vertex, if no Edge_id is used).
6. parse the set of inbound edges of a specified vertex (as above);
7. retrieve or modify the information (the integer) attached to a specified edge.
8. The graph shall be modifiable: it shall be possible to add and remove an edge, and to add and remove a vertex. Think about what should happen with the properties of existing edges and with the identification of remaining vertices. You may use an abstract Vertex_id instead of an int in order to identify vertices; in this case, provide a way of iterating the vertices of the graph.
9. Read the graph from a text file (as an external function); see the format below.
10. Write the graph to a text file (as an external function); see the format below.
11.Create a random graph with specified number of vertices and of edges (as an external function).
12.Get the connected components of the graph.
13. Restart graph
14. Find the lowest cost walks with Floyd-Warshall
0. Exit the program
""")
def clear_screen(self):
print("\n"*100)
def num_of_vertices(self):
print("There are ", self.graph.get_number_of_vertices(), " vertices in the graph.")
def parse_set_of_vertices(self):
for vertex in self.graph.get_vertices():
print(vertex, end=" ")
def is_edge_between_vertices(self):
vertex1 = int(input("Enter the first vertex: "))
vertex2 = int(input("Enter the second vertex: "))
if self.graph.is_edge(vertex1, vertex2):
print("There is an edge between {} and {} with the cost {}".format(vertex1, vertex2, self.graph.retrieve_edge_cost(vertex1, vertex2)))
else:
print("There is no edge between {} and {}!\n".format(vertex1, vertex2))
def in_degree_out_degree(self):
vertex = int(input("Enter the vertex number:"))
degrees = self.graph.get_in_and_out_degree(vertex)
print("The in and out degree of the vertex are {}".format(str(degrees)))
def outbound_edges(self):
vertex = int(input("Specify the vertex: "))
for neighbour in self.graph.get_outbound_neighbours_of_vertex_X(vertex):
print(neighbour, " ")
print("\n")
def inbound_edges(self):
vertex = int(input("Specify the vertex: "))
for neighbour in self.graph.get_inbound_neighbours_of_vertex_X(vertex):
print(neighbour, " ")
print("\n")
def retrieve_modify(self):
first_vertex = int(input("Enter the first vertex of the edge: "))
second_vertex = int(input("Enter the second vertex of the edge: "))
print("1. Retrieve cost of the edge")
print("2. Modify cost of the edge")
option = int(input("Enter option: "))
if option == 1:
try:
print(self.graph.retrieve_edge_cost(first_vertex, second_vertex))
except KeyError as ke:
print("The edge {} does not exist!".format(ke))
else:
try:
new_cost = int(input("Enter the new cost of edge {}: ".format(str((first_vertex, second_vertex)))))
self.graph.modify_edge_cost(first_vertex, second_vertex, new_cost)
except KeyError as ke:
print("The edge {} does not exist!".format(ke))
def add_remove_vertex_edge(self):
self.clear_screen()
print("""
1. Add a new vertex
2. Remove a vertex
3. Add a new edge
4. Remove edge
""")
option = int(input("Enter an option:"))
if option == 1:
new_vertex = int(input("Enter the vertex number:"))
self.graph.add_vertex(new_vertex)
elif option == 2:
removed_vertex = int(input("Enter the vertex number to remove:"))
self.graph.remove_vertex(removed_vertex)
elif option == 3:
first_vertex = int(input("Enter the first vertex:"))
second_vertex = int(input("Enter the second vertex:"))
cost = int(input("Enter the cost:"))
self.graph.add_edge(first_vertex, second_vertex, cost)
elif option == 4:
first_vertex = int(input("Enter the first vertex:"))
second_vertex = int(input("Enter the second vertex:"))
self.graph.remove_edge(first_vertex, second_vertex)
def read_graph(self):
self.filename = input("Enter the input filename of the graph:")
self.graph = DoubleDictGraph.read_graph_from_text_file(self.filename, self._directed)
self.clear_screen()
def write_graph(self):
filename = input("Enter the filename of the output file:")
self.graph.write_graph_to_text_file(filename)
def random_graph(self):
vertices = int(input("Enter the number of vertices:"))
edges = int(input("Enter the number of edges:"))
if edges > vertices * (vertices-1):
print("The number of edges should be max. n*(n-1), where n is the number of vertices. ")
return
self.graph = DoubleDictGraph.create_random_graph(vertices, edges, self._directed)
def get_connected_components(self):
print(self.graph.get_connected_components())
def restart_graph(self):
number_of_nodes = int(input("Enter the number of nodes: "))
self.graph = DoubleDictGraph(number_of_nodes, self._directed)
def fw(self):
self.graph.floyd_warshall()
def main(self):
print("\n\n")
self._directed = True
print("1. Directed")
print("2. Undirected")
option = int(input("Enter an option: "))
if option == 1:
self._directed = True
else:
self._directed = False
self.graph = DoubleDictGraph.read_graph_from_text_file(self.filename, self._directed)
options = [self.exit, self.num_of_vertices, self.parse_set_of_vertices, self.is_edge_between_vertices,
self.in_degree_out_degree, self.outbound_edges, self.inbound_edges, self.retrieve_modify,
self.add_remove_vertex_edge, self.read_graph, self.write_graph, self.random_graph, self.get_connected_components, self.restart_graph,
self.fw]
print("\n\n")
self.clear_screen()
while self.running:
self.print_menu()
"""
try:
option = int(input("Enter an option: "))
self.clear_screen()
options[option]()
except ValueError as ve:
self.clear_screen()
print(ve)
except Exception as e:
print(e)
"""
option = int(input("Enter an option: "))
self.clear_screen()
options[option]()
self.graph.write_graph_to_text_file("result.txt")
menu = Menu()
menu.main()