1

对于更有经验的程序员来说，这可能很容易解决，但我真的找不到解决方案。

我有一个 networkx DiGraph（在 Python w/flask 中），其中包含作为节点的元组和带有权重的边。

我想提取从开始节点到结束节点的所有路径的树，以及它们的权重。这基本上是 all_simple_paths()，但带有权重，并将它们以 JSON 格式导出为一棵树，具有一个根（起始节点）和所有（简单）路径，直到结束节点。

解决方案（除其他外）我查看了：

  • all_simple_paths() 忽略权重，还没有生成树；
  • bfs_tree() 似乎很接近，但忽略了权重，我可以不添加任何端节点（也许没有重复节点？）
  • 我认为带有 [d|b]fs_successors() 的递归函数可以完成这项工作，但我不知道如何构建它。

任何有关如何执行此操作的提示将不胜感激。:)

4

1 回答 1

2

这个问题需要一些特殊性，但这里尝试用节点的元组构造一些虚拟数据，提取任意路径，并转储为 JSON 格式。

设置一些虚拟数据

from random import seed, random, shuffle
seed(11405)

u = [('a','b','c'), ('d','e','f'), ('g','h','i'), 
     ('j','k','l'), ('m','n','o'), ('p','q','r'), 
     ('s','t','u'), ('v','w','x'), ('y','z','a')]
shuffle(u)
v = [('a','b','c'), ('d','e','f'), ('g','h','i'), 
     ('j','k','l'), ('m','n','o'), ('p','q','r'), 
     ('s','t','u'), ('v','w','x'), ('y','z','a')]
shuffle(v)
edges = [ (s,t, {'weight': random()}) for s,t in zip(u,v) if s != t]

创建图表

import networkx as nx
from networkx.readwrite import json_graph

G = nx.DiGraph()
G.add_edges_from(edges)

# Extract a Path between Two Arbitrary Nodes
u = ('m', 'n', 'o')
v = ('a', 'b', 'c')
paths = list(nx.all_simple_paths(G, u,v))
path = paths[0]

# Extract the Subgraph of G using the Selected Nodes
H = G.subgraph(path)

# Output to JSON in Node-Link Format
print json_graph.node_link_data(H)

结果

另请参阅其他 JSON 导出格式的文档。

{'directed': True, 
 'graph': [], 
 'nodes': [{'id': ('g', 'h', 'i')}, 
           {'id': ('p', 'q', 'r')}, 
           {'id': ('a', 'b', 'c')}, 
           {'id': ('m', 'n', 'o')}, 
           {'id': ('v', 'w', 'x')}], 
 'links': [{'source': 0, 'target': 1, 'weight': 0.5156976823289995}, 
           {'source': 1, 'target': 4, 'weight': 0.7392883299553644}, 
           {'source': 3, 'target': 0, 'weight': 0.2109456825712841}, 
           {'source': 4, 'target': 2, 'weight': 0.8368736026881095}], 
 'multigraph': False}
于 2013-08-31T11:52:48.250 回答