In this article, we will discuss how to perform different graph operations. Graphs are nonlinear data structures that consist of vertices and edges. They’re used to represent maps between cities, social media connectivity of users, and connectivity of web pages, etc.
Working on Graph Operations
If you have not studied the implementation of a graph, you may consider reading this article on the implementation of graphs in Python. Now without any further ado, let’s get started on the different graph operations here.
1. Display the vertices of a graph when an adjacency list is given
Consider the following example of a graph.
Suppose that we have been given an adjacency list representation of the graph as follows.
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
As we know that the keys of the dictionary representing the adjacency list represent the vertices of the graph, we can display the vertices of the graph by extracting the keys using the keys() method of the dictionary as follows.
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
vertices=set(graph.keys())
print("The vertices of the graph are:")
print(vertices)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
The vertices of the graph are:
{0, 1, 2, 3, 4, 5}
2. Display the edges of a graph when an adjacency list
To display the edges of the graph, we will traverse each vertex (u) in the graph and then we will look at each vertex (v) that is connected to vertex u by traversing the list of adjacent vertices associated with each vertex. For each vertex u and v, we will add an unordered pair (u,v) in the set of edges.
If a vertex v is in the adjacency list of u, u will also be present in the adjacency list of v. Due to this reason, an adjacency list contains each edge twice. Displaying the edges of a graph is a little trickier as we have to display an edge only once.
To display the edges, we will first create an unordered set {u,v} representing an edge connecting vertex u to v. Thereafter, we will make a list E representing the edges that contain each edge {u,v}.
Due to this, if {u,v} is already in our list of edges, {v,u} can be excluded from the set as {v,u} and {u,v} are considered to be the same.
After that, we will convert each pair in E to a tuple representing the edges of the graph. In this way, we can avoid duplicates and represent the edges as follows.
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
E = list()
for u in graph.keys():
for v in graph[u]:
edge = {u, v}
if edge not in E:
E.append(edge)
print("The edges of the graph are:")
print(E)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
The edges of the graph are:
[{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}]
3. Add a vertex to the graph
To add a vertex to the graph, we will simply add another key and an empty list as its associated adjacency list to the dictionary representing the graph as follows.
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
print("The adjacency List representing the graph is:")
print(graph)
# adding vertex '6' to graph
graph.update({6: []})
print("The new vertices of the graph are:")
print(set(graph.keys()))
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
The new vertices of the graph are:
{0, 1, 2, 3, 4, 5, 6}
4. Add an edge to the graph
To add an edge (u,v) to the graph, We will first check if both the edges “u” and “v” are present in the graph or not. If either of them is not present, we will abort the process.
If both the edges “u” and “v” are present in the graph, we will add u to the adjacency list associated with v and then we will add v to the adjacency list associated with u. In this way, It will be specified that u is connected to v and v is connected to u and hence an edge between u and v will be established.
This can be done as follows.
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2],6:[]}
print("The adjacency List representing the graph is:")
print(graph)
# adding edges (5,6) and (4,6) to graph
new_edges = [(5, 6), (4, 6)]
for edge in new_edges:
u=edge[0]
v=edge[1]
graph[u].append(v)
graph[v].append(u)
#display new edges
E = list()
for u in graph.keys():
for v in graph[u]:
edge = {u, v}
if edge not in E:
E.append(edge)
print("The new edges of the graph are:")
print(E)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
The new edges of the graph are:
[{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}, {4, 6}, {5, 6}]
Conclusion
In this article, we have seen how we can perform different operations on a graph like adding a vertex or edge to the graph and displaying the edges and vertices of the graph. Stay tuned for more informative articles.
Happy Learning!