Проблемы с Networkx optim_edit_paths (расстояние редактирования графика)

Question

Я использую Networkx, чтобы найти расстояние редактирования графа (GED) между двумя направленными ациклическими c графами (DAG) с помощью метода Reconcile, показанного ниже, с целью согласования дерева. Я сопоставляю узлы и края по их меткам, которые (как показано) являются просто их идентификаторами.

В приведенном ниже тестовом примере я копирую график g1 в g2 и добавляю n новые узлы / ребра до g2, затем удалите m узлов / ребер. Даже в случае n = несколько сотен, метод Reconcile работает очень быстро, когда m = 0. Однако моя проблема в том, что он становится очень медленным, если я удаляю более 2 или 3 узлов, которые в противном случае были бы общий для обоих графиков.

import networkx as nx

class MyGraph(nx.DiGraph):

    @classmethod
    def Reconcile(cls, a1, a2):

    # ---------------------------------------------------------------------
    # STAGE 1: MAP NODES/EDGES B/T THE TWO GRAPHSS

    # Equality here means having same labels

        def return_eq(item1, item2):

            label1 = item1['label']
            label2 = item2['label']

            _eq = label1 == label2

            if _eq:
                print('Mapped ', label1, 'to ', label2)

            return _eq


        # ---------------------------------------------------------------------
        # STAGE 2: FIND EDIT PATHS

        paths, cost_nx = nx.optimal_edit_paths(a1, a2, node_match = return_eq, edge_match = return_eq)
        paths = paths[0]

        node_edits = [el for el in paths[0] if el[0] != el[1]]
        edge_edits = [el for el in paths[1] if el[0] != el[1]]
        cost = len(node_edits) + len(edge_edits)

        print('Node edits: {}\nEdge edits: {}\nTotal cost (Networkx): {}\nTotal cost (no. of edits): {}'.format(
            node_edits, edge_edits, cost_nx, cost))
        print('No. of node edits: ', len(node_edits))
        print('No. of edge edits: ', len(edge_edits))

        return paths, cost_nx, cost, node_edits, edge_edits

#######################################################

g1 = MyGraph()

p = 10
edges = [('root', edge) for edge in range(p)]
g1.add_edges_from(edges) # Add root and some nodes + edges

g2 = g1.copy()

n = 10
for edge in range(n):
    node = 100*(edge+10)
    print('Edge added: ', edge)
    g2.add_edge('root2', node) # Add some more edges + nodes not present in g1

m = 2 # When m > 2, code slows massively
for node in list(g1.nodes)[-m:]: # Any will do!
    print('Node/edge removed:', node)
    g2.remove_node(node)

for g in [g1,g2]:
    for node in g.nodes:
        g.nodes[node]['label'] = node
    for edge in g.edges:
        g.edges[edge]['label'] = edge

paths, cost_nx, cost, node_edits, edge_edits = MyGraph.Reconcile(g1,g2)

Возможно, здесь что-то не хватает, и, возможно, проблема просто вычислительная: я понимаю, что это сложная проблема, и абсолютно не предполагаю, что это ошибка в Networkx. Тем не менее, любая помощь или понимание были бы очень признательны, например, путем предварительной обработки графиков перед попыткой их согласования.