Python for Beginners: Graph Operations in Python

A graph is a non linear data structure used to represent connections between different objects. Generally, graphs are used to represent maps, network, and social media connections. In this article, we will study how to perform different graph operations in Python. We will take a graph and will use it as a running example to perform all the graph operations.

What are different graph operations?

A graph is generally provided in the form of an adjacency list. If we talk about operations on the, there may be the following graph operations. 

• Print all the vertices of the graph
• Print all the edges of the graph
• Insert a vertex into the graph
• Insert an edge into the graph

We will perform all these graph operations in python. For this, we will use the graph given in the following image.

Graph in Python

Before performing the graph operations, we will construct an adjacency list representation of the above graph as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Graph representation in python is:")
print(graph)

Output:

Graph representation in python is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}

How to print all the vertices of a graph

From the previous post on graphs in python, we know that the vertices of the graph are represented using the keys of the adjacency matrix (which is a python dictionary). Hence, we can print all the vertices of the graph by simply printing the keys of the adjacency matrix. For this, we will use the keys() method of a python dictionary as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Graph representation in python is:")
print(graph)
vertices= list(graph.keys())
print("Vertices in the graph are:",vertices)

Output:

Graph representation in python is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Vertices in the graph are: ['A', 'D', 'B', 'F', 'C', 'E']

How to print all the edges of the graph

We know that edges are represented in the graph by using a list associated with each vertex. Every vertex stores a list of vertices with which it is connected.  We will traverse through each vertex v1 and create an edge (v1,v2 ) for each vertex present in the list associated with v1. 

Remember that while printing the edges, there will be repetitions because whenever a vertex v2 is present in the list associated with v1, v1 will also be present in the list associated with v2. Hence, while printing the edges, both (v1,v2) and (v2,v1) will be printed which introduces redundancy as (v1,v2) and (v2,v1) both represent the same edge.

To overcome this problem, we will store any edge (v1, v2) as an unordered set. In this way, (v1, v2) will be the same as (v2,v1). After that, we will create a list of edges. Before inserting any new edge to the list, we will first check if the edge is present in the list or not. If any edge is already present in the list, we will not insert any duplicate edge. 

The above process can be implemented in python as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Graph representation in python is:")
print(graph)
edges = []
for vertex in graph:
    for adjacent_vertex in graph[vertex]:
        edge = {vertex, adjacent_vertex}
        if edge not in edges:
            edges.append(edge)

print("Edges in the graph are:", edges)

Output:

Graph representation in python is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Edges in the graph are: [{'B', 'A'}, {'A', 'D'}, {'A', 'E'}, {'A', 'F'}, {'B', 'F'}, {'B', 'C'}]

 How to insert a vertex into the graph

We know that a vertex is represented using keys of the adjacency list. To insert a vertex into the graph, we will insert the vertex as a key into the graph with an empty list  as its associated value. The empty list represents that the current vertex is not connected to any other vertex. We can implement it as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Original Graph representation is:")
print(graph)
# insert vertex G
graph["G"] = []
print("The new graph after inserting vertex G is:")
print(graph)

Output:

Original Graph representation is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
The new graph after inserting vertex G is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': []}

How to insert an edge into the graph

Inserting an edge into the graph is much simpler than printing the edges. We know that each vertex contains a list of vertices to which it is connected. So, to insert an edge (v1,v2), we will simply insert the vertex v1 to the list of vertices associated with v2 and v2 to the list of vertices associated with the vertex v1. 

In this way, It will be established that v1 is connected to v2 and v2 is connected to v1. Hence, the vertex (v1,v2) will be added in the graph. We can implement it as follows.

graph ={'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': []}
print("Original Graph representation is:")
print(graph)
# insert vertex (D,G)
graph["D"].append("G")
graph["G"].append("D")
print("The new graph after inserting edge (D,G) is:")
print(graph)

Output:

Original Graph representation is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': []}
The new graph after inserting edge (D,G) is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A', 'G'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A'], 'G': ['D']}

Conclusion

In this article, we have implemented different graph operations in python. To know more about other data structures, you can read this article on Linked list in python.

The post Graph Operations in Python appeared first on PythonForBeginners.com.

from Planet Python
via read more