Configuration inheritance mechanism

Question

I have the following structure:

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

So inheritance tree for Fred will look like:

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

I need an algorithm to print the linear config read order beginning at the bottom left of the tree (for given example it would be rootgroup - group1 - group2 - group3; group1 overwrites rootgroup, group2 overwrites group1, etc...) and find recursive links (for example if rootgroup includes group 2), moreover it must find the recursion loop (... -> group2 -> group1 -> rootgroup -> group2 -> ...).

Preferable language is python, but any will do.

Thanks.

Answer 1

Well after reading about directed acyclic graphs (DAG) I came up with following solution:

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