I want to perform tree crossover between two graphs using the following steps:
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.
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).