从对象列表构建 tree/linked 列表

Question

我正在尝试从模块及其各自的子模块构建树状层次结构，每个模块都有名称、数据及其子模块列表，

@dataclass
class module(object):
    name: str
    data: int
    submodules: list = field(default_factory=list)


def main():
    module1 = module("Module1", 1, ["Module2", "Module3"])
    module2 = module("Module2", 2, ["Module4"])
    module3 = module("Module3", 3, ["Module6", "Module7"])
    module4 = module("Module4", 4, ["Module5"])
    module5 = module("Module5", 5, )
    module6 = module("Module6", 6, )
    module7 = module("Module7", 7, )

    module_list = [module4, module2, module6, module1, module3, module5, module7] #This is just Example Data 

    for mod in module_list:
        for item in module_list:
            if mod.name in item.submodules:
                print(mod.name + " is submodule of " + item.name)


if __name__ == '__main__':
    main()

使用这段代码，我能够检测出某个东西是否是其他东西的子模块，但我不知道我应该如何形成 connections/build 数据结构。

我想要的输出应该是这样的：

module1 
├── module2
│   └── module4
│       └── module5
└── module3
    ├── module6
    └── module7

我尝试使用 Anytree and Treelib 为任意数量的模块实现此目的，但我无法提出可行的解决方案。虽然这个问题看起来很简单（可能不是）我就是想不通。

干杯！

Answer 1

您的数据结构已经代表了层次结构，但您也可以存储模块父级的引用，并拥有一个容器class Hierarchy 以方便访问功能。

我会用大写 M 命名 class Module，并在 submodules 中存储 references 到模块实例而不是字符串。容器 Hierarchy class 可以充当字典，以便通过名称访问模块实例。

这是一个提议：

class Module:
    def __init__(self, name: str, data: int, parent: 'Module' = None):
        self.name = name
        self.data = data
        self.parent = parent
        if parent:
            parent.submodules.append(self)
        self.submodules = []

    def preorder(self, depth):
        yield self, depth
        for submodule in self.submodules:
            yield from submodule.preorder(depth + 1)

    @property
    def ancestors(self):
        if self.parent.parent:
            yield from self.parent.ancestors
            yield self.parent


class Hierarchy(dict):
    def __init__(self):
        super()
        self._root = Module("_root", None, None)
        self.toplevel = self._root.submodules
        
    def addmodule(self, name, data, submodulenames=None):
        if name in self:
            self[name].data = data
        else:
            self[name] = Module(name, data, self._root)
        for subname in submodulenames or ():
            if subname not in self:
                self[subname] = Module(subname, None, self[name])
            else:
                if self[subname].parent:
                    self[subname].parent.submodules.remove(self[subname])
                self[subname].parent = self[name]
                self[name].submodules.append(self[subname])

    def __iter__(self):
        for module in self.toplevel:
            yield from module.preorder(0)

您可以像以前一样构建您的输入：

    hierarchy = Hierarchy()
    hierarchy.addmodule("Module1", 1, ["Module2", "Module3"])
    hierarchy.addmodule("Module2", 2, ["Module4"])
    hierarchy.addmodule("Module3", 3, ["Module6", "Module7"])
    hierarchy.addmodule("Module4", 4, ["Module5"])
    hierarchy.addmodule("Module5", 5, )
    hierarchy.addmodule("Module6", 6, )
    hierarchy.addmodule("Module7", 7, )

下面是一些关于如何使用这个的例子 hierarchy:

    print("Complete hierarchy:")
    for module, depth in hierarchy:
        print("  " * depth, module.name)
    print("Which is the parent of Module4?", 
            hierarchy["Module4"].parent.name)
    print("Which are the submodules of Module4?", 
            [m.name for m in hierarchy["Module4"].submodules])
    print("Which are the top level modules?", 
            [m.name for m in hierarchy.toplevel])
    print("which are the ancestors of Module4?", 
            [m.name for m in hierarchy["Module4"].ancestors])

这将输出：

Complete hierarchy:
 Module1
   Module2
     Module4
       Module5
   Module3
     Module6
     Module7
which is the parent of Module4? Module2
which are the submodules of Module4? ['Module5']
which are the top level modules? ['Module1']
which are the ancestors of Module4? ['Module1', 'Module2']

从对象列表构建 tree/linked 列表

Build tree/linked list from a list of Objects

python

tree

linked-list

list

data-structures