Python-Networkx搜索前身节点-超出最大深度 [英] Python - Networkx search predecessor nodes - Maximum depth exceeded

问题描述

我正在使用Python中的Networkx库(用于图形管理)在一个项目中工作，而在尝试实现所需的内容时遇到了困难

I'm working in a project using the library Networkx ( for graph management ) in Python, and I been having trouble trying to implement what I need

我有一个有向图集合，其中包含特殊对象作为节点和与边关联的权重，这是我需要从输出节点到输入节点遍历该图.对于每个节点，我必须权衡其前任节点的权重以及由该前任节点计算的运算，以从我的输出节点构建该运算.但是问题在于，前任的运作可能取决于他们自己的前任，依此类推，所以我想知道如何解决这个问题.

I have a collection of directed graphs, holding special objects as nodes and weights associated with the edges, the thing is I need to go through the graph from output nodes to input nodes. and for each node I have to take the weights from their predecessors and an operation calculated by that predecessor node to build the operation form my output node. But the problem is that the operations of the predecessors may depend from their own predecessors, and so on, so I'm wondering how I can solve this problem.

到目前为止，我已经尝试了下一个，可以说我有一个输出节点列表，并且可以使用Networkx库的方法遍历前辈:

So far I have try the next, lets say I have a list of my output nodes and I can go through the predecessors using the methods of the Networkx library:

# 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 )

这段代码似乎可以正常工作……我随机尝试了很多次，但是在很多情况下，它给出了最大递归深度超过，因此我需要以更稳定的方式重写它(并可能采用迭代方式)，以避免最大程度的递归.但是我没有足够的想法来解决这个问题.

This code seems to work... I tried it on in some random many times, but in many occasions it gives a maximum recursion depth exceeded so I need to rewrite it in a more stable ( and possibly iterative ) way in order to avoid maximum recursion. but I'm running out of ideas to handle this..

该库具有一些搜索算法(深度优先搜索) ，但是我不知道如何解决这个问题.

the library has some searching algorithms (Depth first search) but after I don't know how it could help me to solve this.

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

I also try to put some flags on the nodes to know if it had been already activated but I keep getting the same error.

我忘了，输入节点具有定义的响应值，因此它们不需要进行计算.

I forgot, the input nodes have a defined response value so they don't need to do calculations.

推荐答案

如果两个节点之间存在循环，您的代码可能包含无限递归.例如:

your code may contain an infinite recursion if there is a cycle between two nodes. for example:

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

如果其中一个图上可能存在循环，则最好将每个节点标记为已访问，或者将图上的边更改为不具有循环.

if you have possible cycles on one of the graphs you better mark each node as visited or change the edges on the graph to have no cycles.

假设您的图形上没有循环，这是一个如何迭代实现算法的示例:

assuming you do not have cycles on your graphs here is an example of how to implement the algorithm iteratively:

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

注意

您可以使用 DiGraph.reverse()

如果需要使用DFS或其他功能，则可以反转图形以将前任作为该节点的直接连接邻居获得.使用此功能，像DFS这样的算法可能更易于使用.

if you need to use DFS or something else you can reverse the graph to get the predecessor as just the directly connected neighbours of that node. Using this, algorithms like DFS might be easier to use.

这篇关于Python-Networkx搜索前身节点-超出最大深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！