Python:从父子关系计算路径

本文介绍了Python:从父子关系计算路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

父)作为 csv(700,000 行)输入

Parent) as csv (700,000 rows) input

Child Parent fA00 f0 fA9 fA0 fA31 fA0 fA30 fA0 fA1 fA00 dccfA1 fA00 fA2 fA00 fA3 fA00 fA01 fA00 fA4 fA00 fA5 fA00 fA6 fA00 fA7 fA00 fA0 fA00 fA142149 fA00 fA02 fA00 fA8 fA00 qA1 fA10 fA22 fA10 fA23 fA10 fA11 fA10 qA2 fA10 fA15 fA11 fA13 fA11 fA12 fA11 fA14 fA13 fA17 fA16 fA18 fA17 fA19 fA17 fA20 fA17 fA21 fA19 etc....

它可以达到 14 级深度.顶级父级是 f0

It goes up to 14 levels deep. The top parent is f0

我想遍历子父关系来确定路径

I want to iterate through the child parent relationships to determine the path

预期结果

f0 --- top f0\fa00 f0\fa00\.Child f0\fa00\.Child2etc f0\fA0 f0\fA0\.Child f0\fA0\.Child2etc

如何在 Python 中执行此操作?

How can I do this in Python?

推荐答案

我开始思考 树结构 但基本上它很简单.创建子级到父级的映射，然后从子级开始，列出其父级，然后是父级的父级，直到顶部.递归程序可以轻松提取孩子的祖先.

I started out thinking complicated recursive construction of tree structures but basically it is very simple. Create a mapping of child to parent then starting at a child list its parent then the parent's parent up to the top. A recursive routine extracts the child's ancestry easily.

''' This is the family tree: ------------------------ f0: a0: b0 b1: b2: a1: b3: b4: a2: b5: c0 c1 ''' ancestry = [ ('b1', 'a0'), ('c1', 'b5'), ('b2', 'a0'), ('b3', 'a1'), ('b4', 'a1'), ('b5', 'a2'), ('a0', 'f0'), ('a1', 'f0'), ('a2', 'f0'), ('b0', 'a0'), ('c0', 'b5'), ]

代码是:

parents = set() children = {} for c,p in ancestry: parents.add(p) children[c] = p # recursively determine parents until child has no parent def ancestors(p): return (ancestors(children[p]) if p in children else []) + [p] # for each child that has no children print the geneology for k in (set(children.keys()) - parents): print '/'.join(ancestors(k))

输出为:

f0/a1/b4 f0/a0/b0 f0/a0/b1 f0/a0/b2 f0/a1/b3 f0/a2/b5/c1 f0/a2/b5/c0

我将把它作为练习阅读 csv 文件，也许可以更好地对输出进行排序.

I'll leave it as an exercise to read the csv file, and maybe sort the outputs better.