Meaning of the word Looping dictionary

Question

I currently have a program that reads a text file and responds to a set of requests based on the input inside. This helps to find out which of the mothers of the children is being questioned. Now I do it one step and process these outputs to display the complete family tree.

This is a text file containing parents on the left and children on the right. Below are the requested queries, followed by the exits.

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 can decide who the mother is (thanks to Kampu for his help), but now I’m trying to figure out how to accept this value and possibly add it to a new list or dictionary, where it is endless to find 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 still have, where REVERSE_MAP has every child associated with a parent in a dictionary. Then I put my parents on a new list, which I plan to launch again to find out who their parents are. I am stuck at this point, however, because I cannot find an elegant way to complete this whole process without creating three new lists to continue the loop. The method that he is setting at the moment, I assume that I will need to either add them through a for loop, or simply split() values ​​after that, to save all the values ​​with each other. Ideally, I would like to learn how to quote this process and find out which of them asks a question about their ancestors.

It seems to me that I understand how this should look, but my knowledge of Python does not allow the effective use of trial and error.

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 explains, a tree (or something similar to it) is a good choice. The answer I am posting is a completely different path 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. A parent is not a name except for another Person object! (Kinda as a linked list). Then you can save the collection of people as a single list.

When analyzing a file, you add people to the list and at the same time update their child / parent attributes with the correct objects.

Later, given any person, it’s just a matter of printing attributes to look for links

The following is a possible implementation (On Python-2.6). The text file in this case contains only relationships. Queries are later run 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 '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 want everything to be simple, here is a way to use dictionaries (one dictionary) to do what you want

The main idea is as follows. You analyze the file to create a dictionary, where the key is Mother , and the values ​​are 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 returns the key if it is found. If mom is not 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 will only need to repeat this process until 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 in such a way that first there is all the relationships, then an empty 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 entering your sample

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

EDIT2

If you really want to break it down into functions, this is 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 used ANCESTOR_LIST_ADD assumes that it is defined as:

 global ANCESTOR_LIST_ADD ANCESTOR_LIST_ADD = [] 

If so, and ANCESTOR_LIST_ADD is global, you can simply call recursion and populate the ancestors until they appear:

 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 a local variable, you 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 

Not tested, but the general idea is to use recursion.