adding cgiFiles to repo

[familyTree.git] / familyTree / graphQuestions.py

diff --git a/familyTree/graphQuestions.py b/familyTree/graphQuestions.py
new file mode 100755 (executable)
index 0000000..d7e4465
--- /dev/null
+++ b/familyTree/graphQuestions.py
@@ -0,0 +1,170 @@
+#!/usr/bin/python
+
+import askQuestion as aQ
+from pygraph.classes.graph import graph
+from pygraph.classes.digraph import digraph
+import pygraph.algorithms.minmax as minmax
+import pygraph.algorithms.accessibility as access
+import pickle
+import englishUtils as eU
+
+def follow_path_up(this,target):
+       #this being descended from target
+       path =[target]
+       pathdict = minmax.shortest_path(g,this)[0]
+
+       while target != this and pathdict.has_key(target):
+               target = pathdict[target]
+               path.append(target)
+
+
+       return path
+
+def follow_path_down(this,target):
+       #target being descended from this
+       path = [this]
+       pathdict = minmax.shortest_path(g,target)[0]
+
+       while this != target and pathdict.has_key(this):
+               this = pathdict[this]
+               path.append(this)
+
+       return path
+
+def follow_path(this,target):
+       #this and target of unknown relation
+
+       path = follow_path_up(this,target)
+       if len(path)==1:
+               path = follow_path_down(this,target)
+
+       return path
+
+def is_descendant(this,descendant):
+       #is descendant descended from this, path of descent if so
+       dAnc = accessibility[descendant]
+       if this in dAnc:
+               path = follow_path_down(this,descendant)
+               return path
+
+def ancestors_of(self):
+       #all the ancestors of self
+       return accessibility[self]
+
+def descendants_of(self):
+       #all the descendants of self
+       return a1[self]
+
+def join_up(youngest,oldest):
+       #find all the people linking the list youngest to the list oldest
+
+       d = set([])
+       a =set([])
+        for o in oldest:
+                d = d | set(descendants_of(o))
+       for y in youngest:
+                a= a| set(ancestors_of(y))
+
+
+       nodes =  list(d & a) + youngest + oldest
+       nodes = set(nodes)
+       nodes = list(nodes)
+       return nodes
+
+
+def relationship(a,b):
+       #relationship between a and b
+
+       aAnc = set(accessibility[a])
+        bAnc = set(accessibility[b])
+       
+
+        commonAnc = aAnc.intersection(bAnc)
+       if len(commonAnc)==0:
+               return [],[],0,0
+
+       spA = minmax.shortest_path(g,a)
+       spB = minmax.shortest_path(g,b)
+
+       
+       levelTotal = float('inf')
+       for anc in commonAnc:
+               distA =  spA[1][anc]
+               distB =  spB[1][anc]    
+               if distA+distB<levelTotal:
+                       levelTotal = distA+distB
+                       levelA = distA
+                       levelB = distB
+       
+
+       mrca = []
+       otherRCA = []
+       for anc in commonAnc:
+               distA = spA[1][anc]
+               distB = spB[1][anc]
+               if distA+distB==levelTotal:
+                       mrca.append(anc)
+               elif distA==levelA or distB==levelB:
+                       otherRCA.append(anc)
+
+       return mrca,otherRCA,levelA,levelB
+
+def ancestors(self):
+       #all the ancestors of self, with levels
+       ancs = accessibility[self]
+
+       ancDict={}      
+       sp = minmax.shortest_path(g,self)
+       s = "SELECT parentID FROM parents WHERE id = ?"
+       for a in ancs:
+               dist = sp[1][a]
+               if ancDict.has_key(dist):
+                       ancDict[dist].append(a)
+               else:
+                       ancDict[dist] = [a]
+
+               for r in aQ.run_query(s,(a,)):
+                       if not eU.is_number(r[0]):
+                               if ancDict.has_key(dist+1):
+                                       ancDict[dist+1].append(r[0])
+                               else:
+                                       ancDict[dist+1] = [r[0]]
+
+       return ancs,ancDict
+
+
+def descendants(self):
+       dsc = a1[self]
+       dDict={}
+       sp = minmax.shortest_path(g1,self)
+       for d in dsc:
+               dist = sp[1][d]
+               if dDict.has_key(dist):
+                       dDict[dist].append(d)
+               else:
+                       dDict[dist]=[d]
+
+       return dsc,dDict
+def read_graph():
+       global g
+       global accessibility
+       global g1
+       global a1
+
+       
+       filename = '/u3/naath/familyTreeProject/familyTree/graphedData'
+        file = open(filename)
+        g = pickle.load(file)
+        file.close()
+       accessibility = access.accessibility(g)
+       g1 = digraph.reverse(g)
+       a1 = access.accessibility(g1)
+
+def test():
+       print ancestors_of(5)
+
+       print descendants_of(197)
+read_graph()
+
+#test()
+