Show More
@@ -9,9 +9,10 b' import heapq' | |||
|
9 | 9 | |
|
10 | 10 | def ancestor(a, b, pfunc): |
|
11 | 11 | """ |
|
12 | return a minimal-distance ancestor of nodes a and b, or None if there is no | |
|
13 | such ancestor. Note that there can be several ancestors with the same | |
|
14 | (minimal) distance, and the one returned is arbitrary. | |
|
12 | Returns the common ancestor of a and b that is furthest from a | |
|
13 | root (as measured by longest path) or None if no ancestor is | |
|
14 | found. If there are multiple common ancestors at the same | |
|
15 | distance, the first one found is returned. | |
|
15 | 16 | |
|
16 | 17 | pfunc must return a list of parent vertices for a given vertex |
|
17 | 18 | """ |
@@ -22,6 +23,7 b' def ancestor(a, b, pfunc):' | |||
|
22 | 23 | a, b = sorted([a, b]) |
|
23 | 24 | |
|
24 | 25 | # find depth from root of all ancestors |
|
26 | # depth is stored as a negative for heapq | |
|
25 | 27 | parentcache = {} |
|
26 | 28 | visit = [a, b] |
|
27 | 29 | depth = {} |
@@ -39,6 +41,7 b' def ancestor(a, b, pfunc):' | |||
|
39 | 41 | if p not in depth: |
|
40 | 42 | visit.append(p) |
|
41 | 43 | if visit[-1] == vertex: |
|
44 | # -(maximum distance of parents + 1) | |
|
42 | 45 | depth[vertex] = min([depth[p] for p in pl]) - 1 |
|
43 | 46 | visit.pop() |
|
44 | 47 |
General Comments 0
You need to be logged in to leave comments.
Login now