networkx是否提供最大深度（或嵌套深度）？

Question

我正在使用networkx为项目构建图形。对于特定的图，我需要每个节点的最大深度（或嵌套深度）（类似于this）。

例如。

我的图表中有多个节点，比如说 -

G -> d, foo, bar, tar, zar, car, char, jar, par, radar, far, ....

其中d与其他人联系在一起，

d -> {'foo': {'bar': {'tar': 2}, 'zar': {'car': {'char': 1}, 'jar': 'par'}}, 'radar': 'far'}

我想要节点的最大深度（或连接性）。

所以，在这种情况下 - d->foo->zar->car->char（总共5个节点）

有没有办法用networkx计算这个（我有超过1M的节点，所以数据量很大！）？

我检查了他们的手册here。

还在线检查了不同的帖子，但找不到相关信息。

Answer 1

不，他们没有。

所以，我编辑了他们的github代码来添加这个功能。

码：

max_d = []

#dfs_depth base Code reference networkx

def dfs_depth(G, source=None, depth_limit=None):
    if source is None:
        nodes = G
    else:
        nodes = [source]
    visited = set()
    if depth_limit is None:
        depth_limit = len(G)
    for start in nodes:
        print(start)
        if start in visited:
            continue
        max_depth = 0
        visited.add(start)
        stack = [(start, depth_limit, iter(G[start]))]
        while stack:
            parent, depth_now, children = stack[-1]
            try:
                child = next(children)
                if child not in visited:
                    yield parent, child
                    visited.add(child)
                    if depth_now > 1:
                        if((depth_limit - depth_now + 1)>max_depth):
                            max_depth = depth_limit - depth_now + 1
                        stack.append((child, depth_now - 1, iter(G[child])))
            except StopIteration:
                stack.pop()
    global max_d
    max_d.append(max_depth)

在这里，max_d记录最大深度（或嵌套深度）。要计算每个节点的最大深度，可以使用循环（循环遍历所有节点）。