python function to get subpaths on infinite level from single path string

Question

hi I am stuck in a program logic is I am getting paths from 3rd party api like

paths = ['path1' , 'path2']

now I have to get child of both . api will return every time just 1 step further for example If I will pass a path to it

result = get_path_from_api(path='path1')

it will result into

paths = ['path1/subpath1' , 'path1/subpath2']

now thing is I will stop when I will get [] from this get_path_from_api call. and I have to find for further even ['path1/subpath1' , 'path1/subpath2'] all sub paths as well and finally merge in single array.

for now my function is like

def get_subpaths(path_name):
    sub_paths = []
    print(path_name, "path_name")
    paths = get_path_from_api(path=path_name)
    for path in paths:
        if path.is_directory:
            sub_paths.append(path.name)
        sub_path_final = []
        while sub_path_final != None:
            sub_path_final = get_subpaths(path.name)
    return sub_paths if sub_paths else None

any help would be highly appreciated .

Final expected result

final = ['path1' , 'path1/subpath1' , 'path1/subpath2' , 'path2' , 'path2/subpath2' , 'path2/subpath2' , 'path3/subpath3']

`get_subpaths()` only takes one parameter, why are you calling it with 3 arguments? — Barmar, Mar 29 '23 at 19:04
@Barmar thanks for correction made program simple for stackoverlow . forget to remove extra — Shahroz Pervaz, Mar 29 '23 at 19:05
Each time through the loop you should extend `sub_paths` with the paths that are returned. — Barmar, Mar 29 '23 at 19:06
@KennyOstrom actually issue is getting all paths like from parent - then child 1 - then child of child 1 - then child 2 then child of child 2 . not able to figure how I can pass this to loop to get — Shahroz Pervaz, Mar 29 '23 at 19:06
I think you have to fully traverse it, yielding only the leaf nodes (with full path). That way you can pass it to a list constructor. Unless I misunderstood the question -- if you want all valid paths, use extend like Barmar said. (or yield them all) — Kenny Ostrom, Mar 29 '23 at 19:07
Since you said "infinite" you may have to simulate function recursion with a stack, instead, lest you hit the python recursion limit. — Kenny Ostrom, Mar 29 '23 at 19:11
@KennyOstrom from infinite I mean unless I get [] from response from api — Shahroz Pervaz, Mar 29 '23 at 19:15
@KennyOstrom updated answer . any number of path and sub paths . only api will tell where path is ending by sending empty array — Shahroz Pervaz, Mar 29 '23 at 19:27

score 1 · Answer 1 · answered Mar 29 '23 at 19:23

Rather than using recursion, it might be easier to use a queue and a while loop. That way you don't have to pass around tonnes of containers, or worry about the call stack size.

def get_subpaths(path_name):
    results = []
    search_queue = {path_name}

    while search_queue:
        search_path = search_queue.pop()
        results.append(search_path)
        print(f"{search_path=}")

        for path in get_path_from_api(path=search_path):
            if path.is_directory:
                search_queue.add(path.name)

    return results

thanks for replying . i want my output as final = ['path1' , 'path1/subpath1' , 'path1/subpath2' , 'path2' , 'path2/subpath2' , 'path2/subpath2' , 'path3/subpath3'] . but getting None — Shahroz Pervaz, Mar 29 '23 at 19:36

Kenny Ostrom · Answer 2 · 2023-03-29T20:18:19.757

from queue import deque

simulated_filesystem = {
        '': ['path1', 'path2', 'path3'],
        'path1': ['path1/subpath1', 'path1/subpath2'],
        'path2': ['path2/subpath1', 'path2/subpath2'],
        'path3': ['path3/subpath3'],
}

class ApiPathObject:
    def __init__(self, name):
        self.is_directory = True
        self.name = name
    def __repr__(self):
        return f"{self.name}"

def get_path_from_api(path) -> list[ApiPathObject]:
    return [ApiPathObject(name) for name in simulated_filesystem.get(path, [])]

def get_subpaths_bfs(path_name):
    """ generator, breadth first search, using a python list as a stack """
    paths = [path_name]
    while paths:
        for path in get_path_from_api(paths.pop()):
            if path.is_directory:
                paths.append(path.name)
                yield path.name

def get_subpaths_dfs(path_name):
    """ generator, depth first search, preorder """
    paths = deque(get_path_from_api(path_name))
    while paths:
        path = paths.popleft()
        if path.is_directory:
            yield path.name
            for subpath in reversed(get_path_from_api(path.name)):
                paths.appendleft(subpath)

def get_subpaths(path_name):
    return list(get_subpaths_dfs(path_name))

print(get_subpaths(''))
print(get_subpaths('path1'))
print(get_subpaths('path2'))

['path1', 'path1/subpath1', 'path1/subpath2', 'path2', 'path2/subpath1', 'path2/subpath2', 'path3', 'path3/subpath3']
['path1/subpath1', 'path1/subpath2']
['path2/subpath1', 'path2/subpath2']

In your expected result, you left out "path3" and you had two subpaths with the same name. Were those accidents? — Kenny Ostrom, Mar 29 '23 at 20:12
https://stackoverflow.com/questions/21571745/is-pre-order-traversal-on-a-binary-tree-same-as-depth-first-search for some additional info on how to order the results in addition to DFS vs BFS — Kenny Ostrom, Mar 29 '23 at 20:15
Is this isn't what you want, you're welcome to put my test setup code in your question, so you can demonstrate a reproducible issue. Obviously we don't have your api, but we can simulate it. — Kenny Ostrom, Mar 29 '23 at 20:42

python function to get subpaths on infinite level from single path string

2 Answers2