Build tree/linked list from a list of Objects

Question

I am trying to build a tree like hierarchy from modules and their respective submodules, each module has a name, data, and a list of its submodules,

@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()

With this code I'm able to detect if something is a submodule of something else but I don't know how I am supposed to form the connections/build the data structure.

My desired output should look something like this:

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

I tried using Anytree and Treelib to achieve this for an arbitrary amount of modules but I could not come up with a working solution. Although this problem looks simple (might not be) I just can not figure it out.

Cheers!

"I tried using Anytree and Treelib to achieve this": your code works (if you import dataclass and field from dataclasses), so what do you mean with achieving "this"? — trincot
– trincot, Commented Jun 2, 2022 at 9:12
I dont know how I'm supposed to actually build the tree structure from the Data i have, that's what I'm trying to achieve. — Dav7538
– Dav7538, Commented Jun 2, 2022 at 9:29

trincot · Accepted Answer · 2022-06-02 13:58:08Z

1

Your data structure already represents a hierarchy, but you could also store the reference of a module's parent, and have a container class Hierarchy with which to facilitate access to functionality.

I would name the class Module with a capital M, and in submodules store references to Module instances instead of strings. The container Hierarchy class could act as a dictionary so to give access to Module instance by their name.

Here is a proposal:

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)

You could build your input much like you did before:

    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, )

Here are then some examples on how to use this 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])

This will output:

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']

edited Jun 2, 2022 at 13:58

answered Jun 2, 2022 at 10:42

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Dav7538 Over a year ago

I understand what you mean very clearly thank you! But how would I go about transforming my list of modules so that it represents the scheme you are showing me (the one in the first code snipped of yours)?

trincot Over a year ago

Can you clarify? Do you want to keep your data structure and only get this output? Do you want to keep your data structure, and create a second data structure from it? Do you want a different way to create a data structure? But then based on which input?

Dav7538 Over a year ago

Thank you for your patients! So my input is the List of Module Objects, and I want to make a hierarchy from it, which I could walk through and receive data from a selected module in this hierarchy.

trincot Over a year ago

"which I could walk through": which kind of walks you have in mind? Can you be specific which possibilities you want to have, possibly based on a given module name or module instance?

Dav7538 Over a year ago

for example I could retrieve data from module2 ( 2 in this case) , return what its parent module is (Module 1 in this case), return what its child/submodules are ( module 4 in this case) and print out the whole hierarchy structure like in the example you showed me right now.

|

Collectives™ on Stack Overflow

Build tree/linked list from a list of Objects

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related