Рекурсивное нахождение ребенка идентификатора и его дочерних элементов

python recursion sqlite tree

47 просмотра

1 ответ

20 Репутация автора

Я создал таблицу с двумя столбцами, «TOP» и «ПОД». TOP - это родительский столбец с уникальными идентификаторами, а UNDER содержит базовые идентификаторы, разделенные символами ",". Элементы в UNDER также могут быть родителями, перечисленными в столбце «TOP».

TOP     UNDER
----    --------
A       B
B       C,D
C       E,F
D       X,Y,Z
Z       J,K,L
E       V,M
F       G

Я пытаюсь создать функцию, которая будет возвращать все символы под ТОПом. т.е.: foo ("C") = [E, V, M, F, G]. E имеет V, M. F имеет G. Я заблудился о том, как реализовать рекурсивную часть. Каждый раз, когда я пытаюсь это реализовать, я получаю бесконечный цикл.

import sqlite3  
conn = sqlite3.connect("myTable.db") #Conn is a connection object that reps the db
conn.row_factory = sqlite3.Row #access columns of a query by name instead of index 
cursor = conn.cursor()   
id="C"    
cursor.execute("select * from myTable where id='%s'" %id)

def get_underlying(under_list, result_list=[]):
    if len(under_list) == 0:
        return result_list

    print("Query results for: select * from myTable where id='%s'" %(id))
    cursor.execute("select * from myTable where id='%s'" %id)
    r = cursor.fetchall()

    if r == []:
        return result_list

    under_list = r[0]['UNDER'].split(",") 
    for c in under_list:
        result_list.append(c)

    #???? lost on what to write
    if len(r) == 0:
        return
    elif len(r) == 1:
        return
    else
        return

print get_underlying("C")

Under_list будет содержать текущее значение UNDER. т.е. foo ("D"), under_list = [X, Y, Z]. Затем я добавляю каждый элемент в список результатов.

Я подхожу к проблеме / реализую ее неправильно? Могу ли я получить помощь, чтобы сделать это правильно? Я часами гуглял, но не могу достаточно точно сформулировать свой поиск, чтобы найти руководство или решение.

Автор: Vee Cee Источник Размещён: 18.07.2016 11:49

Ответы (1)


2 плюса

51015 Репутация автора

Решение

РЕДАКТИРОВАТЬ

Модифицировано для обработки циклов на графике. («TOP» и «ПОД» заставили меня думать, что это дерево, но, возможно, это не гарантия.)

from __future__ import print_function
import sqlite3

conn = sqlite3.connect('myTable.db')
conn.row_factory = sqlite3.Row
c = conn.cursor()

def initialize():
    c.execute('create table myTable (ID text, UNDER text)')

    data = [
        ['A', 'B'],
        ['B', 'C,D'],
        ['C', 'E,F'],
        ['D', 'X,Y,Z'],
        ['Z', 'J,K,L'],
        ['E', 'V,M'],
        ['F', 'G,C'], # note the cycle!
    ]

    for top, under in data:
        c.execute('insert into myTable values (?, ?)', (top, under))

    conn.commit()

def get_all_reachable(node_id, found=None):
    if found is None:
        found = set()

    c.execute('select * from myTable where id=?', (node_id,))
    rows = c.fetchall()

    if len(rows) == 0:
        return []

    for child in rows[0]['UNDER'].split(','):
        if child not in found:
            found.add(child)
            get_all_reachable(child, found)

    return found

if __name__ == '__main__':
    initialize()
    print(get_all_reachable('C'))

# Output:
# {'V', 'C', 'M', 'G', 'F', 'E'}
Автор: user94559 Размещён: 19.07.2016 12:12
Вопросы из категории :
32x32