Как сделать обход в глубину на основе файловой системы?

Question

[ArtemZA]

Здравствуйте. пытаюсь реализовать обход графа в глубину на основе файловой системы, но ничего не получается.
Граф из папок

import glob
import os
import codecs
import time

node = {}
spisok = []
visited = []

def filegraph(start, last ):
    if start not in visited:
        spisok.clear()
        names = os.listdir(start)
        visited.append(start)
        
       #print(visited)
        print(start , ' Текущая директория')
        #print(os.getcwd())
        print(last , ' Последняя директория')
        
        for name in names:
            directory = os.path.join(start, name)            
            if os.path.isdir(directory) == True:
                spisok.append(directory)
                print(directory , 'директория')
        print( spisok ,  ' список')
        
        print(last)
        node[start] = last , spisok #Добавляем в словарь
        try:
            print(node[last] , ' last' )
        except KeyError:
            print(' Ключа нет')
        print(node[start] , ' start')
        #print(node ,  ' node')
        if len(spisok) != 0:
            for a in range(0 , len(spisok)):
                if node[start][1][a] not in visited:
                    
                    time.sleep(3)
                    os.chdir(node[start][1][a])
                    for key in node:
                        print('%s -> %s' % (key , node[key]) , end = ' \n')
                    print(node[start][1][a] , ' start ' , '-' * 10 )
                    return filegraph(node[start][1][a] ,start)
                
        else:
            time.sleep(3)
            print(' Возвращение ' )
            print(node[start][0] , ' start  0' )
            for key in node:
                print('%s -> %s' % (key , node[key]) , end = ' \n')

            return filegraph(node[start][0] , '')
    elif start in visited:
        print( visited , ' visited')
        print(node)
        for key in node:
                print('%s -> %s' % (key , node[key]) , end = ' \n')
        print(start , ' Посещено')
        #print(node[u'D:\\Project\\test\\First '])



filegraph(u"D:\\Project\\test" , '' )

Что удалось достичь:
Алгоритм доходит только до конца одной ветки

Что не так:
Пытаюсь хранить вершины в словаре, но заметил что почти с самого начала словарь перезаписывается и вернутся на уровень выше благодаря словарю не получается.

D:\Project\test  Текущая директория
  Последняя директория
D:\Project\test\First директория
D:\Project\test\Second директория
D:\Project\test\Three директория
['D:\\Project\\test\\First', 'D:\\Project\\test\\Second', 'D:\\Project\\test\\Three']  список

 Ключа нет
('', ['D:\\Project\\test\\First', 'D:\\Project\\test\\Second', 'D:\\Project\\test\\Three'])  start
D:\Project\test -> ('', ['D:\\Project\\test\\First', 'D:\\Project\\test\\Second', 'D:\\Project\\test\\Three']) 
D:\Project\test\First  start  ----------
D:\Project\test\First  Текущая директория
D:\Project\test  Последняя директория
D:\Project\test\First\1-2 директория
['D:\\Project\\test\\First\\1-2']  список
D:\Project\test
('', ['D:\\Project\\test\\First\\1-2'])  last
('D:\\Project\\test', ['D:\\Project\\test\\First\\1-2'])  start
D:\Project\test -> ('', ['D:\\Project\\test\\First\\1-2']) 
D:\Project\test\First -> ('D:\\Project\\test', ['D:\\Project\\test\\First\\1-2']) 
D:\Project\test\First\1-2  start  ----------

Подскажите пожалуйста что можно сделать?

Comments

[Dimonchik]

ничего не понятно, разбайте вопрос на части

[Astrohas]

Вам нужны только каталоги?

Answer 1

[tsarevfs]

Для реальной задачи используйте os.walk.
Пробел после запятой -- зло!

def filegraph(current, last):
    
    if current in visited:
        print( visited, ' visited')
        print(node)
        for key in node:
                print('%s -> %s' % (key, node[key]), end = ' \n')
        print(current, ' Посещено')
        return #*Сразу выходим, чтобы уменьшить вложенность кода*

    #spisok.clear()
    current_dir_items = [] #*это список файлов в текущей директории, то что он был глобальным создавало проблемы ниже*

    names = os.listdir(current)
    visited.append(current)
    
    print(current, ' Текущая директория')
    print(last, ' Последняя директория')
    
    for name in names:
        directory = os.path.join(current, name)            
        if os.path.isdir(directory) == True:
            current_dir_items.append(directory)
            print(directory, 'директория')
    print( current_dir_items,  ' список')
    
    print(last)
    node[current] = last, current_dir_items #Добавляем в словарь !!!список не копируется, мы помещаем в словарь ссылку на него!!!
    
    if (last in node) #*логика на исключениях -- плохая идея*
        print(node[last], ' last' )
    else
        print(' Ключа нет')

    print(node[current], ' current')
    if len(current_dir_items) != 0:
        #for a in range(0, len(current_dir_items)):
        #    if node[current][1][a] not in visited:
        for next_item in current_dir_items: #*по возможности не используйте for in range(len)*
            if next_item not in visited: 
                time.sleep(3) 
                os.chdir(next_item) #*код становится проще*
                for key in node:
                    print('%s -> %s' % (key, node[key]), end = ' \n')
                print(next_item, ' current ', '-' * 10 )
                return filegraph(next_item, current) #тут происходил spisok.clear() и портил вам данные в словаре. 
            
    else:
        time.sleep(3)
        print(' Возвращение ' )
        print(node[current][0], ' current  0' )
        for key in node:
            print('%s -> %s' % (key, node[key]), end = ' \n')

        return filegraph(node[current][0], '')

Comments

[ArtemZA]

Спасибо за развёрнутый ответ.Насчёт os.walk знаю,но хотелось попробовать сделать своё.
Подскажите пожалуйста как можно обходить папки всей ветви,а так же переходить на уровень выше и не попадать в бесконечный цикл?
Насчёт словаря,если я правильно понял,получается каждый раз когда происходил вызов функции, в словарь добавлялась всё та же ссылка на глобальный список, который я впоследствии очищал?

[tsarevfs]

Да, я пропустил этот момент.
return filegraph(next_item, current)
Вот тут вы выходите, сразу после того как проверили один путь (Test->First->"1-2"->"1-3-1").
for next_item in current_dir_items
Получается что этот цикл выполняется не более 1 раза. А это не то что мы ожидаем.
Убираем return, и все становится лучше.
Бесконечного цикла возникнуть не должно, поскольку мы отмечаем посещенные папки как visited и не будем второй раз заходить в них.
Более того, если у нас нет линков на папки выше по дереву (в общем случае они могут быть), даже без visited все должно быть хорошо, так как мы делаем рекурсивные вызовы только для не visited детей.

[ArtemZA]

tsarevfs, Спасибо вам большое

Answer 2

[Astrohas]

Лучше всего использовать что-то типа os.walk
А для того чтобы получить словарь можно использовать следующее:

import os
from functools import reduce

def get_struct(rootdir):

    dir = {}
    rootdir = rootdir.rstrip(os.sep)
    start = rootdir.rfind(os.sep) + 1
    for path, dirs, files in os.walk(rootdir):
        folders = path[start:].split(os.sep)
        subdir = dict.fromkeys(files)
        parent = reduce(dict.get, folders[:-1], dir)
        parent[folders[-1]] = subdir
    return dir

вывод:

>>>pprint.pprint(get_struct("/home/hasan/Загрузки"), indent=4)
{   'Загрузки': {   '.directory': None,
                    'CS15Setup.exe': None,
                    'CrossOver 16.2.5': {   'Crack': {   'winewrapper.exe.so': None},
                                            'CrossOver 16.2.5.md5': None,
                                            'crossover-16.2.5-1.rpm': None,
                                            'crossover_16.2.5-1.deb': None,
                                            'install-crossover-16.2.5.bin': None},
                    'Effective_Python_proglib.pdf.crdownload': None,
                    'Grokaem_algoritmy_Illyustrirovannoe_posobie_dlya_pr.rar': None,
                    'Hodyachij.zamok.2004.DUAL.BDRip.XviD.AC3.-HQCLUB.avi': None,
                    'IDM-6.28.17': {   'IDM-6.28.17.exe': None,
                                       'Тихая установка.cmd': None},
                    'IDM-6.28.17.zip': None,
                    'IMG_20171002_102640.jpg': None,
                    'IMG_20171002_102653.jpg': None,
                    'IMG_20171006_213030.jpg': None,
                    'IMG_20171009_185922.jpg': None,
                    'IMG_20171009_185934.jpg': None,
                    'IMG_20171009_205812.jpg': None,
                    'IMG_20171009_210242.jpg': None,
                    'IMG_20171009_210311.jpg': None,
                    'IMG_20171009_210355.jpg': None,
                    'Postroenie_sistem_mashinnogo_obuchenia_na_yazyke_Python.zip': None,
                    'SIMS3_Repack.iso': None,
                    'TORRENT': {},
                    '[rutor.is]Hodyachij.zamok.2004.DUAL.BDRip.XviD.AC3.-HQCLU.torrent': None,
                    '[rutor.is]SIMS3_Repack.torrent': None,
                    '[rutor.is]Teoriya.Bolshogo.Vzriva.(5.sezon.01-24.serii.iz.torrent': None,
                    '[rutor.is]The Big Bang Theory.s05.torrent': None,
                    '[rutor.is]Zakljate._Nashi_dni_The_Crucifixion_2017_WEB-DL.torrent': None,
                    'payeer_mastercard_ru.pdf': None,
                    'risovach.ru.jpg': None,
                    'selecttv_latest_07_09_2017.apk': None,
                    'st_7972_1b.jpg': None,
                    'thenightmarebeforechristmas19933d720pblurayx264ytsag-english-110597': {   'The Nightmare Before Christmas en.srt': None},
                    'thenightmarebeforechristmas19933d720pblurayx264ytsag-english-110597.zip': None,
                    'Не подтвержден 741176.crdownload': None,
                    'Силен Д., Мейсман А. - Основы Data Science и Big Data. Python и наука о данных - 2017.PDF': None}}

Comments

[ArtemZA]

Спасибо за ответ. Скажите пожалуйста, в вашем примере цикл for выводит файлы и папки только из одной папки или из всей ветви?

[Astrohas]

ArtemZA, он идет по всем элементам включая подпапаок