最短路径

此笔记本演示了在图中搜索最短路径（以跳数表示）。

[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

图

[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]:

../../_images/tutorials_path_shortest_path_7_0.svg

[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]:

../../_images/tutorials_path_shortest_path_11_0.svg

有向图

[10]:

graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position

[11]:

image = visualize_graph(adjacency, position, names)
SVG(image)

[11]:

../../_images/tutorials_path_shortest_path_14_0.svg

[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]:

../../_images/tutorials_path_shortest_path_17_0.svg

二部图

[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]:

../../_images/tutorials_path_shortest_path_20_0.svg

[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]:

../../_images/tutorials_path_shortest_path_23_0.svg