Rekursives Suchen eines untergeordneten ID-Elements und der ihm untergeordneten Elemente

Question

Ich habe eine Tabelle mit zwei Spalten erstellt, "TOP" und "UNDER". TOP ist die übergeordnete Spalte mit eindeutigen IDs und UNDER enthält zugrunde liegende IDs, getrennt durch "," s. Die Elemente in UNDER können auch ein übergeordnetes Element in der Spalte "TOP" sein.

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

Ich versuche, eine Funktion zu erstellen, die alle Unterzeichen eines TOPs zurückgibt. d.h. foo ("C") = [E, V, M, F, G]. E hat V, M. F hat G. Ich bin verloren, wie ich den Rekursionsteil implementiere. Jedes Mal, wenn ich versuche, es zu implementieren, bekomme ich eine Endlosschleife.

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 enthält den aktuellen UNDER-Wert. d.h. foo ("D"), under_list = [X, Y, Z]. Ich füge dann jedes Element an die result_list an.

Bin ich auf das Problem/die Umsetzung falsch? Könnte ich Hilfe dabei haben, es richtig zu machen? Ich habe stundenlang gegoogelt, aber ich kann meine Suche nicht genau genug beschreiben, um einen Leitfaden oder eine Lösung zu finden.

Answer 1

EDIT

Modifizierte Zyklen in dem Graphen zu handhaben. ("TOP" und "UNDER" ließen mich denken, dass dies ein Baum war, aber vielleicht ist das keine Garantie.)

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'}