Shortest paths

This notebook illustrates the search for shortest paths in graphs.

[1]:
from IPython.display import SVG
[2]:
import numpy as np
[3]:
from sknetwork.data import miserables, painters, movie_actor
from sknetwork.path import shortest_path
from sknetwork.visualization import svg_graph, svg_digraph, svg_bigraph
from sknetwork.utils import bipartite2undirected

Graphs

[4]:
graph = miserables(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[5]:
napoleon = 1
jondrette = 46
[6]:
path = shortest_path(adjacency, sources=napoleon, targets=jondrette)
[7]:
edge_labels = [(path[k], path[k + 1], 0) for k in range(len(path) - 1)]
[8]:
image = svg_graph(adjacency, position, names, edge_labels=edge_labels, edge_width=3, display_edge_weight=False, scale = 1.5)
[9]:
SVG(image)
[9]:
../../_images/tutorials_path_shortest_path_11_0.svg

Digraphs

[10]:
graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[11]:
klimt = 6
vinci = 9
[12]:
path = shortest_path(adjacency, sources=klimt, targets=vinci)
[13]:
edge_labels = [(path[k], path[k + 1], 0) for k in range(len(path) - 1)]
[14]:
image = svg_digraph(adjacency, position, names, edge_labels=edge_labels, edge_width=2)
[15]:
SVG(image)
[15]:
../../_images/tutorials_path_shortest_path_18_0.svg

Bigraphs

[16]:
graph = movie_actor(metadata=True)
biadjacency = graph.biadjacency
names_row = graph.names_row
names_col = graph.names_col
[17]:
adjacency = bipartite2undirected(biadjacency)
[18]:
n_row, _ = biadjacency.shape
[19]:
seydoux = 9
lewitt = 2
[20]:
path = shortest_path(adjacency, sources=seydoux + n_row, targets=lewitt + n_row)
[21]:
edge_labels = []
labels_row = {}
labels_col = {}
for k in range(len(path) - 1):
    i = path[k]
    j = path[k + 1]
    # row first
    if i > j:
        i, j = j, i
    j -= n_row
    labels_row[i] = 0
    labels_col[j] = 0
    edge_labels.append((i, j, 0))
[22]:
image = svg_bigraph(biadjacency, names_row, names_col, labels_row, labels_col,
                    edge_labels=edge_labels, edge_color='gray', edge_width=3)
[23]:
SVG(image)
[23]:
../../_images/tutorials_path_shortest_path_27_0.svg