Implement graphs in python like a pro

In this post I will tell you how you can what are graphs, what is the best method to implement them in python, their application and few other algorithms.

So what are graphs anyways..?

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 termed as vertices, and the links that connect the vertices are called edges.

Source: Google

A simple undirected graph

From the above definition it is clear that graphs are a set of vertices that are connected using edges and can be directed or undirected.

So what are the best data structures that we can use to implement graphs in python.

They are none other than dictionaries and lists.

We would be using a combination of both to show a node and their neighbouring vertices.

For eg the representation of above graph would look something just like this -

{
    1:[2,3],
    2:[1,3],
    3:[1,2,4],
    4:[3]
}

As simple as that.

Now coming on how to write a program to implement the same.

Well that’s also very easy the program below implements the above graph using two functions namely add_edge to add edges to the graph and show_graph to show all the edges in the graph.

What the above program does is, it simply implements a class Graph which stores the graphs in a dictionary and displays all the edges in the end.

The output of the graph will be the same as the input we provided it -

( 1 ,  2 )
( 1 ,  3 )
( 2 ,  3 )
( 2 ,  1 )
( 3 ,  1 )
( 3 ,  2 )
( 3 ,  4 )
( 4 ,  3 )

That’s because we have just printed out the information that we stored in the graph. Now let’s play with it a little bit more….

Let’s find the path between two nodes

Just add this function to your existing class to find a path between any two nodes.

And at the end of your file remove the last line and add this line -

print(g.find_path(‘4’, ‘1’))

Finally after running the program you should get the following result -

[‘4’, ‘3’, ‘1’]

So what’s happening here,

Let’s break the code into smaller pieces to understand it more properly.

So first things first, our function takes 3 arguments namely start, end and path. The first two variables, as the name suggests, store the start and end nodes. The third variable stores the current path while the function recursively calls itself to update that path.

Initially the path is set to an empty list and then we append the start node to it, after that we check if start==end , if yes then we return the path i.e. only the start node.

Then comes this -

for node in self.graph_dict[start]:
    if node not in path:
        newPath=self.find_path(node,end,path)
        if newPath:
            return newPath
        return None

This loop traverses all the neighbouring nodes of the start node and then recursively calls itself again until it finds a path from one of the neighbouring nodes to end node, if it finds a path it returns the path.

And remember that it does not return the shortest, it just returns the first path it finds. So as your homework try to find all possible paths and the shortest path. The process would be the same with just a little bit of changes, at the end of this post I will provide a link to my github repository that implements both of them.

Breadth First Search (BFS)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Source : wikipedia

BFS is an important graph algorithm and has many important applications including solving Rubik’s cube, Computing shortest path (Dijkstra’s algorithm) and Ford-Fulkerson’s algorithm computing maximum flow in a flow network.

A simple BFS implementation

The way this algorithm works is that it starts from any node and traverses all nodes at each level. We use queue to implement BFS, by poping nodes from queue, adding the neighbours of that node in the queue and labeling them as visited so that we don’t add the already traversed nodes in the queue again.

So let’s implement a program for the same -

Add this function to your class and replace the last line with g.BFS('1') and you will get the following output-

1 2 3 4

The way this function works is that it creates an empty dictionary visited and mark value of each node as false indicating that they are not visited yet.

Then we create a queue and append the starting node to it and mark it as visited.

The while loop runs until the queue is empty and it-

1. Pops the first node from the queue.
2. Traverses all the neighbouring nodes of of the popped node and if they are not already visited it marks them as visited and pushes them at the end of the queue.
3. Prints the popped node.

That way we find the connected components in the graph using BFS.

Now try practicing these -

• Dijkstra’s shortest path algorithm
• Depth First search
• Floyd Warshall Shortest Path from every vertex to every other vertex
• Prim’s and Kruskal’s minimum spanning tree algorithms

You can find the solution to these problems here on github.

Thanks for reading ;)