breadth first traversal python program

1class Graph:
2    def __init__(self):
3        # dictionary containing keys that map to the corresponding vertex object
4        self.vertices = {}
5 
6    def add_vertex(self, key):
7        """Add a vertex with the given key to the graph."""
8        vertex = Vertex(key)
9        self.vertices[key] = vertex
10 
11    def get_vertex(self, key):
12        """Return vertex object with the corresponding key."""
13        return self.vertices[key]
14 
15    def __contains__(self, key):
16        return key in self.vertices
17 
18    def add_edge(self, src_key, dest_key, weight=1):
19        """Add edge from src_key to dest_key with given weight."""
20        self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
21 
22    def does_edge_exist(self, src_key, dest_key):
23        """Return True if there is an edge from src_key to dest_key."""
24        return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
25 
26    def __iter__(self):
27        return iter(self.vertices.values())
28 
29 
30class Vertex:
31    def __init__(self, key):
32        self.key = key
33        self.points_to = {}
34 
35    def get_key(self):
36        """Return key corresponding to this vertex object."""
37        return self.key
38 
39    def add_neighbour(self, dest, weight):
40        """Make this vertex point to dest with given edge weight."""
41        self.points_to[dest] = weight
42 
43    def get_neighbours(self):
44        """Return all vertices pointed to by this vertex."""
45        return self.points_to.keys()
46 
47    def get_weight(self, dest):
48        """Get weight of edge from this vertex to dest."""
49        return self.points_to[dest]
50 
51    def does_it_point_to(self, dest):
52        """Return True if this vertex points to dest."""
53        return dest in self.points_to
54 
55 
56class Queue:
57    def __init__(self):
58        self.items = []
59 
60    def is_empty(self):
61        return self.items == []
62 
63    def enqueue(self, data):
64        self.items.append(data)
65 
66    def dequeue(self):
67        return self.items.pop(0)
68 
69 
70def display_bfs(vertex):
71    """Display BFS Traversal starting at vertex."""
72    visited = set()
73    q = Queue()
74    q.enqueue(vertex)
75    visited.add(vertex)
76    while not q.is_empty():
77        current = q.dequeue()
78        print(current.get_key(), end=' ')
79        for dest in current.get_neighbours():
80            if dest not in visited:
81                visited.add(dest)
82                q.enqueue(dest)
83 
84 
85g = Graph()
86print('Menu')
87print('add vertex <key>')
88print('add edge <src> <dest>')
89print('bfs <vertex key>')
90print('display')
91print('quit')
92 
93while True:
94    do = input('What would you like to do? ').split()
95 
96    operation = do[0]
97    if operation == 'add':
98        suboperation = do[1]
99        if suboperation == 'vertex':
100            key = int(do[2])
101            if key not in g:
102                g.add_vertex(key)
103            else:
104                print('Vertex already exists.')
105        elif suboperation == 'edge':
106            src = int(do[2])
107            dest = int(do[3])
108            if src not in g:
109                print('Vertex {} does not exist.'.format(src))
110            elif dest not in g:
111                print('Vertex {} does not exist.'.format(dest))
112            else:
113                if not g.does_edge_exist(src, dest):
114                    g.add_edge(src, dest)
115                else:
116                    print('Edge already exists.')
117 
118    elif operation == 'bfs':
119        key = int(do[1])
120        print('Breadth-first Traversal: ', end='')
121        vertex = g.get_vertex(key)
122        display_bfs(vertex)
123        print()
124 
125    elif operation == 'display':
126        print('Vertices: ', end='')
127        for v in g:
128            print(v.get_key(), end=' ')
129        print()
130 
131        print('Edges: ')
132        for v in g:
133            for dest in v.get_neighbours():
134                w = v.get_weight(dest)
135                print('(src={}, dest={}, weight={}) '.format(v.get_key(),
136                                                             dest.get_key(), w))
137        print()
138 
139    elif operation == 'quit':
140        break