Python Graph
Python Graph: In Computer Science and Mathematics, a Graph is a pictorial representation of a group of objects or elements where some elements are connected using the links. A graph is the network of vertices (also known as nodes) that may or may not be interconnected. These vertices are connected using a path or a line known as an edge. We will be discussing a lot related to the terms used in the Graph and its various functionalities in this section. We will be discovering various things, such as creating a graph and adding several data elements to the Graph using Python programming.
Let’s start with a basic difference between directed and undirected graphs. If the edges in Graph have a specific flow direction, where the direction edge is known as an arc called Graph is directed. At the same time, the Graph with no specified directions is said to be undirected.
Graph plays a significant role in Data Science and it is often practiced in solving real-world problems. Various sectors depend on the Graph and its theories and principles, including molecular studies in chemistry and biology, maps, networks, recommender systems, and a lot.
These are some basic operations we are going to perform on graphs in the following sections.
- Displaying Vertices of the graph.
- Displaying Edges of the graph.
- Adding a Vertex.
- Adding an Edge.
- Creating a Graph.
We can implement a Graph with the help of Python Dictionary data structures. We will represent the graph vertices as the dictionary keys and the edges as the values associated with each key in the dictionary.
Let’s have a look at the graph shown below:
As we can observe in the above graph
Vertices = {p, q, r, s, t}
Edges = {pq, pr, qs, rs, st}
In Python, the above graph can be represented in the syntax, as shown below:
# Creating a dictionary using the graph elements
my_graph = {"p" : ["q","r"],
"q" : ["p", "s"],
"r" : ["p", "s"],
"s" : ["t"],
"t" : ["s"]
}
# Printing the final graph
print("This is my graph: \n", my_graph)
The above snippet of code should produce an Output, as shown below:
This is my graph:
{'p': ['q', 'r'], 'q': ['p', 's'], 'r': ['p', 's'], 's': ['t'], 't': ['s']}
Displaying Vertices of the Graph
We can display the vertices of the graph by finding the keys of the graph dictionary using the keys() method. Let’s have a look at the following example:
class my_graph:
def __init__(self, g_dict = None):
if g_dict is None:
g_dict = []
self.g_dict = g_dict
# Geting the keys of the dictionary
def myVertices(self):
return list(self.g_dict.keys())
# Creating a dictionary using the graph elements
my_graph_elements = {
"p" : ["q","r"],
"q" : ["p", "s"],
"r" : ["p", "s"],
"s" : ["t"],
"t" : ["s"]
}
x = my_graph(my_graph_elements)
print("The Vertices of my graph: \n", x.myVertices())
The above snippet of code should produce an Output, as shown below:
The Vertices of my graph: ['p', 'q', 'r', 's', 't']
Displaying Edges of the Graph
It is slightly hard to find the edges of a graph than to find the vertices because we need to find each of the vertices pairs that hold an edge in between them. Thus, we can build an empty list holding the edges and then we can iterate through the edge values linked with each of the vertices. Then, we will get the complete list holding the different group of edges originated from the vertices. Let's have a look at an example given below:
class my_graph:
def __init__(self, g_dict = None):
if g_dict is None:
g_dict = {}
self.g_dict = g_dict
def my_edges(self):
return self.find_my_edges()
# Finding the distinct list of edges
def find_my_edges(self):
edge_name = []
for vertx in self.g_dict:
for next_vrtx in self.g_dict[vertx]:
if {next_vrtx, vertx} not in edge_name:
edge_name.append({vertx, next_vrtx})
return edge_name
# Creating a dictionary using the graph elements
my_graph_elements = {
"p" : ["q","r"],
"q" : ["p", "s"],
"r" : ["p", "s"],
"s" : ["t"],
"t" : ["s"]
}
x = my_graph(my_graph_elements)
print("The Edges of my graph: \n", x.my_edges())
The above snippet of code should produce an Output, as shown below:
The Edges of my graph:
[{'q', 'p'}, {'p', 'r'}, {'s', 'q'}, {'s', 'r'}, {'s', 't'}]
Inserting a Vertex
We can add a vertex by adding a key to the graph dictionary. Let’s have a look at an example shown below:
class my_graph:
def __init__(self, g_dict = None):
if g_dict is None:
g_dict = {}
self.g_dict = g_dict
def get_Vertices(self):
return list(self.g_dict.keys())
# Adding the vertex as a key
def add_Vertex(self, vertx):
if vertx not in self.g_dict:
self.g_dict[vertx] = []
# Creating a dictionary using the graph elements
my_graph_elements = {
"p" : ["q","r"],
"q" : ["p", "s"],
"r" : ["p", "s"],
"s" : ["t"],
"t" : ["s"]
}
x = my_graph(my_graph_elements)
x.add_Vertex("u")
print("The Vertices of the graph: \n", x.get_Vertices())
The above snippet of code should produce an Output, as shown below:
The Vertices of the graph: ['p', 'q', 'r', 's', 't', 'u']
Inserting an Edge
The process of adding an edge to a current graph involves the following procedure:
- First of all, we need to treat the new vertex as a tuple.
- Then, we need to validate if any edge is already present.
If no edge is present there, we can add one as shown in the following example:
class my_graph:
def __init__(self, g_dict = None):
if g_dict is None:
g_dict = {}
self.g_dict = g_dict
def my_edges(self):
return self.find_edges()
# Adding the new edge
def Add_Edge(self, my_edge):
my_edge = set(my_edge)
(vrtx_a, vrtx_b) = tuple(my_edge)
if vrtx_a in self.g_dict:
self.g_dict[vrtx_a].append(vrtx_b)
else:
self.g_dict[vrtx_a] = [vrtx_b]
# Listing the edge names
def find_edges(self):
edge_name = []
for vertx in self.g_dict:
for next_vrtx in self.g_dict[vertx]:
if {next_vrtx, vertx} not in edge_name:
edge_name.append({vertx, next_vrtx})
return edge_name
# Creating a dictionary using the graph elements
my_graph_elements = {
"p" : ["q","r"],
"q" : ["p", "s"],
"r" : ["p", "s"],
"s" : ["t"],
"t" : ["s"]
}
x = my_graph(my_graph_elements)
x.Add_Edge({'p','t'})
x.Add_Edge({'p','r'})
print("The Edges of my graph: \n", x.my_edges())
The above snippet of code should produce an Output, as shown below:
The Edges of my graph:
[{'q', 'p'}, {'p', 'r'}, {'q', 's'}, {'s', 'r'}, {'t', 's'}, {'t', 'p'}]