Как написать рекурсивную функцию для вычисления числа связующих деревьев в неориентированном взвешенном графе, используя python? - PullRequest
Новая
       19

Как написать рекурсивную функцию для вычисления числа связующих деревьев в неориентированном взвешенном графе, используя python?

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

У меня есть неориентированный взвешенный граф, и я хочу итеративно удалять каждое последовательное ребро и заменять его новым ребром. И в каждой итерации я хочу иметь уравнение, которое зависит от уравнения в предыдущей итерации, но я не могу напиши что в python

Вот изображение, которое объясняет, что я хочу (T (G0)): enter image description here G0 - это начальный граф, T (G0) - это число его связующих деревьев, которые я хочу вычислить в конце концов. G1 - это граф после удаления первых последовательных ребер (первая итерация), а T (G1) - количество остовных деревьев графа в текущей итерации. G2 - конечный граф, а T (G2) - число остовных деревьев последнего графа. ВАЖНО: если у графа есть одно ребро (не больше последовательных ребер), T (G2) = вес последнего и единственного ребра в конечном графе. Затем мы заменяем все уравнения в латах (T (G2) = 2/5 * T (G0)), затем заменяем T (G2) его весом, поскольку у графа есть одно ребро, чтобы в результате получился T (G0) , Вот код, который я попробовал: 

import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([(0,1,1),(0,2,1),(2,3,1),(3,4,1)])
     def tau(G) : 

        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) 
                draw(G)

                #the part i need to give me the desirable result T(G0)
                if G.number_of_edges() == 1 :
                    t_new = list(G.edges(data=True))[0][2]['weight']
                    t_old = (a+b) * t_new

                else : 
                    t_old =  (a+b) * tau(G)
                    t_new = 1/(a+b) * t_old

                print(t_old)
                return t_old

    tau(G)

А вот та часть, где веса нового графа в каждой итерации вычисляются как @ zohar.kom, предложенный здесь: 2 

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