python - 如何使用networkx在两个图之间执行树交叉？

Question

我想使用以下步骤在两个图之间执行树交叉：

1. 在每个图中选择一个节点，选择的节点必须具有相同的类型，即节点是同一类的对象。
2. 交换以选定的两个节点为根的两个子图。每个子图必须插入另一个子图的相同位置。

我曾经ego_graph从两个图中的每一个中提取子图，但我不知道如何在两个图之间交换两个提取的子图。

Answer 1

交换子树可以如下完成：

import networkx as nx
from networkx.algorithms.traversal.depth_first_search import dfs_tree

t1 = nx.DiGraph()
t1.add_edge(0, 1)
t1.add_edge(0, 2)
t1.add_edge(2, 3)
t1.add_edge(2, 4)
t1.add_edge(2, 5)
print('t1:\n{}\n'.format(t1.edges()))

t2 = nx.DiGraph()
t2.add_edge(10, 11)
t2.add_edge(10, 12)
t2.add_edge(10, 13)
t2.add_edge(11, 14)
t2.add_edge(14, 15)
t2.add_edge(14, 16)
t2.add_edge(14, 17)
print('t2:\n{}\n'.format(t2.edges()))

def swap_sub_trees(t1, node1, t2, node2):
    sub_t1 = dfs_tree(t1, node1).edges()
    sub_t2 = dfs_tree(t2, node2).edges()
    replace_sub_tree(t1, sub_t1, node1, sub_t2, node2)
    replace_sub_tree(t2, sub_t2, node2, sub_t1, node1)

def replace_sub_tree(t1, sub_t1, root1, sub_t2, root2):
    t1.remove_edges_from(sub_t1)
    t1.add_edges_from(sub_t2)
    in_edges_1 = t1.in_edges(nbunch=root1)
    for e in list(in_edges_1):
        t1.remove_edge(e[0], e[1])
        t1.add_edge(e[0], root2)

swap_sub_trees(t1, 2, t2, 11)

print('t1:\n{}\n'.format(t1.edges()))
print('t2:\n{}\n'.format(t2.edges()))

请注意，为了使其工作，您将需要 2 个图形的唯一节点标识符（即，在两个原始图形中没有相同的节点）。