-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.py
94 lines (72 loc) · 2.53 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
""" A Python Class
A simple Python graph class, demonstrating the essential
facts and functionalities of graphs.
"""
class Graph_class(object):
def __init__(self, graph_dict=None):
""" initializes a graph object """
if graph_dict == None:
graph_dict = {}
self.graph_dict = graph_dict
def vertices(self):
""" returns the vertices of a graph """
return list(self.graph_dict.keys())
def edges(self):
""" returns the edges of a graph """
return self.generate_edges()
def add_vertex(self, vertex):
""" If the vertex "vertex" is not in
self.graph_dict, a key "vertex" with an empty
list as a value is added to the dictionary.
"""
if vertex not in self.graph_dict:
self.graph_dict[vertex] = []
def add_edge(self, edge):
""" assumes that edge is of type set, tuple or list;
between two vertices can be multiple edges!
"""
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.graph_dict:
self.graph_dict[vertex1].append(vertex2)
else:
self.graph_dict[vertex1] = [vertex2]
def generate_edges(self):
""" A static method generating the edges of the
graph "graph". Edges are represented as sets
with one (a loop back to the vertex) or two
vertices
"""
edges = []
for vertex in self.graph_dict:
for neighbour in self.graph_dict[vertex]:
if {neighbour, vertex} not in edges:
edges.append({vertex, neighbour})
return edges
if __name__ == "__main__":
g = { "a" : ["d"],
"b" : ["d"],
"c" : ["b", "c", "d", "e"],
"d" : ["a", "c"],
"e" : ["f"],
"f" : []
}
graph = Graph_class(g)
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())
print("Add vertex:")
graph.add_vertex("z")
print("Vertices of graph:")
print(graph.vertices())
print("Add an edge:")
graph.add_edge("a","z")
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())
print('Adding an edge {"x","y"} with new vertices:')
graph.add_edge("x","y")
print("Edges of graph:")
print(graph.edges())