Shortest paths
This notebook illustrates the search for shortest paths in graphs (in number of hops).
[1]:
from IPython.display import SVG
[2]:
import numpy as np
[3]:
from sknetwork.data import miserables, painters, movie_actor
from sknetwork.path import get_shortest_path, get_distances
from sknetwork.visualization import visualize_graph, visualize_bigraph
from sknetwork.utils import bipartite2undirected
Graphs
[4]:
graph = miserables(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[5]:
image = visualize_graph(adjacency, position, names, scale=1.5)
SVG(image)
[5]:
[6]:
# shortest path from Cosette
source = np.flatnonzero(names=='Cosette')
path = get_shortest_path(adjacency, source)
[7]:
path
[7]:
<77x77 sparse matrix of type '<class 'numpy.bool_'>'
with 127 stored elements in Compressed Sparse Row format>
[8]:
# distances (for better visualization)
distances = get_distances(adjacency, source)
[9]:
image = visualize_graph(path, position, names, seeds=[source], scores=-distances, scale=1.5)
SVG(image)
[9]:
Directed graphs
[10]:
graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position
[11]:
image = visualize_graph(adjacency, position, names)
SVG(image)
[11]:
[12]:
# shortest path from Paul Cezanne
source = np.flatnonzero(names=='Paul Cezanne')
path = get_shortest_path(adjacency, source)
[13]:
# distances (for better visualization)
distances = get_distances(adjacency, source)
distances[distances < 0] = 5
[14]:
image = visualize_graph(path, position, names, seeds=[source], scores=-distances)
SVG(image)
[14]:
Bipartite graphs
[15]:
graph = movie_actor(metadata=True)
biadjacency = graph.biadjacency
names_row = graph.names_row
names_col = graph.names_col
[16]:
image = visualize_bigraph(biadjacency, names_row, names_col)
SVG(image)
[16]:
[17]:
# shortest path
source_row = np.flatnonzero(np.isin(names_row, ['Drive', 'The Grand Budapest Hotel']))
path = get_shortest_path(biadjacency, source_row)
[18]:
# distances (for better visualization)
distances = np.hstack(get_distances(biadjacency, source_row=source_row))
[19]:
image = visualize_graph(path, names=np.hstack((names_row, names_col)), seeds=[source_row], scores=-distances, scale=1.5)
SVG(image)
[19]:
