how to perform tree crossover between two graphs using networkx?

Question

I want to perform tree crossover between two graphs using the following steps:

1. Select one node in each graph, the selected node must have the same type i.e. the node are objects of the same class.
2. Exchange the two subgraphs that are rooted by the selected two nodes. each subgraph must be inserted in the same place of the other subgraph.

I have used ego_graph to extract subgraph from each of the two graph, but I do not have idea how to swap the two extracted subgraphs between the two graphs.

Answer 1

Swapping the subtrees can be done as follows:

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()))

Note that in order for it to work you will need unique node identifiers for the 2 graphs (i.e., don't have the same node in both original graphs).