Механизм наследования конфигурации

Question

У меня следующая структура:

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

Так что дерево наследования для Фреда будет выглядеть так:

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

Мне нужен алгоритм для печати порядка чтения линейной конфигурации, начиная свнизу слева от дерева (для данного примера это будет rootgroup - group1 - group2 - group3; group1 перезаписывает rootgroup, group2 перезаписывает group1 и т. д.) и находит рекурсивные ссылки (например, если rootgroup включает группу 2), более того, она должнанайти цикл рекурсии (... -> group2 -> group1 -> rootgroup -> group2 -> ...).

Предпочтительным языком является 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