Сравнение двух деревьев/графиков в Python

Question

Прежде всего, я должен признаться, что я очень плохо отношусь к графику. Мои деревья реализованы как вложенные словари, которые представляют собой невзвешенные цепи Маркова.

class Tree(object): 
    def __init__(self, depth=6, seq=None): 
     self.graph = dict() 
     self.depth = depth 
     if seq is not None: 
      self.build(seq) 

    def build(self, seq): 
     for i in xrange(len(seq)): 
      sseq = seq[i:i+self.depth] 
      for j in xrange(len(sseq)): 
       if j == 0: 
        if sseq[j] not in self.graph: 
         self.graph[sseq[j]] = dict() 
        nest_pointer = self.graph[sseq[j]] 
       else: 
        if sseq[j] not in nest_pointer: 
         nest_pointer[sseq[j]] = dict() 
        nest_pointer = nest_pointer[sseq[j]] 

Что мне нужно, чтобы иметь возможность сравнить два дерева, в то же время известно о глубине, на которой происходят несходства, потому что я собираюсь использовать иерархическую систему подсчета очков сходства, поэтому простой рекурсивный DFS не делает Хитрость.

P.S.

Если вы можете предложить лучшую структуру данных для моих деревьев, я был бы очень признателен. Я пошел со словарями, чтобы получить максимальную производительность. Заранее спасибо.

Answer 1

Почему вы не можете использовать рекурсивную DFS? Просто передайте текущую высоту в качестве параметра. Я не совсем уверен, как вы идете по поводу сравнения узлов или поддеревьев, но что-то подобное может работать, что просто записывает все времена, что два узла сравнения неравны (с некоторым определенным пользователем сравнению nodes_different)

(псевдокод):

def compare_trees_r(node1, node2, depth, result): 
    if nodes_different(node1, node2): 
     result.append(depth) 
    for (pairs of children c1 and c2): 
     compare_trees_r(c1, c2, depth + 1, result) 

def compare_trees(t1, t2): 
    result = [] 
    compare_trees_r(t1.graph, t2.graph, 0, result) 
    return result 

Насколько ваша фактическая структура данных идет, трудно предложить более подходящую структуру, не зная, что такое seq. Тем не менее, я настоятельно рекомендую вам создать класс для ваших узлов, что значительно облегчит рассуждения о вашем коде. Если окажется, что на самом деле это вызывает проблему производительности (после профилирования), только тогда ее оптимизируйте (прежде всего, преждевременная оптимизация - корень всего зла).