بایگانی‌های Graphs

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)

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

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

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

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)

# 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

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

# 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

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

🙂

Source link

برچسب: Graphs

Introduction to Graphs in Python – Useful code

Setup

Undirected graph

Directed graph

Multigraph

Directed Acyclic Graph (Tree)

Hypergraph

Weighted Graph