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

Question

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

Select每个图中一个节点，所选节点必须具有相同的类型，即节点是相同的对象class。
交换以所选两个节点为根的两个子图。每个子图必须插入到另一个子图的相同位置。

我已经使用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 个图表提供唯一的节点标识符（即，两个原始图表中的节点不同）。

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

how to perform tree crossover between two graphs using networkx?

python

graph

networkx

crossover