Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
135 lines (108 sloc) 5.23 KB
def tokens(s):
cursor=0
n=''
while cursor<len(s):
if s[cursor]=='(':
cursor+=1
yield 'OPEN_PAREN','('
continue
if s[cursor]==')':
cursor+=1
yield 'CLOSE_PAREN',')'
continue
if s[cursor]==':':
cursor+=1
yield 'COLON',':'
if s[cursor]==';':
cursor=len(s)
break
if s[cursor]==',':
cursor+=1
yield 'COMMA',','
continue
n=''
while cursor<len(s) and s[cursor] not in [',',';',')','(',':']:
n+=s[cursor]
cursor+=1
if len(n.strip())>0:
yield 'LABEL',n.strip()
def build_tree2(s):
tree,labels,weights={},{},{}
taxa=[]
parent,curnode=-1,0
new_node=1
tree[0]=-1 #introduce an artificial root note
prior_kind=None
for (kind,value) in tokens(s):
if kind=='OPEN_PAREN':
parent=curnode
curnode=new_node
tree[curnode]=parent
new_node=new_node+1
prior_kind=kind
continue
if kind=='LABEL':
if prior_kind=='CLOSE_PAREN':
labels[value]=savenode
elif prior_kind=='COLON':
weights[savenode]=int(value)
else:
labels[value]=new_node
tree[new_node]=curnode
savenode=new_node # needed if this label is followed by colon
taxa.append(value)
new_node+=1
prior_kind=kind
continue
if kind=='COLON':
if prior_kind=='COMMA' or prior_kind=='OPEN_PAREN':
tree[new_node]=curnode
# savenode=new_node
new_node+=1
prior_kind=kind
continue
if kind=='CLOSE_PAREN':
if prior_kind=='COMMA':
tree[new_node]=curnode
new_node+=1
savenode=curnode
curnode=parent
parent=tree[curnode]
prior_kind=kind
continue
if kind=='COMMA':
if prior_kind=='COMMA':
tree[new_node]=curnode
new_node+=1
prior_kind=kind
continue
if parent!=-1:
raise Exception('ParseError')
else:
return tree,labels,weights,taxa
s="((((((Agama_ammon,Latastia_lineatus),(Boiga_atthis,Bos_leporosum)),Turdus_laticauda),(Circus_acutus,Dipus_franckii)),(((((Asthenodipsas_caudatus,Passer_novaeguineae),Testudo_quadriocellata),Oedura_kopsteini),(((Basiliscus_rosmarus,(Lepidobatrachus_viridescens,Streptopelia_breitensteini)),((Butastur_hispida,Ciconia_fiber),Lepus_multifasciata)),sibiricus_aegyptia)),Hirundo_fissipes)),((Aix_erythronotus,Uroplatus_garulla),Almo_guttifer),(((((((((((((((((((((((((Alaus_fasciata,Oceanodroma_kingii),(Marmota_vegans,Phrynosoma_amethistina)),Tupinambus_vitticeps),Corallus_baeri),Ciconia_wogura),Budytes_marcianus),Ortigometra_brachydactyla),Phrynosoma_oenanthe),((((Ambystoma_taezanowskyi,Anolis_adspersus),((Monodon_stejnegeri,(Parus_walti,Phrynops_fulva)),Pogona_alterna)),((Chrysopelea_torquatus,Ninox_monachus),Riparia_cambridgei)),Phoca_carbo)),Aythya_stagnalis),Tropidurus_not),Paramesotriton_docilis),Lycaenopsis_hypomelus),Phormictopus_leucophyllata),Petrocincla_oxycephalum),Vipera_arizonensis),((Almo_carnivorus,Nyctaalus_dulkeitiana),Chelodina_dentata)),(((((((((((((Ambystoma_czerskii,(Fulica_stagnalis,(Haplopelma_multituberculatus,Phrynohyas_himalayanus))),Xenochrophis_caninus),Ptychozoon_semipalmatus),Querquedula_graeca),Haliaetus_caniceps),Machetes_laevis),(Litoria_thibetanus,Otis_grandis)),Uroplatus_platyrhinos),Parus_pardalis),(Camptoloma_constrictor,Leuciscus_iguana)),(Lamprophis_fernandi,Sorex_onocrotalus)),((((((((Boiga_gecko,Tropidurus_guentheri),Euspiza_veredus),Net_turtor),Polypedates_krueperi),Notophthalmus_hispida),Ceratophrys_kingii),(Capella_bairdi,(Paraphysa_marmorata,Sus_taxus))),Tropidurus_geyri)),Scincus_semipalmatus)),Thymallus_tristis),(Phyllopneuste_oenanthe,Psammophis_pardus)),Desnana_parahybana),Haplopelma_quadrivirgata),Egretta_insularis),((((Bronchocela_leptochelis,((Circus_mycterizans,(Dasypeltis_orientalis,(Meles_rufina,Pandinus_troglodytes))),Thymallus_alpestris)),Prunella_celer),Ziphius_bifasciatus),(Motacilla_sujfunensis,Neolycaena_yeltoniensis))),Chrttusia_davidiana));"
x,y='Psammophis_pardus', 'Phrynohyas_himalayanus'
def path_to_root(x,tree,labels):
start_node=labels[x]
path=[start_node]
parent=tree[start_node]
while parent!=-1:
path.append(parent)
parent=tree[parent]
return path
def tree_distance(x,y,tree,labels,weights):
xnode=labels[x]
ynode=labels[y]
d=0
while True:
if xnode<ynode:
d+=weights.get(ynode,1)
ynode=tree[ynode]
elif ynode<xnode:
d+=weights.get(xnode,1)
xnode=tree[xnode]
elif ynode==xnode:
return d
#tree,labels=build_tree2(s)
#print path_to_root(x,tree,labels)
#print path_to_root(y,tree,labels)
You can’t perform that action at this time.