Как написать рекурсивную функцию в Python? - PullRequest
Новая
       31

Как написать рекурсивную функцию в Python?

0 голосов
/ 13 января 2019

У меня есть неориентированный граф, и я хочу итеративно удалить каждое последовательное ребро и заменить его новым ребром. Вес нового ребра представляет количество связующих деревьев и должен быть вычислен следующим образом: T_new = (1/a+b) * T_old, где a и b - веса удаленных ребер, T_new - это количество остовных деревьев в текущей итерации, а T_old - количество остовных деревьев в предыдущей итерации. Это уравнение изменяется итеративно по мере изменения графика, поэтому, если у нас есть 4 итерации, у нас будет 4 уравнения, каждое из которых соответствует предыдущему. Мы остановимся, как только у графа не останется серийных ребер. Если конечный граф состоит из 1 ребра, вес этого ребра является последним T_new, и у нас будет числовое значение T-old. В противном случае мы должны иметь T_old в терминах T_new. Вот прикрепленное изображение , объясняющее, что я сказал в случае, если это не очень хорошо объяснено. Вот часть моего кода, описывающая проблему:

** PS: мне нужна только часть, где уравнение меняется на каждой итерации, а не то, что нужно сделать, чтобы удалить и добавить новые ребра и т. Д. Вот пример: enter image description here * *

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

1 Ответ

0 голосов
/ 14 января 2019

Рекурсия не требуется, так как мы меняем график по мере продвижения. Вот решение: 

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