Hey folks! Today, in this tutorial, we are gonna understand what Bipartite graphs are and how to implement them in the python programing language using the networkx library.
Introduction to Bipartite Graph
A Bipartite Graph is a graph whose vertices can be divided into two independent sets – A and B. Every (a, b) means a connection between a node from set A and a node from set B. Here “a” belongs to A and “b” belongs to B.
The nodes in one set cannot be connected to one another; they can only be connected to nodes in the other set.
A bipartite graph can be useful in the modeling of a customer’s purchases, for example. The nodes are divided into two groups in this case: the customers’ partition and the products partition.
Edges indicate that a consumer has purchased a certain product. In this scenario, it seems to reason that items cannot be linked to one another; after all, a product cannot purchase another product.
Implementing Bitpartite Graph in Python
The first step in a program is importing modules/libraries into our code. We would require importing basic networkx along with bipartite from networkx.
import networkx as nx
from networkx.algorithms import bipartite
Next, we will be creating an empty Graph in order to add nodes and edges to it in the later sections.
G = nx.Graph()
The next step is to add nodes with the node attribute “bipartite”. Here, the value of the bipartite attribute determines the class of the node. If its value is 0 then it belongs to first-class and in case its value is 1 it belongs to the second class.
G.add_nodes_from(['A1','A2','A3','A4'], bipartite=0)
G.add_nodes_from(['B1','B2','B3'],bipartite=1)
Next, we will add edges only between nodes of opposite classes. You can add as many edges as you want, for now, we have added a few of them.
G.add_edges_from([('A1', "B3"),('A4', "B1"),('A2', "B2"),('A2', "B3"),('A3', "B1")])
We can also confirm if the graph is bipartite or not using the simple code line mentioned below.
bipartite.is_bipartite(G)
Now, visualize the graph very easily through the code snippet mentioned below.
nx.draw_networkx(G, pos = nx.drawing.layout.bipartite_layout(G, ['A1','A2','A3','A4']), width = 2)
Conclusion
Congratulations! You just learned how to build a bipartite graph using Networkx. Hope you enjoyed it! 😇
Liked the tutorial? In any case, I would recommend you to have a look at the tutorials mentioned below:
- NetworkX Package – Python Graph Library
- Calculating the Distance Between Nodes in an Unweighted Graph
- Graph Operations in Python [With Easy Examples]
- Implementing a Graph in Python
Thank you for taking your time out! Hope you learned something new!! 😄