Python - Networkx 搜索前驱节点 - 超出最大深度

我正在使用 Python 中的 Networkx 库（用于图形管理）进行一个项目，并且在尝试实现我需要的内容时遇到了麻烦

我有一个有向图的集合，将特殊对象作为节点和与边关联的权重，问题是我需要从输出节点到输入节点遍历该图。对于每个节点，我必须从其前任节点获取权重以及由该前任节点计算的操作，以从我的输出节点构建操作。但问题是前辈的操作可能依赖于自己的前辈，等等，所以我想知道如何解决这个问题。

到目前为止，我已经尝试了下一个，假设我有一个输出节点列表，我可以使用 Networkx 库的方法浏览前一个节点：

# graph is the object containig my directe graph 
for node in outputNodes:
    activate_predecessors(node , graph)

# ...and a function to activate the predecessors .. 
def activate_predecessors( node = None  , graph ):
    ws = [] # a list for the weight
    res = [] # a list for the response from the predecessor
    for pred in graph.predecessors( node ):
        # get the weights 
        ws.append( graph[pred][node]['weight'] )

        activate_predecessors( pred , graph )
        res.append( pred.getResp() )  # append the response from my predecessor node to a list, but this response depend on their own predecessors, so i call this function over the current predecessor in a recursive way 


    # after I have the two lists ( weights and the response the node should calculate a reduce operation

     # do after turning those lists into numpy arrays...
     node.response = np.sum( ws*res )

这段代码似乎有效......我多次随机尝试过它，但在很多情况下它给出了一个超出最大递归深度所以我需要以更稳定（并且可能是迭代）的方式重写它，以避免最大递归。但我已经没有办法处理这个问题了..

该库有一些搜索算法（深度优先搜索） https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.traversal.html但我不知道它如何帮助我解决这个问题。

我还尝试在节点上放置一些标志以了解它是否已被激活，但我不断收到相同的错误。

编辑：我忘记了，输入节点有一个定义的响应值，因此它们不需要进行计算。

your 代码可能包含无限递归如果两个节点之间存在环路。例如：

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(1,2), (2,1)])

def activate_nodes(g, node):               
    for pred in g.predecessors(node):
        activate_nodes(g, pred)

activate_nodes(G, 1)
RuntimeError: maximum recursion depth exceeded

如果其中一个图表上有可能的循环，您最好将每个节点标记为已访问或更改图表上的边以使其没有循环。

假设您的图表上没有循环，这里是如何迭代实现算法的示例：

import networkx as nx

G = nx.DiGraph()
G.add_nodes_from([1,2,3])
G.add_edges_from([(2, 1), (3, 1), (2, 3)])

G.node[1]['weight'] = 1
G.node[2]['weight'] = 2
G.node[3]['weight'] = 3

def activate_node(g, start_node):          
    stack = [start_node]
    ws = []

    while stack:
        node = stack.pop()
        preds = g.predecessors(node)
        stack += preds
        print('%s -> %s' % (node, preds))
        for pred in preds:
            ws.append(g.node[pred]['weight'])

    print('weights: %r' % ws)
    return sum(ws)


print('total sum %d' % activate_node(G, 1))

此代码打印：

1 -> [2, 3]
3 -> [2]
2 -> []
2 -> []
weights: [2, 3, 2]
total sum 7

Note

您可以使用以下命令反转有向图的方向DiGraph.reverse() https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.operators.unary.reverse.html

如果您需要使用 DFS 或其他方法，您可以反转图以将前驱节点视为该节点的直接连接的邻居。使用这个，像 DFS 这样的算法可能会更容易使用。