Looping dictionary values

Question

I currently have a program which reads a text file and answers a set of queries based on the input inside. It serves to figure out who the mothers are of the children questioned. I'm now taking it one step further and reprocessing these outputs provided to display a full family tree.

This is the text file containing the parents on the left hand side and the kids on the right. Below that are the queries being asked, which are to be followed by the outputs.

Sue: Chad, Brenda, Harris
Charlotte: Tim
Brenda: Freddy, Alice
Alice: John, Dick, Harry

mother Sue
ancestors Harry
ancestors Bernard
ancestors Charlotte

>>> Mother not known
>>> Alice, Brenda, Sue
>>> Unknown Person
>>> No known ancestors

The program is able to work out who the mother is (Thanks to Kampu for his help) but I'm now trying to understand how to then take this value and perhaps append it to a new list or dictionary where it is indefinitely looped to find any possible grandparents.

def lookup_ancestor(child):
    ancestor = REVERSE_MAP.get(child)
    if ancestor:
        ANCESTOR_LIST_ADD.append(ancestor)
    if ancestor not in LINES[0:]:
        print("Unknown person")
    else:
        print("No known ancestors")

This is what I have so far, where REVERSE_MAP has each child mapped to their parent in a dictionary. I'm then placing the parents into a new list which I plan to run again to figure out who their parents are. I'm stuck at this point however as I can't find an elegant way to perform this whole process without creating three new lists to keep looping over. The way it's setup at the moment, I'm assuming I'd need to either append them via a for loop or just split() the values afterwards to keep all the values with each other. Ideally, I'd like to learn how to loop this process and find out who each questions ancestors are.

I feel as if I have a grasp on how it should possibly look but my knowledge of Python prevents my trial and error method from being time efficient..

Any help would be greatly appreciated!

EDIT: Link - http://pastebin.com/vMpT1GvX

EDIT 2:

def process_commands(commands, relation_dict):
    '''Processes the output'''
    output = []
    for c in commands: 
        coms = c.split()
        if len(coms) < 2: 
            output.append("Invalid Command")
            continue
        action = coms[0]
        param = coms[1]

def mother_lookup(action, param, relation_dict):
    output_a = []
    if action == "mother": 
        name_found = search_name(relation_dict, param)
        if not name_found: 
            output_a.append("Unknown person")
        else: 
            person = find_parent(relation_dict, param)
            if person is None: 
                output_a.append("Mother not known")
            else: 
                output_a.append(person)
    return output_a

def ancestor_lookup(action, param, relation_dict):
    output_b = []
    if action == "ancestors": 
        name_found = search_name(relation_dict, param)
        if not name_found: 
            output_b.append("Unknown person")
        else: 
            ancestor_list = []
            person = param
            while True: 
                person = find_parent(relation_dict, person)
                if person == None: 
                    break
                else: 
                    ancestor_list.append(person)
                if ancestor_list: 
                    output_b.append(", ".join(ancestor_list))
                else: 
                    output_b.append("No known ancestors")
    return output_b

def main():
    '''Definining the file and outputting it'''
    file_name = 'relationships.txt'
    relations,commands = read_file(file_name)
    #Process Relqations to form a dictionary of the type 
    #{parent: [child1,child2,...]}
    relation_dict = form_relation_dict(relations)
    #Now process commands in the file
    action = process_commands(commands, relation_dict)
    param = process_commands(commands, relation_dict)
    output_b = ancestor_lookup(action, param, relation_dict)
    output_a = mother_lookup(action, param, relation_dict)
    print('\n'.join(output_a))
    print ('\n'.join(output_b))


if __name__ == '__main__': 
    main()

Answer 1

As @NullUserException said, a tree (or something resembling it) is a good choice. The answer I am posting is quite a different track from what you have chosen for this problem.

You can define a Person object that knows its name and keeps track of who its parent is. The parent isn't a name but another Person object! (Kinda like a linked list). Then you can keep the collection of people as a single list.

While parsing the file, you keep adding people to the list while at the same time updating their children/parent attribute with the correct objects.

Later given any person, it is just a matter of printing the attributes to find relationships

The following is a possible implementation (On Python-2.6). The text file in this case contains just the relationships. The queries are later fired using interactive input

class Person(object): 
    """Information about a single name"""
    def __init__(self,name): 
        self.name = name
        self.parent = None
        self.children = []

def search_people(people,name): 
    """Searches for a name in known people and returns the corresponding Person object or None if not found"""
    try: 
        return filter(lambda y: y.name == name,people)[0]
    except IndexError: 
        return None

def search_add_and_return(people,name): 
    """Search for a name in list of people. If not found add to people. Return the Person object in either case"""
    old_name = search_people(people,name)
    if old_name is None: 
        #First time entry for the name
        old_name = Person(name)
        people.append(old_name)
    return old_name

def read_file(file_name,people): 
    fp = open(file_name,'r')
    while True: 
        l = fp.readline()
        l.strip('\n').strip()
        if not l: 
            break
        names = l.split(':')
        mother = names[0].strip()
        children = [x.strip() for x in names[1].split(',')]
        old_mother = search_add_and_return(people,mother)
        #Now get the children objects
        child_objects = []
        for child in children: 
            old_child = search_add_and_return(people,child)
            child_objects.append(old_child)
        #All children have been gathered. Link them up
        #Set parent in child and add child to parent's 'children'
        old_mother.children.extend(child_objects)
        for c in child_objects: 
            c.parent = old_mother
    fp.close()


def main(): 
    file_name = 'try.txt'
    people = []
    read_file(file_name,people)

    #Now lets define the language and start a loop
    while True: 
        command = raw_input("Enter your command or 0 to quit\n")
        if command == '0': 
            break
        coms = command.split()
        if len(coms) < 2: 
            print "Wrong Command"
            continue
        action = coms[0]
        param = coms[1]
        if action == "mother": 
            person = search_people(people,param)
            if person == None: 
                print "person not found"
                continue
            else: 
                if person.parent is None: 
                    print "mother not known"
                else: 
                    print person.parent.name
        elif action == "ancestors": 
            person = search_people(people,param)
            if person == None: 
                print "person not found"
                continue
            else: 
                ancestor_list = []
                #Need to keep looking up parent till we don't reach a dead end
                #And collect names of each ancestor
                while True: 
                    person = person.parent
                    if person is None: 
                        break
                    ancestor_list.append(person.name)
                if ancestor_list: 
                    print ",".join(ancestor_list)    
                else: 
                    print "No known ancestors"

if __name__ == '__main__': 
    main()

EDIT

Since you would like to keep things simple, here is a way of using dictionaries (a single dictionary) to do what you want

The basic idea is following. You parse the file to form a dictionary where the key is Mother and the values is list of children. So When your sample file is parsed, you get a dictionary like

relation_dict = {'Charlotte': ['Tim'], 'Sue': ['Chad', 'Brenda', 'Harris'], 'Alice': ['John', 'Dick', 'Harry'], 'Brenda': ['Freddy', 'Alice']}

To find a parent simply search if the name is in dictionary values and return the key if found. If no mother is found, return None

mother = None
for k,v in relation_dict.items(): 
    if name in v: 
        mother = k
        break
return mother

If you want to find all the ancestors, you'll only need to repeat this process till None is returned

ancestor_list = []
person = name
while True: 
    person = find_parent(relation_dict,person)
    if person == None: 
        #Top of the ancestor chain found
        break
    else: 
        ancestor_list.append(person)

Here's an implementation in Python-2.6. It assumes that your text file is structured such that first there are all the relations, then a blank line and then all the commands.

def read_file(file_name): 
    fp = open(file_name,'r')
    relations = []
    commands = []
    reading_relations = True
    for l in fp: 
        l = l.strip('\n')
        if not l: 
            reading_relations = False
            continue
        if reading_relations:     
            relations.append(l.strip())
        else: 
            commands.append(l.strip())
    fp.close()
    return relations,commands

def form_relation_dict(relations): 
    relation_dict = {}
    for l in relations: 
        names = l.split(':')
        mother = names[0].strip()
        children = [x.strip() for x in names[1].split(',')]
        existing_children = relation_dict.get(mother,[])
        existing_children.extend(children)
        relation_dict[mother] = existing_children
    return relation_dict

def search_name(relation_dict,name): 
    #Returns True if name occurs anywhere in relation_dict
    #Else return False
    for k,v in relation_dict.items(): 
        if name ==k or name in v: 
            return True
    return False

def find_parent(relation_dict,param): 
    #Finds the parent of 'param' in relation_dict
    #Returns None if no mother found
    #Returns mother name otherwise
    mother = None
    for k,v in relation_dict.items(): 
        if param in v: 
            mother = k
            break
    return mother

def process_commands(commands,relation_dict): 
    output = []
    for c in commands: 
        coms = c.split()
        if len(coms) < 2: 
            output.append("Invalid Command")
            continue
        action = coms[0]
        param = coms[1]
        if action == "mother": 
            name_found = search_name(relation_dict,param)
            if not name_found: 
                output.append("person not found")
                continue
            else: 
                person = find_parent(relation_dict,param)
                if person is None: 
                    output.append("mother not known")
                else: 
                    output.append("mother - %s" %(person))
        elif action == "ancestors": 
            name_found = search_name(relation_dict,param)
            if not name_found: 
                output.append("person not found")
                continue
            else: 
                #Loop through to find the mother till dead - end (None) is not reached
                ancestor_list = []
                person = param
                while True: 
                    person = find_parent(relation_dict,person)
                    if person == None: 
                        #Top of the ancestor found
                        break
                    else: 
                        ancestor_list.append(person)
                if ancestor_list: 
                    output.append(",".join(ancestor_list))
                else: 
                    output.append("No known ancestors")
    return output

def main(): 
    file_name = 'try.txt'
    relations,commands = read_file(file_name)
    #Process Relqations to form a dictionary of the type {parent: [child1,child2,...]}
    relation_dict = form_relation_dict(relations)
    print relation_dict
    #Now process commands in the file
    output = process_commands(commands,relation_dict)
    print '\n'.join(output)


if __name__ == '__main__': 
    main()

Output for your sample input is

mother not known
Alice,Brenda,Sue
person not found
No known ancestors

EDIT2

If you really want to split it further into functions, here's how process_commands should look

def process_mother(relation_dict,name): 
    #Processes the mother command
    #Returns the ouput string
    output_str = ''
    name_found = search_name(relation_dict,name)
    if not name_found: 
        output_str = "person not found"
    else: 
        person = find_parent(relation_dict,name)
        if person is None: 
            output_str = "mother not known"
        else: 
            output_str = "mother - %s" %(person)
    return output_str

def process_ancestors(relation_dict,name): 
    output_str = ''
    name_found = search_name(relation_dict,name)
    if not name_found: 
        output_str = "person not found"
    else: 
        #Loop through to find the mother till dead - end (None) is not reached
        ancestor_list = []
        person = name
        while True: 
            person = find_parent(relation_dict,person)
            if person == None: 
                #Top of the ancestor found
                break
            else: 
                ancestor_list.append(person)
        if ancestor_list: 
            output_str = ",".join(ancestor_list)
        else: 
            output_str = "No known ancestors"
    return output_str

def process_commands(commands,relation_dict): 
    output = []
    for c in commands: 
        coms = c.split()
        if len(coms) < 2: 
            output.append("Invalid Command")
            continue
        action = coms[0]
        param = coms[1]
        if action == "mother": 
            new_output = process_mother(relation_dict,param)
        elif action == "ancestors": 
            new_output = process_ancestors(relation_dict,param)
        if new_output: 
            output.append(new_output)    
    return output

Answer 2

The way you have used ANCESTOR_LIST_ADD suggests that it's defined as:

global ANCESTOR_LIST_ADD
ANCESTOR_LIST_ADD = []

If that is the case and ANCESTOR_LIST_ADD is global, you can just call the recursion and it will fill in ancestors until there are any:

def lookup_ancestor(child):
    ancestor = REVERSE_MAP.get(child)
    if ancestor:
        ANCESTOR_LIST_ADD.append(ancestor)
        lookup_ancestor(ancestor) #recursion
    if ancestor not in LINES:
        print("Unknown person")
    else:
        print("No known ancestors")

if ANCESTOR_LIST_ADD is local variable, you will need to pass it as part of the call:

def lookup_ancestor(child, ANCESTOR_LIST_ADD):
    ancestor = REVERSE_MAP.get(child)
    if ancestor:
        ANCESTOR_LIST_ADD.append(ancestor)
        return lookup_ancestor(ancestor, ANCESTOR_LIST_ADD) #recursion
    if ancestor not in LINES:
        print("Unknown person")
    else:
        print("No known ancestors")
    return ANCESTOR_LIST_ADD

Haven't tested it, but the general idea is to use recursion.