pythonnetworkxgraph-theorydepth-first-searchdepth

Does networkx give maximum depth (or nesting depth)?


I am using networkx to build graphs for a project.For a specific plot I need max depth (or nesting depth) of each node (something like this).

For eg.

I have multiple nodes in my graph, say-

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

where d is connected with others like this,

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

I want max depth (or connectivity) of nodes.

So, in this case - d->foo->zar->car->char (5 nodes in total)

Is there any way to calculate this using networkx (I have over 1M nodes, so the data is huge!)?

I checked their manual here.

Also checked different posts online but couldn't find the information.


Solution

  • No, they don't.

    So, I edited their github code to add this functionality.

    Code:

    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)
    

    Here max_d keeps track of the maximum depth (or nesting depth). To calculate the maximum depth of each node, a loop can be used (which iterates through all the nodes).