Python NetworkX: Обновление графика после сжатия узла

Question

Я создал орграф networkX следующим образом:

import networkx.algorithms.isomorphism as iso
import networkx as nx
G1 = nx.DiGraph()
G1.add_nodes_from(range(1,7))

# Creating Acyclic Directed Graph
G1.add_edges_from([(1,2),(2,3),(3,4),(1,4),(4,5),(5,6)])

На графике G1 выглядит следующим образом:

Now I want to contract node 2 in node 1 which I am doing using NetowrkX's "contract_node" function. I plot the graph and print all nodes and edges after contraction.

H = nx.contracted_nodes(G1,1,2,self_loops=False)
print(H.nodes)
print(H.edges)

введите описание изображения здесь

Он просто сворачивает узел 2 в узле 1, и все ребра между 2 и 1 удаляются, как будто узел 2 никогда не существовал, что делает индекс узла несмежным [1,3,4,5,6] . Вместо этого я хочу обновить граф после сжатия узла и отодвинуть все узлы над узлом с ограничением (в данном случае 2), чтобы мой список узлов и список ребер выглядели следующим образом:

Node List : [1,2,3,4,5]
Edge List : [(1,3),(1,2),(2,3),(3,4),(4,5)]

В основном узел обновления idx всех узлов над узлом с ограничением по количеству узлов с ограничением (в данном случае на 1, поскольку я заключаю договор с одним узлом) и обновите соответствующие ссылки.

Есть ли функция NetworkX для этого? Если нет, то как лучше всего этого добиться? В конце концов, я хотел бы объединить узлы в упорядоченный граф (отсортированные списки узлов и ребер), а затем сравнить его с другими упорядоченными графами (отсортированные списки узлов и ребер) на предмет изоморфизма. Функции изоморфизма NetworkX предоставляют логический результат (Графы являются Изоморфными c или Графы НЕ являются Изоморфными c), но они НЕ предоставляют никакой информации о точках расхождения между 2 Неизоморфными c графиками. Есть ли поддержка NetworkX для этого? Учитывая начальный узел, для поиска точки расхождения я планировал получить все списки ребер с помощью nx.edge_bfs () для 2 упорядоченных графов и сравнить их, чтобы найти точку расхождения для дальнейшего исследования. Этот подход потерпит неудачу, если idx узлов не являются смежными. Спасибо за ваше время.

Answer 1

Вы можете использовать nx.relabel_nodes для перемаркировки ваших узлов и ребер. Пример:

>>> mapping = dict(zip(sorted(H), range(1,len(H)+1)))
>>> mapping
{1: 1, 3: 2, 4: 3, 5: 4, 6: 5}
>>> H2 = nx.relabel_nodes(H, mapping)
>>> H2.nodes
NodeView((1, 2, 3, 4, 5))
>>> H2.edges
OutEdgeView([(1, 3), (1, 2), (2, 3), (3, 4), (4, 5)])