2

I have a large RDF file containing about 600,000 records of Wikidata taxonomy. From this file, I am only interested in subclassOf relations (predicate), thus, I ignore all the other statements keeping only "subclassOf" statements. The statement is like: a is a subclassOf b, b is a subclassOf c Like that c is a parent of b and b is a parent of a. And any parent can have many children. I want to build hierarchical tree using this taxonomy. I have checked this thread and it almost solved my problem. Recursively creating a tree hierarchy without using class/object However, with this, I am getting tree in dictionary which I want to convert into tree data-structure. Following is what I have tried: 

data = [['a','x'], ['b','x'], ['c','x'], ['x','y'], ['t','y'], ['y','p'], ['p','q']]

roots = set()
mapping = {}
for child,parent in data:        
    childitem = mapping.get(child,None)
    if childitem is None:
        childitem =  {}
        mapping[child] = childitem
    else:
        roots.discard(child)
    parentitem = mapping.get(parent,None)
    if parentitem is None:
        mapping[parent] = {child:childitem}
        roots.add(parent)
    else:
        parentitem[child] = childitem

for root in roots:
    print(mapping[root])

tree = { id : mapping[id] for id in roots }
print(tree)

Output of tree looks as below:

{'q': {'p': {'y': {'t': {}, 'x': {'c': {}, 'b': {}, 'a': {}}}}}}

I want to convert this dictionary to tree. So e.g. when I say print(mapping['y']), it should give me Node y i.e. 

q
├── p
    └── y

currently, if I say mapping['y'], it gives me subtree rooted at y. I think there is some easy solution for this, but I am not able to understand it. I have found this link as well https://gist.github.com/hrldcpr/2012250 to convert dictionary into tree, but not sure how to use it in my case. Alernatively, if anyone knows to directly built a tree from the RDF data that I had given above, then it will be most welcome. Probably python's anytree API will solve my issue.

Nilakshi Naphade
  • 1,055
  • 4
  • 14
  • 30
  • Do you need a "Tree" class? a way to pretty-print the ancestors of a node for the dictionary-tree you have now? or both? – Shihab Shahriar Khan Nov 26 '17 at 15:28
  • Ultimately I need only ancestors (or path till that node). Whether I am getting it using Tree or dictionary is immaterial. Thus, if I can somehow access path for the keys in nested dictionary, my issue will be resolved. – Nilakshi Naphade Nov 26 '17 at 15:33

1 Answers1

1

If you don't mind extra O(N) space, you can keep a parents dictionary, storing the value parent for every key child. And populate it in main for loop.

Finding all ancestors is now pretty easy. Recursively find all ancestors of your parent and append current node to that result.

data = [['a','x'], ['b','x'], ['c','x'], ['x','y'], ['t','y'], ['y','p'], ['p','q']]
parents = {} #to store parents
roots = set()
mapping = {}
for child,parent in data:
    parents[child] = parent #populate parents
    childitem = mapping.get(child,None)
    ................................

def ancestors(node): #the ancestor-finding function
    if not node: return []
    return ancestors(parents.get(node))+[node]

def first_k_ancestor(node,k=5):
    ances = ancestors(node)
    ances.reverse()
    return ances[:k]


print(ancestors('a'))

which prints:

['q', 'p', 'y']
Shihab Shahriar Khan
  • 4,930
  • 1
  • 18
  • 26
  • Seems to work fine for me. And what if I want this hierarchy in reverse order and only till level 3. E.g. For node 'a' I want only [a, x, y] and Not [a,x,y,p,q] – Nilakshi Naphade Nov 26 '17 at 16:21
  • Is performance an issue? and can that 3 might change i.e top 5 ancestors maybe? – Shihab Shahriar Khan Nov 26 '17 at 16:27
  • Performance is not really an issue, because creating this hierarchy is a one time process and later I am going to store required keys and their respective path (as value) in dictionary which I will access often. And I actually want 5 ancestors only, I said 3 to make this example work. In real data I can have like 50 ancestors among which I will need only last 5. – Nilakshi Naphade Nov 26 '17 at 16:30
  • see if `first_k_ancestors` do the job. which automatically selects top 5, but u can change that by passing a 2nd parameter – Shihab Shahriar Khan Nov 26 '17 at 17:06
  • Okay. I will try this. Thanks :) – Nilakshi Naphade Nov 26 '17 at 17:56