Networkx has_edge для неориентированного графа учитывается только один раз - PullRequest
Новая
       12

Networkx has_edge для неориентированного графа учитывается только один раз

1 голос
/ 16 мая 2019

У меня есть следующий график: 

full_graph = nx.Graph()

tgt_nodes = ['B','F']

full_graph.add_edge('A','B')
full_graph.add_edge('B','C')
full_graph.add_edge('B','D')
full_graph.add_edge('B','E')
full_graph.add_edge('E','F')

#display and save as img
p = nx.drawing.nx_pydot.to_pydot(full_graph)
p.layout = 'spring'

#p.write_png(outputDir+ version+ '//' + 'cluster_no' + str(clusterNo) + '.png')
display.Image(p.create_png())

enter image description here

Я пытаюсь найти все узлы, которые находятся точно на расстоянии двух соединений, и делаювещи с ними в зависимости от веса. 

out_graph = nx.Graph()

for curr_node in tgt_nodes:

        #find all paths for curr_node that are <=2
        pot_paths = nx.single_source_dijkstra_path_length(full_graph, curr_node,2)
        print(pot_paths)

        #iterate over all potential paths. If length ==2 either increment weight or add with weight = 1
        for pot_node, dist in pot_paths.items():

            if dist == 2:
                print(pot_node)

                if out_graph.has_edge(curr_node, pot_node):

                    # we added this one before, just increase the weight by one. NEED TO LIMIT SO THAT THIS DOESN't TRIGGER ON INVERSES
                    out_graph[curr_node][pot_node]['weight'] += 1
                    print('incremented edge for '+ curr_node)
                else:
                    # new edge. add with weight=1
                    out_graph.add_edge(curr_node, pot_node, weight=1)
                    print('added edge for '+ pot_node)

Это должно срабатывать только один раз - при сравнении B> F следует добавить ребро.Когда дело доходит до F> B, я не хочу, чтобы оно увеличивалось, потому что оно точно обратное.Вот мои результаты: 

>> {'B': 0, 'A': 1, 'C': 1, 'D': 1, 'F': 2, 'E': 1}
>> F
>> added edge for F
>> {'F': 0, 'B': 2, 'E': 1}
>> B
>> incremented edge for F

out_graph.edges(data = True)

>> EdgeDataView([('F', 'B', {'weight': 2})])

Как я могу изменить так (F, B) и (B, F) для одного и того же промежуточного узла, который считается один, а не два?

Спасибо!

РЕДАКТИРОВАТЬ

Собственно, вот пример, который не работает: 

full_graph = nx.Graph()

tgt_nodes = ['B','F']

full_graph.add_edge('A','B')
full_graph.add_edge('B','C')
full_graph.add_edge('B','D')
full_graph.add_edge('B','E')
full_graph.add_edge('E','F')
full_graph.add_edge('G','F')
full_graph.add_edge('B','G')
full_graph.add_edge('F','H')
full_graph.add_edge('B','H')


#display and save as img
p = nx.drawing.nx_pydot.to_pydot(full_graph)
p.layout = 'spring'

#p.write_png(outputDir+ version+ '//' + 'cluster_no' + str(clusterNo) + '.png')
display.Image(p.create_png())

Он выводит ребро 2, когда это должнобыть 3 (B & F соединены через G, E и H)

Ответы [ 3 ]

2 голосов
/ 16 мая 2019

Так что да, если G не является ненаправленным, то G.has_edge(a,b) и G.has_edge(b,a) оба равны True, если ребро существует, и False, если ребро не существует.

Итак, учитываяКак настроен ваш код, вы дважды посмотрите на каждую пару узлов и дважды выполните одно и то же вычисление.

Как насчет добавления еще одного условия: if G.has_edge(a,b) and a<b: (если вы делаете это в случае, когдау вас может быть самообладание, вы можете подумать о a<=b).

Тогда один из двух случаев будет игнорировать вычисления.Пока узлам определена операция сравнения, она будет работать.Так что 'A'<1 не будет работать, но 'A'<'B' возвращает True.

Предупреждение, которое я должен дать, это то, что это работает, только если вы гарантированно видите каждое ребро в обоих направлениях, то естьесли оба узла появляются в вашем списке tgt_nodes.Если появляется только «больший» узел, он не будет его считать.Так что вам может понадобиться усовершенствовать свой тест для этого.

1 голос
/ 16 мая 2019

За запрос @ Energya - вот простой код, который работает: 

out_graph = nx.bipartite.weighted_projected_graph(full_graph, ['B','F'])
0 голосов
/ 16 мая 2019

Вы определяете длину пути на основе full_graph, но добавляете ребра к out_graph.После добавления ребра (B, F) к out_graph он все еще не существует в full_graph.В конце концов, ваш out_graph инициализируется как пустой.Вот почему ваш out_graph в конце содержит только один край (B, F).

Если ваша цель - обновить оригинал, вы должны инициализировать out_graph вбудьте копией full_graph и сделайте все свои вычисления на этом.В зависимости от ваших потребностей, встроенный в Networkx out_graph = full_graph.copy() может сделать свое дело, в противном случае вы должны взглянуть на Python copy.deepcopy().

...