Graphs in Python

Neha Kumawat

a year ago

What is graph in Python?

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points known as vertices, and the links that connect the vertices are called edges.
The different terms and functionalities associated with a graph is described in great detail in this article later.
Let’s see how to create a graph and add various data elements to it using a python program.
Some of the basic operations on graphs are as follows:
  • Display graph vertices
  • Display graph edges
  • Add a vertex
  • Add an edge
  • Creating a graph
We can represent a graph in python using dictionary data types. Here the vertices are the keys of the dictionary and the connection between the vertices also known as edges are represented as the values in the dictionary.
Let’s a take graph
Graph
Graph
In the above graph we can see the graph as
Vertices = {a, b, c, d, e}
Edges = {ab, ac, bd, cd, de}
Lets now write a program for this graph
# Create the dictionary with graph elements
graph_data
= { "a" : ["b","c"],

          "b" : ["a",
"d"],

          "c" : ["a",
"d"],

          "d" : ["e"],

          "e" : ["d"]

         }

graph_data
= { "a" : ["b","c"], "b" : ["a","d"], "c" : ["a","d"],"d" : ["e"],"e" : ["d"]}
#
Printing the graph

print(graph_data)
# Printing the graph
print(graph_data)
Output
{'a': ['b', 'c'], 'b': ['a', 'd'], 'c': ['a', 'd'], 'd': ['e'], 'e': ['d']}

How to Display the graph vertices in python?

By using the keys of the graph dictionary, we display the graph vertices. Here we use the keys() method of python dictionary data type.
class
graph:

    def __init__(self,gdict=none):

        if gdict is none:

            gdict = []

        self.gdict = gdict
# Get the keys of the dictionary
    def getVertices(self):

        return list(self.gdict.keys())
# Create the dictionary with graph elements
graph_data
= { "a" : ["b","c"],

                "b" : ["a",
"d"],

                "c" : ["a",
"d"],

                "d" : ["e"],

                "e" : ["d"]

                }

a =
graph(graph_data)

print(a.getVertices())
Output
['a', 'b', 'c', 'd', 'e']

How to Display graph edges in python?

Finding graph edges is a little difficult than the finding of the graph vertices. Here we have to find each of the pairs of vertices which have an edge in between them.

How to do it?

Here, we create an empty list of edges then we run an iteration over the edge’s values associated with each of the vertices. A list is formed containing the distinct group of edges found from the vertices is shown below.
class graph:

   
def __init__(self,gdict=none):

       
if gdict is none:

            gdict = {}

       
self.gdict = gdict

   
def edges(self):

       
return self.findedges()
# Find the distinct list of edges
   
def findedges(self):

       
edgename = []

       
for vrtx in self.gdict:

            for nxtvrtx in self.gdict[vrtx]:

                if {nxtvrtx, vrtx} not in
edgename:

                    edgename.append({vrtx,
nxtvrtx})

       
return edgename
# Creating the dictionary with graph elements
graph_data = { "a" :
["b","c"],

                "b" : ["a",
"d"],

                "c" : ["a",
"d"],

                "d" : ["e"],

                "e" : ["d"]

                }

a = graph(graph_data)

print(a.edges())
Output
[{'b', 'a'}, {'a', 'c'}, {'b', 'd'}, {'d', 'c'}, {'d', 'e'}]

How to Add a vertex in graph?

Adding a vertex is straight forward where we add another additional key to the graph dictionary.
Below an example is shown
class graph:

   
def __init__(self,gdict=none):

       
if gdict is none:

            gdict = {}

       
self.gdict = gdict

   
def getVertices(self):

       
return list(self.gdict.keys())
# Add the vertex as a key
   
def addVertex(self, vrtx):

      
if vrtx not in self.gdict:

            self.gdict[vrtx] = []
# Create the dictionary with graph elements
graph_data = { "a" :
["b","c"],

                "b" : ["a",
"d"],

                "c" : ["a",
"d"],

                "d" :
["e"],

                "e" : ["d"]

                }

a = graph(graph_data)

a.addVertex("f")

print(a.getVertices())
Output
['a', 'b', 'c', 'd', 'e', 'f']

How to Add an edge to a graph?

Adding an edge to an existing graph is done as treating the new vertex as a tuple and validating if the edge is already present. If it is not present then the edge is added.
An example is shown below
class graph:

   
def __init__(self,gdict=none):

     
  if gdict is none:

            gdict = {}

       
self.gdict = gdict

   
def edges(self):

       
return self.findedges()
# Add the new edge
   
def AddEdge(self, edge):

       
edge = set(edge)

       
(vrtx1, vrtx2) = tuple(edge)

       
if vrtx1 in self.gdict:

            self.gdict[vrtx1].append(vrtx2)

       
else:

            self.gdict[vrtx1] = [vrtx2]
# List the edge names
   
def findedges(self):

       
edgename = []

       
for vrtx in self.gdict:

            for nxtvrtx in self.gdict[vrtx]:

                if {nxtvrtx, vrtx} not in
edgename:

                    edgename.append({vrtx,
nxtvrtx})

       
return edgename
# Create the dictionary with graph elements
graph_data = { "a" :
["b","c"],

                "b" : ["a",
"d"],

                "c" : ["a",
"d"],

                "d" :
["e"],

                "e" : ["d"]

                }

a = graph(graph_data)

a.AddEdge({'a','e'})

a.AddEdge({'a','c'})

print(a.edges())
Output
[{'b', 'a'}, {'a', 'c'}, {'a', 'e'}, {'b', 'd'}, {'d', 'c'}, {'d', 'e'}]
For more blogs/courses on data science, machine learning, artificial intelligence, and new technologies do visit us at InsideAIML.
Thanks for reading…  

Submit Review

We're Online!

Chat now for any query