查找最大循环子树

Question

我有一个这样的 Python 字典：

dictionary = {
    'r1': {
        'val': 'r',
        'sub': {
            'a1': {
                'val': 'a',
                'sub': {
                    'b1': {
                        'val': 'b',
                        'sub': {}
                    }
                }
            },
            'b1': {
                'val': 'b',
                'sub': {
                    'c1': {
                        'val': 'c',
                        'sub': {}
                    },
                    'a2': {
                        'val': 'a',
                        'sub': {
                            'c2': {
                                'val': 'c',
                                'sub': {}
                            },
                        }
                    },
                    'a3': {
                        'val': 'a',
                        'sub': {}
                    },
                    'b2': {
                        'val': 'b',
                        'sub': {}
                    },
                    'a4': {
                        'val': 'a',
                        'sub': {
                            'c3': {
                                'val': 'c',
                                'sub': {}
                            },
                            'd1': {
                                'val': 'd',
                                'sub': {}
                            }
                        }
                    }
                }
            }
        }
    }
}

将字典解释为一棵树，我需要做的是找到最大循环子树。

对于最大循环子树，我的意思是例如：

subtree = {
    'structure': {
        'r': {
            'sub': {
                'b': {
                    'sub': {
                        'a': {
                            'sub': {
                                'c': {
                                    'sub': {}
                                },
                            }
                        },
                    }
                }
            }
        }
    },
    'counter': 2
}

基本上我正在尝试实现一个递归函数，例如：

def find_max_subtree(dict: tree, dict: output) -> dict:
    for key in tree:
        ...
        output[key] = {
            'sub' = {}
        }
        output[key]['sub'] = find_max_subtree(key['sub'], output['sub'])
    return output

不知道怎么解决。即使是伪代码策略对我来说也足够了。

Answer 1

您可以在递归时保留一个深度计数器，并且在每个级别，return 具有最大关联计数器的子词典：

def max_subtree(d, c = 0):
  a, c_d, b = max([(a, c, b) if not b else (a, *max_subtree(b, c+1)) 
                       for a, b in d.items()], key=lambda x:x[1])
  return (c_d, {a:b})

_, sub_dict = max_subtree(dictionary)

输出：

{'r': {'sub': {'b': {'sub': {'a': {'sub': {'c': {'sub': {}}}}}}}}}

from collections import Counter
def build_dict(d):
   return {} if not d else {d[0]:{'sub':build_dict(d[1:])}}

def get_paths(d, c = []):
   if 'sub' not in d:
      yield from [j for i in d.values() for j in get_paths(i,c)]
   elif not d['sub']:
      yield tuple(c+[d['val']])
   else:
      for _, b in d['sub'].items():
        yield from get_paths(b, c+[d['val']])

result = Counter(get_paths(dictionary))
c = max(result, key=lambda x:[result[x] > 1, result[x], len(x)])
print(build_dict(c), result[c])

输出：

{'r': {'sub': {'b': {'sub': {'a': {'sub': {'c': {'sub': {}}}}}}}}} 2

查找最大循环子树

Find maximum recurring subtree

python

algorithm

tree

graph-theory

pseudocode