Coalesce 2 узла в сетевом графике

Question

Я шел, хотя функция blockmodel в networkx. Кажется, что-то очень похоже на то, что я хочу.

Я хочу объединить два узла в диаграмме networkx и заменить их на метки узлов, соответствующие любому из соединяемых узлов. Остальные узлы должны оставаться без изменений в своих именах. (Правила узла присоединения являются такими, как описано в руководстве blockmodel 1)

• Как за то, что я понял, blockmodel требует создания явных paritions целого графа, прежде чем он может быть использован, что не так удобно.
• Отсутствует контроль над именами сформированных моделей блоков (то есть узлов нового графика).

Как я могу достичь этой, казалось бы, более простой задачи свернуть 2 узла в один? Я хочу сделать это над неориентированным графом с взвешенными ребрами.

Answer 1

Вот моя попытка создать функцию coalesce для программы раскраски графа, над которой я работаю. Это, однако, не работает с взвешенными краями.

import networkx as nx 
# G is a graph created using nx 
# this is to establish the number of colors 
k = 5 
# inputs node1 and node2 are labels of nodes, e.g. 'a' or 'b' etc. 
def coalesce(G,node1,node2): 
    """Performs Briggs coalescing. Takes in the graph and two nodes. 
    Returns 1 if unable to coalesce, 0 otherwise.""" 
    if node1 in G.neighbors(node2) or node2 in G.neighbors(node1): 
     print "Cannot coalesce. Node",node1,"and node",node2,"share an edge" 
     return 1 
    elif G.degree(node1)+G.degree(node2) >= k: 
     print "Cannot coalesce. Combined degree of",node1,"and",node2,"\ 
is",G.degree(node1)+G.degree(node2),"which is too high for k =",k 
     return 1 
    else: 
     newedge = [] 
     for i in range(len(G.neighbors(node2))): 
      newedge.append((node1 , G.neighbors(node2)[i])) 
     G.add_edges_from(newedge) 
     G.remove_node(node2) 
     nx.relabel_nodes(G, {node1:node1+node2},copy=False) 
    return 0