配置继承机制

Question

我有以下结构：

config
  |-- groups
    |-- rootgroup
    |-- group1 (includes rootgroup)
    |-- group2 (includes group1)
    |-- group3 (includes rootgroup)
  |-- users
    |-- Fred (includes group3 and group2)

因此 Fred 的继承树将如下所示：

    _Fred_
   v      v
group2  group3
   v      v
group1    v
   v     /
rootgroup

我需要一个算法来打印从树的左下角开始的线性配置读取顺序（对于给定的示例，它将是 rootgroup - group1 - group2 - group3; group1覆盖 rootgroup，group2 覆盖 group1 等...）并查找递归链接（例如，如果 rootgroup 包含组 2），而且它必须找到递归循环（... -> group2 -> group1 -> rootgroup - >组2->...)。

首选语言是 python，但任何语言都可以。

谢谢。

Answer 1

在阅读了有向无环图（DAG）之后，我想出了以下解决方案：

def getNodeDepsTree(self, node, back_path=None):
    """Return whole dependency tree for given node"""
    # List of current node dependencies
    node_deps = []

    if not back_path:
        back_path = []

    # Push current node into return path list
    back_path.append(node)

    # Get current node dependencies list
    deps = getNodeDeps(node)

    for dep in deps:
        # If dependency persist in list of visited nodes - it's a recursion
        if dep in back_path:
            pos = back_path.index(dep)
            self.log.error("Recursive link detected. '" + node
                    + "', contains a recursive link to '" + dep
                    + "'. Removing dependency. Recursive loop is:\n\t"
                    + '\n\t'.join(back_path[pos:]))
            continue
        # Recursively call self for child nodes
        node_deps.extend(self.getNodeDepsTree(dep, back_path))

    # Finally add current node as dependency
    node_deps.append(node)

    # Remove current node from list of visited nodes and return
    back_path.pop()

    return node_deps