Как выполнить пересечение деревьев между двумя графиками с помощью networkx? - PullRequest
Новая
       31

Как выполнить пересечение деревьев между двумя графиками с помощью networkx?

0 голосов
/ 30 сентября 2018

Я хочу выполнить пересечение деревьев между двумя графиками, используя следующие шаги:

  1. Выберите один узел в каждом графике, выбранный узел должен иметь один и тот же тип, т.е. узлы являются объектами одного класса.
  2. Обмен двух подграфов, которые укоренены в выбранных двух узлах.каждый подграф должен быть вставлен в то же место другого подграфа.

crossover

Я использовал ego_graph для извлечения подграфа из каждого из двух графиков, но я не знаю, как поменять местамидва извлеченных подграфа между двумя графами.

1 Ответ

0 голосов
/ 02 октября 2018

Обмен поддеревьев может быть выполнен следующим образом: 

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 графиков (т. Е. Не иметь одинаковый узел воба исходных графика).

...