python /networkx 求与根的距离

Question

我有下面的例子

import networkx as nx

data = {
  'modules': {
         'aws_vpc': {
            'deps': []
         },
         'aws_security_group': {
           'deps': ['aws_vpc']
         },
         'aws_subnet': {
            'deps': ['aws_vpc']
         },
         'aws_db_subnet': {
            'deps': ['aws_subnet']
         },
         'aws_db_instance': {
            'deps': ['aws_security_group','aws_db_subnet']
         }
   }
}


G = nx.DiGraph()
roots = set()
for module,data in data['modules'].items():
    if len(data['deps']) == 0:
        roots.add(module)
        continue

    for d in data['deps']:
        G.add_edge(d, module)


for s in roots:
    print s
    spacer = {s: 0}
    for prereq, target in nx.dfs_edges(G, s):
        spacer[target] = spacer[prereq] + 2
        print '{spacer}+-{t}'.format(
                                     spacer=' ' * spacer[prereq],
                                     t=target)
    print ''

现在看起来像

aws_vpc
+-aws_security_group
  +-aws_db_instance
+-aws_subnet
  +-aws_db_subnet

我想做的是从依赖项中找到与根模块的当前距离。例如。 aws_db_instance 取决于 aws_security_group 和 aws_db_subnet。

aws_db_subnet 距离较远，因此应将 aws_db_instance 添加到那里的边缘。我只是想不出一种方法来找到与模块依赖关系的距离。

我知道图形并不总是表现得像树，所以也许我使用了错误的模块，但我的想法是你可以有许多没有任何依赖关系的根。所以我认为 networkx 会很合适。

所以最终结果应该是这样的

aws_vpc
+-aws_security_group
+-aws_subnet
  +-aws_db_subnet
    +-aws_db_instance

Answer 1

nx.shortest_path呢？

distance = len(nx.shortest_path(G, source='aws_vpc', target='aws_subnet'))

python /networkx 求与根的距离

python / networkx find the distance from root

python

networkx