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.
Trees are different, when we talk about graphs in python
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”) |
Undirected graph
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”) |
Directed graph
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”) |
Multigraph
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) |
Directed Acyclic Graph (Tree)
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) |
Hypergraph
Weighted Graph
- Graph with weights on the edges
- Idea for mapping distances between cities on a map
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
# 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() |
Weighted Graph
https://www.youtube.com/watch?v=8vnu_5QRC74
🙂
دیدگاهتان را بنویسید