networkx - 遍历从节点A到节点A的所有路径，进行运算，求最大值
networkx - traverse all paths from node A to node A, perform operation, and find max value
假设我有一个由以下代码生成的有向图：
G = nx.DiGraph()
G.add_edges_from([('A', 'B'),('B', 'A'), ('C','D'),('G','D')], weight=1)
G.add_edges_from([('D','A'),('D','E'),('B','D'),('D','E')], weight=2)
G.add_edges_from([('B','C'),('E','F')], weight=3)
G.add_edges_from([('C','F')], weight=4)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G.edges(data=True)])
pos=nx.spring_layout(G)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
nx.draw(G,pos, node_size=1500,edge_cmap=plt.cm.Reds)
pylab.show()
初始值为n，起始节点A，同时假设所有节点都有入边和出边，我想遍历A中的每条路径网络并不断将起始 n 除以方向边的值，然后找到最大化 n 的路径，这样我最终会到达节点又是A.
例如，如果 n = 100，这是另一个图的示例路径，我在其中遍历了一些路径并取回了最终值：
n / 2 = 50, 50 / 5 = 10, 10 / 2 = 5, 5 / 0.01 = 500
我的用例尤其具有更大的网络，其中迭代解决方案不可行。有没有一种算法可以近似精确解，同时最小化计算时间？
初始答案 - 基于 nx.simple_cycles
有很多方法可以达到您的要求，但这里有一个建议：
首先，让我将原始图表替换为具有更多循环和另一种布局的图表。
G = nx.DiGraph()
G.add_edges_from([('A', 'B'),('B', 'A'), ('C','D'),('G','D')], weight=50)
G.add_edges_from([('D','B')], weight=1)
G.add_edges_from([('B','C'),('F','E'),('E','A')], weight=2)
G.add_edges_from([('C','F'),('B','G'),('A','G')], weight=3)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G.edges(data=True)])
# improve layout and draw node labels
pos=nx.drawing.layout.circular_layout(G,scale=10)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(G,pos,font_color='white')
nx.draw(G,pos, node_size=1500,edge_cmap=plt.cm.Reds)
现在我们找到 G 中开始和结束于给定感兴趣节点的所有简单循环，并为每个循环计算 n。
# node of interest
inode = 'A'
acycs = [ cyc for cyc in nx.simple_cycles(G) if inode in cyc ]
# for ease of computation we append the first node to the end of each cycle
acycs = [cyc+[cyc[0]] for cyc in acycs]
mcyc = []
maxn = 0
# for each cycle involving node of interest
for cyc in acycs:
n = 100
# group the nodes in the cycle by pairs
for u, v in zip(cyc[:-1], cyc[1:]):
# retrieve the respective edge weigth for the current pair
print(u,v, end=',\t')
div = G.get_edge_data(u,v)['weight']
# calculate and update n
r = n/div
print(f"{n}\t/\t{div}\t=\t{r}")
n=r
print('----------------------------------------------------------------------------')
if n>maxn:
maxn=n
mcyc=cyc
这为我们提供了从 inode='A':
开始的所有循环
[out]:
E A, 100 / 2 = 50.0
A G, 50.0 / 3 = 16.666666666666668
G D, 16.666666666666668 / 50 = 0.33333333333333337
D B, 0.33333333333333337 / 1 = 0.33333333333333337
B C, 0.33333333333333337 / 2 = 0.16666666666666669
C F, 0.16666666666666669 / 3 = 0.05555555555555556
F E, 0.05555555555555556 / 2 = 0.02777777777777778
----------------------------------------------------------------------------
E A, 100 / 2 = 50.0
A B, 50.0 / 50 = 1.0
B C, 1.0 / 2 = 0.5
C F, 0.5 / 3 = 0.16666666666666666
F E, 0.16666666666666666 / 2 = 0.08333333333333333
----------------------------------------------------------------------------
B A, 100 / 50 = 2.0
A G, 2.0 / 3 = 0.6666666666666666
G D, 0.6666666666666666 / 50 = 0.013333333333333332
D B, 0.013333333333333332 / 1 = 0.013333333333333332
----------------------------------------------------------------------------
B A, 100 / 50 = 2.0
A B, 2.0 / 50 = 0.04
----------------------------------------------------------------------------
还有最大化循环n:
print(f"The loop {mcyc} in G maximizes n with {maxn}")
[out]:
The loop ['E', 'A', 'B', 'C', 'F', 'E'] in G maximizes n with 0.08333333333333333
我已经上传了这个笔记本 here 以防您希望克隆它并在本地测试此方法。
非迭代替代方案 - 基于 nx.dijkstra_path
根据您的评论，您所追求的似乎不是 to traverse every path in the network，但如果可能的话，仅遍历 n 最大化路径并计算 nmax。
这只是具有更新权重函数的 Dijkstra 最短路径算法的变体。
但是，nx.Dijkstra_path 在查找循环时遇到问题。 nx.Dijkstra_path('A','A') 产生 A 即使 w(A,A)=math.inf
但是可以使用一个技巧：
- 删除节点
A并引入Ai和Ao
- 将 A 的所有入边替换为
Ai
- 将 A 的所有出边替换为
Ao
- link
Ai 和 Ao 边权重等于 math.inf.
- 计算从
Ao到Ai 的最短路径
我在最初的回答中提供的图表如下所示：
import math
Gp = nx.DiGraph()
Gp.add_edges_from([('Ao', 'B'),('B', 'Ai'), ('C','D'),('G','D')], weight=50)
Gp.add_edges_from([('D','B')], weight=1)
Gp.add_edges_from([('B','C'),('F','E'),('E','Ai')], weight=2)
Gp.add_edges_from([('C','F'),('B','G'),('Ao','G')], weight=3)
# this edge is strictly speaking not needed.
Gp.add_edges_from([('Ai','Ao'),('Ao','Ai')], weight=math.inf)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in Gp.edges(data=True)])
pos=nx.drawing.layout.circular_layout(Gp,scale=10)
pos['Ai'], pos['B'] = pos['B'], pos['Ai']
nx.draw_networkx_edge_labels(Gp,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(Gp,pos,font_color='white')
nx.draw(Gp,pos, node_size=1500,edge_cmap=plt.cm.Reds)
使用 nx.dijkstra_path 我们有：
nmpath = nx.dijkstra_path(Gp,'Ao','Ai')
nmpath
[out]: ['Ao', 'B', 'C', 'F', 'E', 'Ai']
我们可以看到该路径的权重如下：
lennmpath=len(nmpath)
datnmpath=[Gp.get_edge_data(u, nmpath[i+1])['weight'] for u,i in zip(nmpath[:-1], range(lnmpath))]
[out]: [50, 2, 3, 2, 2]
我们可以简单地计算出 nmax:
maxn=100;
for w in datnmpath: maxn/=w
print(maxn)
[out] 0.08333333333333333
我已经更新了 the notebook，因此您可以克隆它并在本地测试此方法。
假设我有一个由以下代码生成的有向图：
G = nx.DiGraph()
G.add_edges_from([('A', 'B'),('B', 'A'), ('C','D'),('G','D')], weight=1)
G.add_edges_from([('D','A'),('D','E'),('B','D'),('D','E')], weight=2)
G.add_edges_from([('B','C'),('E','F')], weight=3)
G.add_edges_from([('C','F')], weight=4)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G.edges(data=True)])
pos=nx.spring_layout(G)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
nx.draw(G,pos, node_size=1500,edge_cmap=plt.cm.Reds)
pylab.show()
初始值为n，起始节点A，同时假设所有节点都有入边和出边，我想遍历A中的每条路径网络并不断将起始 n 除以方向边的值，然后找到最大化 n 的路径，这样我最终会到达节点又是A.
例如，如果 n = 100，这是另一个图的示例路径，我在其中遍历了一些路径并取回了最终值：
n / 2 = 50, 50 / 5 = 10, 10 / 2 = 5, 5 / 0.01 = 500
我的用例尤其具有更大的网络，其中迭代解决方案不可行。有没有一种算法可以近似精确解，同时最小化计算时间？
初始答案 - 基于 nx.simple_cycles
有很多方法可以达到您的要求，但这里有一个建议：
首先，让我将原始图表替换为具有更多循环和另一种布局的图表。
G = nx.DiGraph()
G.add_edges_from([('A', 'B'),('B', 'A'), ('C','D'),('G','D')], weight=50)
G.add_edges_from([('D','B')], weight=1)
G.add_edges_from([('B','C'),('F','E'),('E','A')], weight=2)
G.add_edges_from([('C','F'),('B','G'),('A','G')], weight=3)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G.edges(data=True)])
# improve layout and draw node labels
pos=nx.drawing.layout.circular_layout(G,scale=10)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(G,pos,font_color='white')
nx.draw(G,pos, node_size=1500,edge_cmap=plt.cm.Reds)
现在我们找到 G 中开始和结束于给定感兴趣节点的所有简单循环，并为每个循环计算 n。
# node of interest
inode = 'A'
acycs = [ cyc for cyc in nx.simple_cycles(G) if inode in cyc ]
# for ease of computation we append the first node to the end of each cycle
acycs = [cyc+[cyc[0]] for cyc in acycs]
mcyc = []
maxn = 0
# for each cycle involving node of interest
for cyc in acycs:
n = 100
# group the nodes in the cycle by pairs
for u, v in zip(cyc[:-1], cyc[1:]):
# retrieve the respective edge weigth for the current pair
print(u,v, end=',\t')
div = G.get_edge_data(u,v)['weight']
# calculate and update n
r = n/div
print(f"{n}\t/\t{div}\t=\t{r}")
n=r
print('----------------------------------------------------------------------------')
if n>maxn:
maxn=n
mcyc=cyc
这为我们提供了从 inode='A':
[out]:
E A, 100 / 2 = 50.0
A G, 50.0 / 3 = 16.666666666666668
G D, 16.666666666666668 / 50 = 0.33333333333333337
D B, 0.33333333333333337 / 1 = 0.33333333333333337
B C, 0.33333333333333337 / 2 = 0.16666666666666669
C F, 0.16666666666666669 / 3 = 0.05555555555555556
F E, 0.05555555555555556 / 2 = 0.02777777777777778
----------------------------------------------------------------------------
E A, 100 / 2 = 50.0
A B, 50.0 / 50 = 1.0
B C, 1.0 / 2 = 0.5
C F, 0.5 / 3 = 0.16666666666666666
F E, 0.16666666666666666 / 2 = 0.08333333333333333
----------------------------------------------------------------------------
B A, 100 / 50 = 2.0
A G, 2.0 / 3 = 0.6666666666666666
G D, 0.6666666666666666 / 50 = 0.013333333333333332
D B, 0.013333333333333332 / 1 = 0.013333333333333332
----------------------------------------------------------------------------
B A, 100 / 50 = 2.0
A B, 2.0 / 50 = 0.04
----------------------------------------------------------------------------
还有最大化循环n:
print(f"The loop {mcyc} in G maximizes n with {maxn}")
[out]:
The loop ['E', 'A', 'B', 'C', 'F', 'E'] in G maximizes n with 0.08333333333333333
我已经上传了这个笔记本 here 以防您希望克隆它并在本地测试此方法。
非迭代替代方案 - 基于 nx.dijkstra_path
根据您的评论，您所追求的似乎不是 to traverse every path in the network，但如果可能的话，仅遍历 n 最大化路径并计算 nmax。
这只是具有更新权重函数的 Dijkstra 最短路径算法的变体。
但是，nx.Dijkstra_path 在查找循环时遇到问题。 nx.Dijkstra_path('A','A') 产生 A 即使 w(A,A)=math.inf
但是可以使用一个技巧：
- 删除节点
A并引入Ai和Ao - 将 A 的所有入边替换为
Ai - 将 A 的所有出边替换为
Ao - link
Ai和Ao边权重等于math.inf. - 计算从
Ao到Ai的最短路径
我在最初的回答中提供的图表如下所示：
import math
Gp = nx.DiGraph()
Gp.add_edges_from([('Ao', 'B'),('B', 'Ai'), ('C','D'),('G','D')], weight=50)
Gp.add_edges_from([('D','B')], weight=1)
Gp.add_edges_from([('B','C'),('F','E'),('E','Ai')], weight=2)
Gp.add_edges_from([('C','F'),('B','G'),('Ao','G')], weight=3)
# this edge is strictly speaking not needed.
Gp.add_edges_from([('Ai','Ao'),('Ao','Ai')], weight=math.inf)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in Gp.edges(data=True)])
pos=nx.drawing.layout.circular_layout(Gp,scale=10)
pos['Ai'], pos['B'] = pos['B'], pos['Ai']
nx.draw_networkx_edge_labels(Gp,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(Gp,pos,font_color='white')
nx.draw(Gp,pos, node_size=1500,edge_cmap=plt.cm.Reds)
使用 nx.dijkstra_path 我们有：
nmpath = nx.dijkstra_path(Gp,'Ao','Ai')
nmpath
[out]: ['Ao', 'B', 'C', 'F', 'E', 'Ai']
我们可以看到该路径的权重如下：
lennmpath=len(nmpath)
datnmpath=[Gp.get_edge_data(u, nmpath[i+1])['weight'] for u,i in zip(nmpath[:-1], range(lnmpath))]
[out]: [50, 2, 3, 2, 2]
我们可以简单地计算出 nmax:
maxn=100;
for w in datnmpath: maxn/=w
print(maxn)
[out] 0.08333333333333333
我已经更新了 the notebook，因此您可以克隆它并在本地测试此方法。