0

我有一个无向图，我想迭代地删除每个串行边并用新边替换它。新边的权重代表生成树的数量，计算如下：T_new = (1/a+b) * T_old, 其中a和b是删除边的权重，T_new 是当前迭代中生成树的数量，T_old 是前一次迭代中生成树的数量。这个方程随着图形的变化而迭代地变化，所以如果我们有 4 次迭代，我们将有 4 个方程，每个方程都是前一个方程。一旦图形不再有串行边，我们就会停止。如果最终图由 1 条边组成，则该边的权重是最后一条 T_new，我们将有一个数值 T-old。否则，就 T_new 而言，我们应该有 T_old。这是一个附加的图像，解释了我所说的，以防它没有得到很好的解释。这是我描述问题的代码部分：

** PS：我只需要方程在每次迭代中发生变化的部分，而不是删除和添加新边等要做的事情。这是一个例子：在此处输入图像描述**

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
4

1 回答 1

0

不需要递归，因为我们会随时更改图形。这是一个解决方案：

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)
于 2019-01-14T08:17:28.473 回答