python - 动画化网络图以显示算法的进度

我想给网络图制作动画以显示算法的进度。我正在使用NetworkX进行图形创建。

在this SO answer中，我想出了一个使用clear_ouput中的IPython.display和命令plt.pause()来管理动画速度的解决方案。这对于带有几个节点的小型图效果很好，但是当我在10x10网格上实现时，动画非常慢，减少plt.pause()中的参数似乎对动画速度没有任何影响。这是带有Dijkstra算法实现的MME，在该算法中，每次算法迭代时我都会更新节点的颜色:

import math
import queue
import random
import networkx as nx
import matplotlib.pyplot as plt
from IPython.display import clear_output
%matplotlib inline

# plotting function
def get_fig(G,current,pred):
    nColorList = []
    for i in G.nodes():
        if i == current: nColorList.append('red')
        elif i==pred: nColorList.append('white')
        elif i==N: nColorList.append('grey')
        elif node_visited[i]==1:nColorList.append('dodgerblue')
        else: nColorList.append('powderblue')
    plt.figure(figsize=(10,10))
    nx.draw_networkx(G,pos,node_color=nColorList,width=2,node_size=400,font_size=10)
    plt.axis('off')
    plt.show()

# graph creation
G=nx.DiGraph()
pos={}
cost={}
for i in range(100):
    x= i % 10
    y= math.floor(i/10)
    pos[i]=(x,y)
    if i % 10 != 9 and i+1 < 100:
       cost[(i,i+1)] = random.randint(0,9)
       cost[(i+1,i)] = random.randint(0,9)
    if i+10 < 100:
       cost[(i,i+10)] = random.randint(0,9)
       cost[(i+10,i)] = random.randint(0,9)
G.add_edges_from(cost)

# algorithm initialization
lab={}
path={}
node_visited={}
N = random.randint(0,99)
SE = queue.PriorityQueue()
SE.put((0,N))
for i in G.nodes():
    if i == N: lab[i] = 0
    else: lab[i] = 9999
    path[i] = None
    node_visited[i] = 0

# algorithm main loop
while not SE.empty():
    (l,j) = SE.get()
    if node_visited[j]==1: continue
    node_visited[j] = 1
    for i in G.predecessors(j):
        insert_in_SE = 0
        if lab[i] > cost[(i,j)] + lab[j]:
            lab[i] = cost[(i,j)] + lab[j]
            path[i] = j
            SE.put((lab[i],i))
        clear_output(wait=True)
        get_fig(G,j,i)
        plt.pause(0.0001)
print('end')

理想情况下，我希望在不超过5秒的时间内显示整个动画，而目前需要几分钟才能完成算法，这表明plt.pause(0.0001)不能按预期工作。

在阅读了关于图动画的SO帖子(post 2和post 3)之后，似乎可以使用matplotlib的animation模块来解决此问题，但是我无法在算法中成功实现答案。第2部分中的答案建议使用matplotlib中的FuncAnimation，但我正在努力使update方法适应我的问题，而第3部分中的答案导致了一个具有类似建议的不错的教程。

我的问题是如何解决问题的动画速度:是否可以安排clear_output和plt.pause()命令以更快地进行动画制作，还是应该使用matplotlib中的FuncAnimation？如果是后者，那么我应该如何定义update函数？

感谢您的帮助。

编辑1

import math
import queue
import random
import networkx as nx
import matplotlib.pyplot as plt

# plotting function
def get_fig(G,current,pred):
    for i in G.nodes():
        if i==current: G.node[i]['draw'].set_color('red')
        elif i==pred: G.node[i]['draw'].set_color('white')
        elif i==N: G.node[i]['draw'].set_color('grey')
        elif node_visited[i]==1: G.node[i]['draw'].set_color('dodgerblue')
        else: G.node[i]['draw'].set_color('powderblue')

# graph creation
G=nx.DiGraph()
pos={}
cost={}
for i in range(100):
    x= i % 10
    y= math.floor(i/10)
    pos[i]=(x,y)
    if i % 10 != 9 and i+1 < 100:
        cost[(i,i+1)] = random.randint(0,9)
        cost[(i+1,i)] = random.randint(0,9)
    if i+10 < 100:
        cost[(i,i+10)] = random.randint(0,9)
        cost[(i+10,i)] = random.randint(0,9)
G.add_edges_from(cost)

# algorithm initialization
plt.figure(1, figsize=(10,10))
lab={}
path={}
node_visited={}
N = random.randint(0,99)
SE = queue.PriorityQueue()
SE.put((0,N))
for i in G.nodes():
    if i == N: lab[i] = 0
    else: lab[i] = 9999
    path[i] = None
    node_visited[i] = 0
    G.node[i]['draw'] = nx.draw_networkx_nodes(G,pos,nodelist=[i],node_size=400,alpha=1,with_labels=True,node_color='powderblue')
for i,j in G.edges():
    G[i][j]['draw']=nx.draw_networkx_edges(G,pos,edgelist=[(i,j)],width=2)

plt.ion()
plt.draw()
plt.show()

# algorithm main loop
while not SE.empty():
    (l,j) = SE.get()
    if node_visited[j]==1: continue
    node_visited[j] = 1
    for i in G.predecessors(j):
        insert_in_SE = 0
        if lab[i] > cost[(i,j)] + lab[j]:
            lab[i] = cost[(i,j)] + lab[j]
            path[i] = j
            SE.put((lab[i],i))
        get_fig(G,j,i)
        plt.draw()
        plt.pause(0.00001)
plt.close()

编辑2

import math
import queue
import random
import networkx as nx
import matplotlib.pyplot as plt

# graph creation
G=nx.DiGraph()
pos={}
cost={}
for i in range(100):
    x= i % 10
    y= math.floor(i/10)
    pos[i]=(x,y)
    if i % 10 != 9 and i+1 < 100:
        cost[(i,i+1)] = random.randint(0,9)
        cost[(i+1,i)] = random.randint(0,9)
    if i+10 < 100:
        cost[(i,i+10)] = random.randint(0,9)
        cost[(i+10,i)] = random.randint(0,9)
G.add_edges_from(cost)

# algorithm initialization
lab={}
path={}
node_visited={}
N = random.randint(0,99)
SE = queue.PriorityQueue()
SE.put((0,N))
cf = plt.figure(1, figsize=(10,10))
ax = cf.add_axes((0,0,1,1))
for i in G.nodes():
    if i == N:
        lab[i] = 0
        G.node[i]['draw'] = nx.draw_networkx_nodes(G,pos,nodelist=[i],node_size=400,alpha=1.0,node_color='grey')
    else:
        lab[i] = 9999
        G.node[i]['draw'] = nx.draw_networkx_nodes(G,pos,nodelist=[i],node_size=400,alpha=0.2,node_color='dodgerblue')
    path[i] = None
    node_visited[i] = 0
for i,j in G.edges():
    G[i][j]['draw']=nx.draw_networkx_edges(G,pos,edgelist=[(i,j)],width=3,alpha=0.2,arrows=False)

plt.ion()
plt.show()
ax = plt.gca()
canvas = ax.figure.canvas
background = canvas.copy_from_bbox(ax.bbox)

# algorithm main loop
while not SE.empty():
    (l,j) = SE.get()
    if node_visited[j]==1: continue
    node_visited[j] = 1
    if j!=N:
        G.node[j]['draw'].set_color('r')
    for i in G.predecessors(j):
        insert_in_SE = 0
        if lab[i] > cost[(i,j)] + lab[j]:
            lab[i] = cost[(i,j)] + lab[j]
            path[i] = j
            SE.put((lab[i],i))
        if i!=N:
            G.node[i]['draw'].set_alpha(0.7)
            G[i][j]['draw'].set_alpha(1.0)
        ax.draw_artist(G[i][j]['draw'])
        ax.draw_artist(G.node[i]['draw'])
        ax.draw_artist(G.node[j]['draw'])
        canvas.blit(ax.bbox)
        plt.pause(0.0001)
plt.close()

最佳答案

如果图形不太大，则可以尝试以下方法来设置各个节点和边的属性。诀窍是保存绘图函数的输出，该输出使您可以处理诸如颜色，透明度和可见性之类的对象属性。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.cycle_graph(12)
pos = nx.spring_layout(G)

cf = plt.figure(1, figsize=(8,8))
ax = cf.add_axes((0,0,1,1))

for n in G:
    G.node[n]['draw'] = nx.draw_networkx_nodes(G,pos,nodelist=[n], with_labels=False,node_size=200,alpha=0.5,node_color='r')
for u,v in G.edges():
    G[u][v]['draw']=nx.draw_networkx_edges(G,pos,edgelist=[(u,v)],alpha=0.5,arrows=False,width=5)

plt.ion()
plt.draw()

sp = nx.shortest_path(G,0,6)
edges = zip(sp[:-1],sp[1:])

for u,v in edges:
    plt.pause(1)
    G.node[u]['draw'].set_color('r')
    G.node[v]['draw'].set_color('r')
    G[u][v]['draw'].set_alpha(1.0)
    G[u][v]['draw'].set_color('r')
    plt.draw()

编辑

这是一个使用graphviz进行布局的10x10网格示例。
整个过程在我的机器上运行大约1秒钟。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.grid_2d_graph(10,10)
pos = nx.graphviz_layout(G)

cf = plt.figure(1, figsize=(8,8))
ax = cf.add_axes((0,0,1,1))

for n in G:
    G.node[n]['draw'] = nx.draw_networkx_nodes(G,pos,nodelist=[n], with_labels=False,node_size=200,alpha=0.5,node_color='k')
for u,v in G.edges():
    G[u][v]['draw']=nx.draw_networkx_edges(G,pos,edgelist=[(u,v)],alpha=0.5,arrows=False,width=5)

plt.ion()
plt.draw()
plt.show()
sp = nx.shortest_path(G,(0,0),(9,9))
edges = zip(sp[:-1],sp[1:])

for u,v in edges:
    G.node[u]['draw'].set_color('r')
    G.node[v]['draw'].set_color('r')
    G[u][v]['draw'].set_alpha(1.0)
    G[u][v]['draw'].set_color('r')
    plt.draw()

编辑2

这是另一种更快的方法(不重绘轴或所有节点)，并使用广度优先搜索算法。这个程序在我的机器上运行大约2秒钟。我注意到某些后端速度更快-我正在使用GTKAgg。

import networkx as nx
import matplotlib.pyplot as plt

def single_source_shortest_path(G,source):
    ax = plt.gca()
    canvas = ax.figure.canvas
    background = canvas.copy_from_bbox(ax.bbox)
    level=0                  # the current level
    nextlevel={source:1}       # list of nodes to check at next level
    paths={source:[source]}  # paths dictionary  (paths to key from source)
    G.node[source]['draw'].set_color('r')
    G.node[source]['draw'].set_alpha('1.0')
    while nextlevel:
        thislevel=nextlevel
        nextlevel={}
        for v in thislevel:
#            canvas.restore_region(background)
            s = G.node[v]['draw']
            s.set_color('r')
            s.set_alpha('1.0')
            for w in G[v]:
                if w not in paths:
                    n = G.node[w]['draw']
                    n.set_color('r')
                    n.set_alpha('1.0')
                    e = G[v][w]['draw']
                    e.set_alpha(1.0)
                    e.set_color('k')
                    ax.draw_artist(e)
                    ax.draw_artist(n)
                    ax.draw_artist(s)
                    paths[w]=paths[v]+[w]
                    nextlevel[w]=1
                    canvas.blit(ax.bbox)
        level=level+1
    return paths



if __name__=='__main__':

    G = nx.grid_2d_graph(10,10)
    pos = nx.graphviz_layout(G)
    cf = plt.figure(1, figsize=(8,8))
    ax = cf.add_axes((0,0,1,1))

    for n in G:
        G.node[n]['draw'] = nx.draw_networkx_nodes(G,pos,nodelist=[n], with_labels=False,node_size=200,alpha=0.2,node_color='k')
    for u,v in G.edges():
        G[u][v]['draw']=nx.draw_networkx_edges(G,pos,edgelist=[(u,v)],alpha=0.5,arrows=False,width=5)
    plt.ion()
    plt.show()

    path = single_source_shortest_path(G,source=(0,0))