Introduction to Graphs in Python

Lately, I am reading the book Optimization Algorithms by Alaa Khamis and the chapter 3 – Blind Search Algorithms, has caught my attention. The chapter starts with explaining what graphs are how these are displayed in python and I have decided to make a YT video, presenting the code of the book with Jupyter Notebook.

Why graphs? Because they are everywhere:

• A road map is a graph
• Your social-media friends form a graph
• Tasks in a to-do list, with dependables on each other, can be a graph

With Python we can build and draw these structures in just a few lines of code.

Setup

import shutup
shutup.please()

%matplotlib inline

import pandas as pd
import matplotlib.pyplot as plt
import numpy as np  

import networkx as nx
import hypernetx as hnx

plt.rcParams["figure.figsize"] = (6, 4)

Undirected graph

• Edges have no arrows
• Use it for two‑way streets or mutual friendships.

# Undirected Graph
graph = nx.Graph()
nodes = list(range(5))
graph.add_nodes_from(nodes)
edges = [(0,1),(3,4),(3,0),(3,5),(2,0)]
graph.add_edges_from(edges)
nx.draw_networkx(graph, font_color = "white")

Directed graph

• Arrowheads show direction.
• Good for “A follows B” but not the other way around.

# Directed Graph
digraph = nx.DiGraph()
nodes = list(range(5))
edges = [(0,0),(4,0),(1,0),(3,0),(2,0)]
digraph.add_nodes_from(nodes)
digraph.add_edges_from(edges)
nx.draw_networkx(digraph, font_color = "white")

Multigraph

• Allows two or more edges between the same nodes.
• Think of two train lines that join the same pair of cities.

# Multigraph
multigraph = nx.MultiGraph()
nodes = list(range(5))
edges = [(0,0),(4,0),(1,0),(1,0),(1,0),(1,0),(1,0),(3,0),(2,0)]
multigraph.add_nodes_from(nodes)
multigraph.add_edges_from(edges)

pos = nx.kamada_kawai_layout(multigraph)
ax = plt.gca()

for my_edge in multigraph.edges:
    ax.annotate("", xy=pos[my_edge[0]], xycoords='data', xytext=pos[my_edge[1]], textcoords='data', arrowprops=dict(arrowstyle="-", connectionstyle=f"arc3, rad={0.3*my_edge[2]}"),zorder=1)

nx.draw_networkx_nodes(multigraph, pos)
nx.draw_networkx_labels(multigraph, pos, font_color = "w")

Directed Acyclic Graph (Tree)

• No cycles = no way to loop back.
• Used in task schedulers and Git histories.

# Acyclic Graph (Tree)
acyclic_graph = nx.DiGraph()
nodes = list(range(5))
edges = [(4,0),(1,0),(3,0),(0,2),(2,1)]
acyclic_graph.add_nodes_from(nodes)
acyclic_graph.add_edges_from(edges)

nx.draw_networkx(acyclic_graph, nx.kamada_kawai_layout(acyclic_graph), with_labels= True, font_color = "white")
plt.show()

nx.is_directed_acyclic_graph(acyclic_graph)

Hypergraph

• One “edge” can touch many nodes.
• We simulate it with a bipartite graph: red squares = hyper‑edges.

#Hypergraph
data = {
    "Ivan":("Football","Maths","Dancing"),
    "Peter":("French","Spanish","Dancing"),
    "George":("Dancing","English","Advanced French"),
    "Vitosh":("Maths","Dancing","Spanish","Talking", "YouTube"),
}
H = hnx.Hypergraph(data)
hnx.draw(H)

Weighted Graph

• Graph with weights on the edges
• Idea for mapping distances between cities on a map

# Weighted Graph 
weighted_graph = nx.Graph()
weighted_graph.add_node("Sofia", pos=(0,0))
weighted_graph.add_node("Plovdiv", pos=(0,2))
weighted_graph.add_node("Varna", pos=(2,0))
weighted_graph.add_node("Rousse", pos=(2,2))

weighted_graph.add_weighted_edges_from([("Sofia", "Plovdiv", 200),
                                       ("Sofia","Varna",450),
                                        ("Plovdiv","Rousse",300)])

pos = nx.get_node_attributes(weighted_graph, 'pos')
nx.draw_networkx(weighted_graph, pos, with_labels=True)
nx.draw_networkx_edge_labels(weighted_graph, pos,edge_labels={(u,v):d['weight'] for u,v,d in weighted_graph.edges(data=True)})
plt.show()

# make it more beautiful :)

nx.draw_networkx(weighted_graph, pos, with_labels=False, node_color = 'cyan')
labels = {node: node for node in weighted_graph.nodes()}
node_labels = nx.draw_networkx_labels(weighted_graph, pos, labels=labels,font_size = 12)

offset = .12
node_labels["Sofia"].set_position((pos["Sofia"][0], pos["Sofia"][1] - offset))
node_labels["Varna"].set_position((pos["Varna"][0], pos["Varna"][1] - offset))
node_labels["Plovdiv"].set_position((pos["Plovdiv"][0], pos["Plovdiv"][1] + offset))
node_labels["Rousse"].set_position((pos["Rousse"][0], pos["Rousse"][1] + offset))

nx.draw_networkx_edge_labels(weighted_graph, pos,edge_labels={(u,v):d['weight'] for u,v,d in weighted_graph.edges(data=True)})
plt.show()

• Optimization Algorithms Github link: https://github.com/Optimization-Algorithms-Book/Code-Listings/tree/main/Chapter%203
• VitoshAcademy Github link: https://github.com/Vitosh/Python_personal/tree/master/YouTube/036_Python-introduction-to-graphs

🙂