All Courses

Graphs in Python

Neha Kumawat

10 months ago

Graphs in Python | insideAIML
Table of Contents
  • What is graph in Python?
  • Basic Operations
              1. Display graph vertices
              2. Display graph edges
              3. Add a vertex
              4. Add an edge
              5. Creating a graph

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 | insideAIML
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']}

1. 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']

2. 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'}]

3. 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']

4. 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'}]
Like the Blog, then Share it with your friends and colleagues to make this AI community stronger. 
To learn more about nuances of Artificial Intelligence, Python Programming, Deep Learning, Data Science and Machine Learning, visit our insideAIML blog page.
Keep Learning. Keep Growing. 

Submit Review