Vee Cee Vee Cee - 4 months ago 15
Python Question

Recursively finding an ID's child and its underlying children

I created a table with two columns, "TOP" and "UNDER". TOP is the parent column with unique IDs, and UNDER contains underlying ID's, separated by ","s. The items in UNDER can also be a parent listed in the "TOP" column.

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


I'm trying to create a function that will return all of a TOP's UNDER characters. ie: foo("C") = [E, V, M, F, G]. E has V, M. F has G. I'm lost on how to implement the recursion part. Everytime I try to implement it, I get an infinite loop.

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 will contain the current UNDER value. ie foo("D"), under_list = [X, Y, Z]. I then append each element to the result_list.

Am I approaching the problem/implementing it the wrong way? Could I have some help doing it correctly? I've been googling for hours, but I can't seem to word my search accurately enough to find a guide or solution. Thank you so much!

Answer

EDIT

Modified to handle cycles in the graph. ("TOP" and "UNDER" made me think this was a tree, but perhaps that's not a guarantee.)

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