Python: tree structure and numerical codes?
I'm using Python and I have some data that I want to put into a tree format and assign codes to. Here's some example data:
Africa North Africa Algeria
Africa North Africa Morocco
Africa West Africa Ghana
Africa West Africa Sierra Leone
What would be an appropriate tree structure for this data?
Also, is there a way that I can then retrieve numerical codes from this tree structure, so that I could query the data and get codes like the follo开发者_开发百科wing example?
def get_code(place_name):
# Python magic query to my tree structure
return code
get_code("Africa") # returns 1
get_code("North Africa") # returns 1.1
get_code("Morocco") # returns 1.1.2
Thank you for your help - I still have much to learn about Python :)
I would recommend, assuming you can count on there being no duplication among the names, something like:
class Node(object):
byname = {}
def __init__(self, name, parent=None):
self.name = name
self.parent = parent
self.children = []
self.byname[name] = self
if parent is None: # root pseudo-node
self.code = 0
else: # all normal nodes
self.parent.children.append(self)
self.code = len(self.parent.children)
def get_codes(self, codelist):
if self.code:
codelist.append(str(self.code))
self.parent.get_codes(codelist)
root = Node('')
def get_code(nodename):
node = Node.byname.get(nodename)
if node is None: return ''
codes = []
node.get_codes(codes)
codes.reverse()
return '.'.join(codes)
Do you also want to see the Python code for how to add a node given a hierarchical sequence of names, such as ['Africa', 'North Africa', 'Morocco']
? I hope it would be pretty clear given the above structure, so you might want to do it yourself as an exercise, but of course do ask if you'd rather see a solution instead;-).
Getting the hierarchical sequence of names from a text line (string) depends on what the separators are -- in your example it looks like it's just a bunch of spaces added for purely aesthetic reasons connected with lining up the columns (if that's the case I'd recommend a simple re
based approach to split on sequence of two+ spaces), but if it's actually (e.g.) tab characters as the separators, the csv
module from Python's standard library would serve you better. I just can't tell from the short example you posted in your Q!-)
Edit: the OP says they can get the sequence of names just fine but would like to see the code to add the relevant nodes from those -- so, here goes!-)
def addnodes(names):
parent = root
for name in names:
newnode = Node.byname.get(name)
if newnode is None:
newnode = Node(name, parent)
parent = newnode
See why it's important that node names are unique, to make the above class work? Since Node.byname
is a single per-class dict
, it can record only one "corresponding node" for each given name -- thus, a name that's duplicated in two or more places in the hierarchy would "clash" and only one of the two or more nodes would be properly recorded.
But then again, the function get_code
which the OP says is the main reason for this whole apparatus couldn't work as desired if a name could be ambiguous, since the OP's specs mandate it returning only one string. So, some geographical list like
America United States Georgia
Europe Eastern Europe Georgia
(where two completely unrelated areas just happen to be both named 'Georgia'
-- just the kind of thing that unfortunately often happens in real-world geography, as the above example shows!-) would destroy the whole scheme (depending on how the specs for get_code
happen to be altered to deal with an ambiguous-name argument, of course, the class structure could surely be altered accordingly and accomodate the new, drastically different specs!).
The nice thing about encapsulating these design decisions in a class (albeit in this case with a couple of accompanying functions -- they could be elegantly be made into class methods, of course, but the OP's specs rigidly demand that get_code
be a function, so I decided that, in that case addnodes
might as well also be one!-) is that the specific design decisions are mostly hidden from the rest of the code and thus can easily be altered (as long as specs never change, of course -- that's why it's so crucial to spend time and attention defining one's API specs, much more than on any other part of design and coding!-) to refactor the internal behavior (e.g. for optimization, ease of debugging/testing, and so on) while maintaining API-specified semantics intact, and thus leaving all other parts of the application pristine (not even needing re-testing, actually, as long of course as the parts that implement the API are very thoroughly unit-tested -- not hard to do, since they're nicely isolated and stand-alone!-).
An ad-hoc POD ("plain old data") class representing a tree would do fine, something like:
class Location(object):
def __init__(self, data, parent)
self.data = data
self.parent = parent
self.children = []
Now assign/read the data
attribute, or add/remove children, perhaps with helper methods:
def add_child(self, child):
self.children.append(child)
Now, to actually divide your data into tree levels, a simple algorithm would be look at all the places with a common level-data (such as Africa) and assign them a location, then recursively for next level of data.
So, for Africa you create a location with data = Africa. Then, it will have a Location child for North Africa, West Africa and so on.
For "get the code" have a dictionary mapping each country to its location node, and use the parent links in the nodes. Traverse from the node to the top (until parent is None) at each level assigning the part of the code to be the index in the children list of the parent.
I am not sure, if I have got it right. If we keep every object in a global dict then it defeats the purpose of using a tree, which is only used to construct the numbering scheme. But the tree based representation looks something like this:
class Location(object):
allLocation = {}
def __init__(self, name):
self.name = name
self.parent = None
self.number = "0"
self.children = {}
def putChild(self, childLocation):
if childLocation.name not in self.allLocation.keys():
# Now adjust the number scheme
#if self.number is "0":
# this is root
numScheme = str(len(self.children) + 1)
childLocation.setNumber(numScheme)
# Add the child
self.children[childLocation.number] = childLocation
self.allLocation[childLocation.name] = childLocation
childLocation.parent = self
return 0
else:
return 1 # Location already a child of the current clocation
def setNumber(self, num):
if self.number is not "0":
# raise an exception, number already adjusted
pass
else:
# set the number
self.number = num
def locateChild(self, numScheme):
# Logic should be to break up the numScheme and pass the token successively
numSchemeList = []
if type(numScheme) is str:
numSchemeList = numScheme.split(".")
else:
numSchemeList = numScheme
if len(numSchemeList) >= 1:
k = numSchemeList.pop()
# if the child is available
if k in self.children.keys():
childReferenced = self.children[k]
# Is child of child required
if len(numSchemeList) >= 1:
return childReferenced.locateChild(numSchemeList)
else:
return childReferenced
else:
# No such child
return None
else:
# The list is empty , search ends here
return None
def getScheme(self, name):
if name in self.allLocation.keys():
locObj = self.allLocation[name]
return locObj.getNumScheme(name, "")
else:
return None
def getNumScheme(self, name, numScheme="0",):
if not self.parent:
return numScheme
if numScheme != "":
return self.parent.getNumScheme(name, self.number + "." + numScheme)
else:
return self.parent.getNumScheme(name, self.number )
root = Location("root")
africa = Location("Africa")
asia = Location("Asia")
america = Location("America")
root.putChild(africa)
root.putChild(asia)
root.putChild(america)
nafrica = Location("North Africa")
africa.putChild(nafrica)
nafrica.putChild(Location("Morrocco"))
obj = root.locateChild("1.1.1")
print obj.name
print root.getScheme("Morrocco")
This code can be hideous. But, I just want to paste it because I have put some time into it :)
tree = file_to_list_of_tuples(thefile)
d = {}
i = 1
for continent, region, country in tree:
if continent not in d:
d[continent] = [i, 0, 0]
i += 1
cont_code = d[continent][0]
if region not in d:
max_reg_code = max( [y for x, y, z in d.values() if x==cont_code] )
d[region] = [cont_code, max_reg_code+1 , 0]
reg_code = d[region][1]
if country not in d:
max_country_code = max( [z for x, y, z in d.values() if x == cont_code and y== reg_code] )
d[country] = [cont_code, reg_code, max_country_code+1]
def get_code(x):
print d[x]
get_code will print lists, but you can easily make them print in the format you want.
You might use itertree package (I'm the author):
from itertree import *
#1. create the tree:
root2=iTree('root')
root2.append(iTree('Africa'))
root2[0].append(iTree('North Africa'))
root2[0].append(iTree('West Africa'))
root2[0][0].append(iTree('Algeria'))
root2[0][0].append(iTree('Morocco'))
item=iTree('Ghana') # keep the item for easier access
root2[0][1].append(item)
root2[0][1].append(iTree('Sierra Leone'))
# get the index path information of an item:
print('"Ghana" item index path:',item.idx_path)
# you can also search for items:
result = root2.find(['**', 'Morroco'])
print('"Morroco" item index path:', result.idx_path)
executing the script will deliver:
"Ghana" item index path: [0, 1, 0]
"Morroco" item index path [0, 0, 1]
Beside this you might add additional data to each item and do filtered searches.
精彩评论