Дает ли 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 узлов, поэтому данные огромны!)?

Я проверил их руководство здесь .

Также проверил различные сообщения в Интернете, ноне смог найти информацию.

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 отслеживает максимальную глубину (или глубину вложения).Чтобы рассчитать максимальную глубину каждого узла, можно использовать цикл (который проходит через все узлы).