如何在Python中编写递归函数? [英] How to write a recursive function in Python?
问题描述
我有一个无向图,我想迭代地删除每个串行边缘,并用新的边缘替换它.新边的权重表示生成树的数量,应按以下方式计算:T_new = (1/a+b) * T_old
,其中 a 和 b 是已删除边的权重, T_new是当前迭代中的生成树数,T_old是前一次迭代中的生成树数.这个方程随着图形的变化而迭代地变化,因此,如果我们有4次迭代,我们将有4个方程,每个方程都与前一个方程有关.一旦图表不再有串行边,我们将停止.如果最终图形由1条边组成,则该边的权重为最后的T_new,我们将得到T-old的数值.否则,就T_new而言,我们应该使用T_old.这是随附的图片,以解释我在未正确解释的情况下所说的内容.
这是我的代码描述问题的部分:
I have an undirected graph, and I want to iteratively remove each serial edge and replace it with a new edge. The weight of the new edge represents the number of spanning trees, and should be computed as follows: T_new = (1/a+b) * T_old
, where a and b are the weights of the removed edges, T_new is the number of spanning trees in current iteration and T_old is the number of spanning trees in the previous iteration. This equation changes iteratively, as the graph changes, so if we have 4 iterations we will have 4 equations, each one is in terms of the previous one. We stop once the graph has no more serial edges. If the final graph is composed of 1 edge, the weight of that edge is the last T_new, and we will have a numerical value of T-old. Otherwise, we should have T_old in terms of T_new. Here is an attached image explaining what I said in case it is not well explained.
Here is the part of my code describing the problem :
** PS:我只需要方程在每次迭代中都发生变化的部分,而不是删除和添加新边等的事情.下面是一个示例: **
** PS : I only need the part where the equation changes in every iteration, not the things to do to remove and add new edges and so on.here is an example : **
import networkx as nx
def fun2(G) :
L1= G.degree()
print(L1)
L= list(L1)
for x in L :
if G.degree(x[0]) == 2 : #if the adjacent edges to x[0] are serial
... do somthing(remove edges and add new one with new weight)
#T-new = 1/(a+b) T-old here the equation should change
def tau(G) : # it should return T_old which is the number of spanning trees of the initial graph
if G.number_of_edges() == 1 :
T_new = list(G.edges(data=True))[0][2]['weight']
T_old = (a+b) * t_new
else :
T_new = 1/(a+b) * tau(G)
T_old = (a+b) * t_new
return t_old
推荐答案
不需要递归,因为我们可以随时更改图形.这是一个解决方案:
No recursion is needed, as we change the graph as we go. Here's a solution:
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([(0,1,5),(0,2,10),(2,3,30)])
for node in list(G.nodes()):
if G.degree(node) == 2:
neighbors = list(G.neighbors(node))
a = G.get_edge_data(neighbors[0], node)['weight']
b = G.get_edge_data(neighbors[1], node)['weight']
w = (a * b) / (a + b)
G.add_edge(neighbors[0], neighbors[1], weight=w)
G.remove_node(node)
这篇关于如何在Python中编写递归函数?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!