Have fun with graph folder structure

folder_fun.py

from collections import deque

'''
Graph problems
A
    C
        E
            F
    D
        G
    H
B
    I
    K
    L
        M
            N
'''

folder_rels = (
    (None, 'A'),
    ('A', 'C'),
    ('C', 'E'),
    ('E', 'F'),
    ('A', 'D'),
    ('D', 'G'),
    ('A', 'H'),
    (None, 'B'),
    ('B', 'I'),
    ('B', 'K'),
    ('B', 'L'),
    ('L', 'M'),
    ('M', 'N'),
)


class FolderUtil:
    def __init__(self, folder_rels):
        parent_children = {}
        parents = {}
        for parent, child in folder_rels:
            if parent not in parent_children:
                parent_children[parent] = [child]
            else:
                parent_children[parent].append(child)
            parents[child] = parent
        self.parent_children = parent_children
        self.parents = parents


    def expand_access(self, access: set) -> set:
        """Expand eccess to deeper level"""
        expanded = set()  # Store children only
        queue = deque(access)
        visited = set()
        while queue:
            folder = queue.popleft()
            if folder in visited:
                continue
            visited.add(folder)
            for child in self.parent_children.get(folder, []):
                expanded.add(child)
                queue.append(child)
        return expanded

    def has_access(self, access, folder):
        # This should be precache somewhere
        expanded = self.expand_access(access) | access  
        return folder in expanded
    
    def has_access_without_preprocess(self, access, folder):
        node = folder
        while node:
            if node in access:
                return True
            node = self.parents.get(node)
        return False

    def clean_up_deep(self, access: set) -> set:
        """Clean up redundant access list, deep
            N: number of folders
            M: number of original access folder
            O(M*N)
        """
        return access - self.expand_access(access)

    def clean_up_access(self, access: set) -> set:
        """Clean up redundant access list
            access: set
            N: number of folders
            M: number of original access folder
            O(M) (inverse Ackermann function)
        """
        redundant = set()
        for folder in access:
            branch_redundant = set([folder])
            node = folder
            while node in self.parents:
                node = self.parents[node]
                if node in access:
                    redundant.update(branch_redundant)
                branch_redundant.add(node)
                folder = node
        return access - redundant


if __name__ == '__main__':
    util = FolderUtil(folder_rels)
    assert util.expand_access({'A'}) == {'C', 'D', 'E', 'F', 'G', 'H'}
    assert util.expand_access({'E'}) == {'F'}

    assert util.has_access({'E'}, 'F')
    assert util.has_access({'F'}, 'F')
    assert util.has_access({'A'}, 'F')
    assert util.has_access({'F'}, 'A') == False
    assert util.has_access({'B'}, 'A') == False

    assert util.clean_up_access({'A', 'E', 'F'}) == util.clean_up_deep({'A', 'E', 'F'}) == {'A'}
    assert util.clean_up_access({'E', 'G', 'F', 'M', 'N'}) == util.clean_up_deep({'E', 'G', 'F', 'M', 'N'}) == {'E', 'G', 'M'}