How can I create nested folders with attributes in python?

Question

I'm a beginner programmer, and I just started learning about Nested lists and dictionaries. I have a task to create a system of files, with class Directory and it's attributes.

class Directory:
    def __init__(self, name: str, parent: Optional['Directory'], children: List[Optional['Directory']]):
        self.name = name
        self.parent = parent
        self.children = children

I'm supposed to build a function to create this system of files recursively, given root and it's directories from dictionary. Parent is a directory which includes current dir as one of his children. Any dir which doesn't have any children is supposed to be an empty directory.

    "root": ["dirA", "dirB"],          
    "dirA": ["dirC"],
    "dirC": ["dirH", "dirG"],
    "dirB": ["dirE"]
    "dirG": ["dirX", "dirY"]}

I've been trying to do this and I think I know how to create directories recursively, however I have no idea what to put in dir.parent place without any additional imports. With root, there's no problem because it is None but further in process I don't know how to place child's parent (which is supposed to be Directory) as one of his attributes since I'm going recursively from there. Do you have any idea how to do that? Here's code which I have so far:

def create_system(system: Dict[str, List[str]], parent_children: List[str]) -> Optional[List[Optional['Directory']]]:
    children: List[Optional['Directory']] = []
    for child in parent_children:
        if child in system.keys():
            children.append(Directory(child, parent, create_system(system, list(system.get(child)))))
        else:
            children.append(Directory(child, parent, []))
    return children

def root(system: Dict[str, List[str]]) -> Optional['Directory']:
    return Directory("root", None, create_system(system, list(system.get("root"))))

Thank you for any responses!

Answer 1

Your goal is to transform the dictionary

system = {
    "root": ["dirA", "dirB"],          
    "dirA": ["dirC"],
    "dirC": ["dirH", "dirG"],
    "dirB": ["dirE"]
    "dirG": ["dirX", "dirY"]
}

into the following tree:

            root
           /    \
        dirA    dirB
        /         \
      dirC        dirE
     /   \
   dirH  dirG
         /   \
       dirX  dirY

Hopefully, it's clear that the return value of the process can be just the root. To guarantee that you hit every folder only after its parent has been created, you can use either a stack-based BFS approach, or a recursive DFS approach.

Let's look at a simple BFS approach:

def create_system_bfs(system):
    root = Directory('root', None, [])
    stack = [root]  # in practice, use collections.deque([root])

    while stack:
        current = stack.pop(0)
        for child in system.get(current.name, []):
            d = Directory(child, current, [])
            current.children.append(d)
            stack.append(d)

    return root

The DFS version of that could be something like:

def create_system_dfs(system):
    def create_node(name, parent):
        d = Directory(name, parent, [])
        d.children = [create_node(child, d) for child in system.get(name, [])]
        return d
    return create_node('root', None)

Keep in mind that there are other possible approaches. In both cases, the create_root method is completely unnecessary. The BFS approach is limited only by available heap memory. The DFS approach may also be limited by stack size.

Answer 2

Before get all tangled up in classes we can think in terms of an ordinary function -

def paths(t, init="root"):
  def loop(q, path):
    if isinstance(q, dict):
      for (dir, v) in q.items():
        yield from loop(v, [*path, dir])
    elif isinstance(q, list):
      for dir in q:
        yield from loop \
          ( t[dir] if dir in t else None
          , [*path, dir]
          )
    else:
      yield "/".join(path)
  yield from loop(t[init], ["."])

Using paths is easy, simply call it on your input tree -

input = {
  "root": ["dirA", "dirB"],          
  "dirA": ["dirC"],
  "dirC": ["dirH", "dirG"],
  "dirB": ["dirE"],
  "dirG": ["dirX", "dirY"]
}

for path in paths(input):
  print(path)

./dirA/dirC/dirH
./dirA/dirC/dirG/dirX
./dirA/dirC/dirG/dirY
./dirB/dirE

Using paths allows us to easily create the directories we need -

import os

for path in paths(input):
  os.makedirs(path)

Answer 3

This is an opportunity to learn about reusable modules and mutual recursion. This solution in this answer solves your specific problem without any modification of the modules written in another answer. The distinct advantage of this approach is that tree has zero knowledge of your node shape and allows you to define any output shape.

Below we create a tree using plain dict with name, parent, and children properties. tree does not make this choice for you. A different structure or a custom class can be used, if desired -

from tree import tree

input = {
  None: ["dirA", "dirB"],          
  "dirA": ["dirC"],
  "dirC": ["dirH", "dirG"],
  "dirB": ["dirE"],
  "dirG": ["dirX", "dirY"]
}

result = tree \
  ( flatten(input)
  , parent
  , lambda node, children:
      dict \
        ( name=name(node)
        , parent=parent(node)
        , children=children(name(node))
        )
  )

print(result)

[
  {
    "name": "dirA",
    "parent": None,
    "children": [
      {
        "name": "dirC",
        "parent": "dirA",
        "children": [
          {
            "name": "dirH",
            "parent": "dirC",
            "children": []
          },
          {
            "name": "dirG",
            "parent": "dirC",
            "children": [
              {
                "name": "dirX",
                "parent": "dirG",
                "children": []
              },
              {
                "name": "dirY",
                "parent": "dirG",
                "children": []
              }
            ]
          }
        ]
      }
    ]
  },
  {
    "name": "dirB",
    "parent": None,
    "children": [
      {
        "name": "dirE",
        "parent": "dirB",
        "children": []
      }
    ]
  }
]

In order to use tree, we defined a way to flatten the input nodes -

def flatten(t):
  seq = chain.from_iterable \
    ( map(lambda _: (_, k), v)
        for (k,v) in input.items()
    )
  return list(seq)

print(flatten(input))

[ ('dirA', None)
, ('dirB', None)
, ('dirC', 'dirA')
, ('dirH', 'dirC')
, ('dirG', 'dirC')
, ('dirE', 'dirB')
, ('dirX', 'dirG')
, ('dirY', 'dirG')
]

And we also defined the primary key and foreign key. Here we use name and parent, but you can choose whichever names you like -

def name(t):
  return t[0]

def parent(t):
  return t[1]

To learn more about the tree module and some of its benefits, see the original Q&A