This is a Python program to implement a graph.
The program creates a Graph data structure and allows the user to add vertices and edges to it.
1. Create a class Graph.
2. Create a class Vertex.
3. Each object of Vertex has two instance variables, key and points_to.
4. key is the value of the Vertex object.
5. points_to is a dictionary with keys being the Vertex objects that the current object points to. Each such Vertex object pointed to by the current object is mapped to the weight of the corresponding directed edge.
6. The class Vertex provides methods to get the key, to add a neighbour, to get all neighbours, to get the weight of a directed edge and to test whether a vertex is a neigbour of the current Vertex object.
7. The class Graph has one instance variable, vertices.
8. vertices is a dictionary that contains vertex values mapped to their corresponding Vertex objects. Each Vertex object also stores the vertex value in its key instance variable.
9. The class Graph provides methods to add a vertex with a given key, get the Vertex object with a given key, test whether a vertex with a given key is in the Graph, add an edge between two vertices given their keys and weight and test whether an edge exists between two vertices given their keys. The __iter__ method is implemented to allow iteration over the Vertex objects in the graph.
10. If whenever edge (u, v) is added to the graph, the reverse edge (v, u) is also added, then this would become the implementation of an undirected graph.
Here is the source code of a Python program to implement a graph. The program output is shown below.
class Graph: def __init__(self): # dictionary containing keys that map to the corresponding vertex object self.vertices = {} def add_vertex(self, key): """Add a vertex with the given key to the graph.""" vertex = Vertex(key) self.vertices[key] = vertex def get_vertex(self, key): """Return vertex object with the corresponding key.""" return self.vertices[key] def __contains__(self, key): return key in self.vertices def add_edge(self, src_key, dest_key, weight=1): """Add edge from src_key to dest_key with given weight.""" self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight) def does_edge_exist(self, src_key, dest_key): """Return True if there is an edge from src_key to dest_key.""" return self.vertices[src_key].does_it_point_to(self.vertices[dest_key]) def __iter__(self): return iter(self.vertices.values()) class Vertex: def __init__(self, key): self.key = key self.points_to = {} def get_key(self): """Return key corresponding to this vertex object.""" return self.key def add_neighbour(self, dest, weight): """Make this vertex point to dest with given edge weight.""" self.points_to[dest] = weight def get_neighbours(self): """Return all vertices pointed to by this vertex.""" return self.points_to.keys() def get_weight(self, dest): """Get weight of edge from this vertex to dest.""" return self.points_to[dest] def does_it_point_to(self, dest): """Return True if this vertex points to dest.""" return dest in self.points_to g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest> [weight]') print('display') print('quit') while True: do = input('What would you like to do? ').split() operation = do[0] if operation == 'add': suboperation = do[1] if suboperation == 'vertex': key = int(do[2]) if key not in g: g.add_vertex(key) else: print('Vertex already exists.') elif suboperation == 'edge': src = int(do[2]) dest = int(do[3]) if src not in g: print('Vertex {} does not exist.'.format(src)) elif dest not in g: print('Vertex {} does not exist.'.format(dest)) else: if not g.does_edge_exist(src, dest): if len(do) == 5: weight = int(do[4]) g.add_edge(src, dest, weight) else: g.add_edge(src, dest) else: print('Edge already exists.') elif operation == 'display': print('Vertices: ', end='') for v in g: print(v.get_key(), end=' ') print() print('Edges: ') for v in g: for dest in v.get_neighbours(): w = v.get_weight(dest) print('(src={}, dest={}, weight={}) '.format(v.get_key(), dest.get_key(), w)) print() elif operation == 'quit': break
1. An instance of Graph is created.
2. The user is presented with a menu to perform various operations on the graph.
3. The corresponding methods are called to perform each operation.
4. The operations are: add vertex with a given key, add edge from a source vertex to a destination vertex (optionally with weight specified, otherwise weight=1 is assumed) and to display the all vertices and edges in the graph.
Case 1: Menu add vertex <key> add edge <src> <dest> [weight] display quit What would you like to do? add vertex 1 What would you like to do? add vertex 2 What would you like to do? display Vertices: 1 2 Edges: What would you like to do? add edge 1 2 What would you like to do? add vertex 3 What would you like to do? display Vertices: 1 2 3 Edges: (src=1, dest=2, weight=1) What would you like to do? add edge 1 3 What would you like to do? add edge 3 1 What would you like to do? display Vertices: 1 2 3 Edges: (src=1, dest=2, weight=1) (src=1, dest=3, weight=1) (src=3, dest=1, weight=1) What would you like to do? quit Case 2: Menu add vertex <key> add edge <src> <dest> [weight] display quit What would you like to do? add vertex 1 What would you like to do? add vertex 2 What would you like to do? add vertex 3 What would you like to do? add vertex 4 What would you like to do? add vertex 5 What would you like to do? add edge 1 2 What would you like to do? add edge 2 3 What would you like to do? add edge 4 5 What would you like to do? display Vertices: 1 2 3 4 5 Edges: (src=1, dest=2, weight=1) (src=2, dest=3, weight=1) (src=4, dest=5, weight=1) What would you like to do? add edge 5 4 What would you like to do? display Vertices: 1 2 3 4 5 Edges: (src=1, dest=2, weight=1) (src=2, dest=3, weight=1) (src=4, dest=5, weight=1) (src=5, dest=4, weight=1) What would you like to do? quit
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.
- Check Python Books
- Practice Programming MCQs
- Apply for Programming Internship
- Check Information Technology Books
- Apply for Python Internship
