API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 25th, 2015
182
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.44 KB | None | 0 0
raw download clone embed print report
  1. class lattice_node:
  2. '''used int fca_lattice'''
  3. def __init__(self,i,u,d,a,o,oi):
  4. self.intent = a
  5. self.object = o
  6. self.object_index = oi
  7. self.up = u
  8. self.down = d
  9. self.index = i
  10. self.weight = 1
  11. def __str__(self):
  12. return str([self.index,self.weight,self.intent,self.up,self.down])
  13. def __repr__(self):
  14. return repr([self.index,self.weight,self.intent,self.up,self.down])
  15. class fca_lattice:
  16. '''lattice is an unsorted list of lattice_node entries
  17.  
  18. >>> fca_lattice([{1,2},{2},{1,3}],lambda x:x)
  19. [[0, 1, {1, 2, 3}, {2, 5}, set()], [1, 4, set(), set(), {3, 4}], [2, 2, {1, 2}, {3, 4}, {0}], [3, 2, {2}, {1}, {2}], [4, 3, {1}, {1}, {2, 5}], [5, 2, {1, 3}, {4}, {0}]]
  20.  
  21. '''
  22. def __init__(self,o,a):
  23. self.attribute_extractor = a
  24. self.objects = o
  25. self.ASets=[set(self.attribute_extractor(oo)) for oo in self.objects]
  26. self.Asequence=[elem for elem in reduce(lambda x,y:x|y,self.ASets)]
  27. #initial nodes are bottom and top
  28. self.nodes = [lattice_node(0,set([1]),set(),set(self.Asequence),None,-1),lattice_node(1,set(),set([0]),set(),None,-1)]
  29. self.itop = 1 #if itop is not added here, there won't be any top
  30. self.ibottom = 0
  31. sai = self._sorted_aset_index(self.Asequence)
  32. for i in sai:
  33. self.AddIntent(self.ASets[i],i,self.ibottom)
  34. self.path = []
  35. #calc weights
  36. def inc_weight(n):
  37. n.weight+=1
  38. self.traverse_up(lambda p:inc_weight(p[-1]))
  39. def __str__(self):
  40. return str(self.nodes)
  41. def __repr__(self):
  42. return repr(self.nodes)
  43. def __getitem__(self,key):
  44. return self.nodes[key]
  45. def sort_by_weight(self,indices):
  46. bw = list(indices)
  47. bw.sort(key=lambda x:self.nodes[x].weight)
  48. bw.reverse()
  49. return bw
  50. def traverse_down(self,visit,node=None):
  51. if node == None:
  52. node = self.nodes[self.itop]
  53. for t in self.sort_by_weight(node.down):
  54. if t==0:
  55. continue
  56. next = self.nodes[t]
  57. self.path.append(next)
  58. visit(self.path)
  59. self.traverse_down(visit,next)
  60. del self.path[-1]
  61. def traverse_up(self,visit,node=None):
  62. if node == None:
  63. node = self.nodes[self.ibottom]
  64. for t in node.up:
  65. if t==0:
  66. continue
  67. next = self.nodes[t]
  68. self.path.append(next)
  69. visit(self.path)
  70. self.traverse_up(visit,next)
  71. del self.path[-1]
  72. def _sorted_aset_index(self,Asequence):
  73. a_i = {}
  74. for a in Asequence:
  75. a_i[a] = [i for i in range(len(self.ASets)) if a in self.ASets[i]]
  76. Asequence.sort(key=lambda x:len(a_i[x]))
  77. Asequence.reverse()
  78. done = set()
  79. index = []
  80. for a in Asequence:
  81. new = set(a_i[a]) - done;
  82. done |= new
  83. index += list(new)
  84. return index
  85. def _get_maximal_concept(self,intent, gen_index):
  86. parentIsMaximal = True
  87. while parentIsMaximal:
  88. parentIsMaximal = False
  89. Parents = self.nodes[gen_index].up
  90. for Parent in Parents:
  91. if intent <= self.nodes[Parent].intent:
  92. gen_index = Parent
  93. parentIsMaximal = True
  94. break
  95. return gen_index
  96. def AddIntent(self,intent,oi,gen_index):
  97. gen_index = self._get_maximal_concept(intent, gen_index)
  98. if self.nodes[gen_index].intent == intent:
  99. if oi > -1:
  100. self.nodes[gen_index].object = self.objects[oi]
  101. return gen_index
  102. GeneratorParents = self.nodes[gen_index].up
  103. NewParents = []
  104. for Parent in GeneratorParents:#Ic&Ii != 0 | Ic&Ii == 0
  105. if not self.nodes[Parent].intent < intent:
  106. nextIntent = self.nodes[Parent].intent & intent
  107. Parent = self.AddIntent(nextIntent, -1, Parent)#if Ic&Ii=0, then top is returned. This could go easier
  108. addParent = True
  109. for i in range(len(NewParents)):
  110. if NewParents[i]==-1:
  111. continue
  112. if self.nodes[Parent].intent <= self.nodes[NewParents[i]].intent:
  113. addParent = False
  114. break;
  115. else:
  116. if self.nodes[NewParents[i]].intent <= self.nodes[Parent].intent:
  117. NewParents[i] = -1
  118. if addParent:
  119. NewParents += [Parent]
  120. #NewConcept = (gen_index.intent, intent ), but here only intent set
  121. NewConcept = len(self.nodes)
  122. oo = None
  123. if oi > -1:
  124. oo = self.objects[oi]
  125. self.nodes += [lattice_node(NewConcept,set(),set(),intent,oo,oi)]
  126. for Parent in NewParents:
  127. if Parent == -1:
  128. continue
  129. #RemoveLink(Parent, gen_index, self.nodes )
  130. self.nodes[Parent].down -= set([gen_index])
  131. self.nodes[gen_index].up -= set([Parent])
  132. #SetLink(Parent, NewConcept, self.nodes )
  133. self.nodes[Parent].down |= set([NewConcept])
  134. self.nodes[NewConcept].up |= set([Parent])
  135. #SetLink(NewConcept, gen_index, self.nodes )
  136. self.nodes[NewConcept].down |= set([gen_index])
  137. self.nodes[gen_index].up |= set([NewConcept])
  138. return NewConcept
  139.  
  140. from svgfig import SVG
  141. from tkinter import *
  142.  
  143. class lattice_diagram:
  144. ''' format and draw a lattice
  145. .. {lattice_diagram,inkscape,tkinter}
  146. >>> src=[ [1,2], [1,3], [1,4] ]
  147. >>> lattice = fca_lattice(src,lambda x:set(x))
  148. >>> ld = lattice_diagram(lattice,400,400)
  149. >>> #display using tkinter
  150. >>> ld.tkinter()
  151. >>> mainloop()
  152. >>> #display using inkscape
  153. >>> ld.svg().inkscape()
  154. '''
  155. def __init__(self,lattice,page_w,page_h):
  156. w = page_w
  157. h = page_h
  158. self.lattice = lattice
  159. self.border = (h+w)//20
  160. self.w = w - 2*self.border
  161. self.h = h - 2*self.border
  162. self.top = self.border
  163. self.dw = w
  164. self.dh = h
  165. self.topnode = self.lattice[self.lattice.itop]
  166. self.nlevels = 0
  167. for n in self.lattice:
  168. n.level = -1
  169. self.topnode.level=0
  170. self.find_levels(self.topnode, self.top, 0)
  171. self.fill_levels()
  172. self.setPos(self.topnode,self.xcenter, self.top,self.dw,self.dh)
  173. self.horizontal_align(self.xcenter)
  174. self.make()
  175. def setPos(self,node,x,y,w,h):
  176. node.x = x
  177. node.y = y
  178. node.w = w
  179. node.h = h
  180. def make(self) :
  181. for n in self.lattice:
  182. n.level = -1
  183. self.topnode.level=0
  184. self.find_levels(self.topnode, self.top, 0)
  185. self.fill_levels()
  186. h = self.top-3*self.dh
  187. for level in self.levels:
  188. h += 3*self.dh
  189. for n in level:
  190. self.setPos(n,0,h,self.dw,self.dh)
  191. self.horizontal_align(self.xcenter)
  192. def find_levels(self,node,ystart,y):
  193. h = 3*self.dh + ystart
  194. y += 1
  195. if(len(node.down) == 0): self.nlevels = y
  196. for i in node.down:
  197. child = self.lattice[i]
  198. if(child.level < y) :
  199. self.setPos(child,0,h,self.dw,self.dh)
  200. child.level=y
  201. self.find_levels(child, h, y)
  202. def fill_levels(self):
  203. self.levels = []
  204. self.dh = self.h / (3*self.nlevels)
  205. self.nmaxlevel = 0
  206. for i in range(self.nlevels):
  207. level = [n for n in self.lattice if n.level==i]
  208. if len(level)>self.nmaxlevel:
  209. self.nmaxlevel = len(level)
  210. self.levels.append(level)
  211. self.dw = self.w / (2*self.nmaxlevel-1)
  212. self.xcenter = self.w+self.border
  213. def find_levels_new(self,min_dist):
  214. '''find levels via multiple sequence alignment
  215. .. {find_levels_new,todo}
  216. Algorithm (started):
  217. - find all paths (which are ordered sets)
  218. - build lattice out of paths (loosing order) (intent = node indices, extent = paths)
  219. - walk lattice from top to bottom breadth-first
  220. - adjust distances between and to already fixed nodes
  221. - stretch everything to meet minimal node distance requirement and convert to integer
  222. '''
  223. pass
  224. def horizontal_align(self,center) :
  225. pX = 0
  226. for level in self.levels:
  227. llen = len(level)
  228. if (llen%2)==0:
  229. pX = center - llen*self.dw + self.dw/2
  230. else:
  231. pX = center - llen*self.dw - self.dw/2
  232. for n in level:
  233. self.setPos(n,pX,n.y,self.dw,self.dh)
  234. pX += 2*self.dw
  235. self.minCrossing(level, False)
  236. for level in self.levels:
  237. self.minCrossing(level, True)
  238. def minCrossing(self,level, forChildren) :
  239. test = False
  240. nbTotal = 0
  241. nbCrossing1 = 0
  242. nbCrossing2 = 0
  243. i = 0
  244. j = 0
  245. while(i<len(level)) :
  246. if(test) :i = 0
  247. test = False
  248. node1 = level[i]
  249. j = i+1
  250. while(j<len(level)):
  251. node2 = level[j]
  252. nbCrossing1 = self.nbCrossing(node1.up, node2.up)
  253. nbCrossing2 = self.nbCrossing(node2.up, node1.up)
  254. if(forChildren) :
  255. nbCrossing1 += self.nbCrossing(node1.down, node2.down)
  256. nbCrossing2 += self.nbCrossing(node2.down, node1.down)
  257. if(nbCrossing1 > nbCrossing2) :
  258. self.swap(level, i, j)
  259. nbTotal += nbCrossing2
  260. test = True
  261. else: nbTotal += nbCrossing1
  262. j += 1
  263. i += 1
  264. return nbTotal
  265. def swap(self,v, i, j) :
  266. node1 = v[i]
  267. node2 = v[j]
  268. v[i]=node2
  269. x = node2.x
  270. node2.x=node1.x
  271. v[j]=node1
  272. node1.x=x
  273. def nbCrossing(self,v1,v2) :
  274. nbCrossing = 0
  275. for in1 in v1:
  276. n1 = self.lattice[in1]
  277. for in2 in v2:
  278. n2 = self.lattice[in2]
  279. if(n1.x>n2.x):
  280. nbCrossing += 1
  281. return nbCrossing
  282. def svg(self):
  283. svg = SVG("g",stroke_width="0.1pt")
  284. for an in self.lattice:
  285. gn=[self.lattice[i] for i in an.down]
  286. for ag in gn:
  287. svg.append(SVG("line",x1=an.x, y1=an.y+an.h/2, x2=ag.x, y2=ag.y+an.h/2))
  288. for an in self.lattice:
  289. txt = ','.join([str(l) for l in an.intent if l])
  290. node = SVG("g",font_size=an.h/2,text_anchor="middle",stroke_width="0.1pt")
  291. node.append(SVG("rect", x=an.x-an.w/2, y=an.y, width=an.w, height=an.h, fill="yellow"))
  292. node.append(SVG("text",txt, x=an.x, y=an.y+3*an.h/4, fill="black"))
  293. svg.append(node)
  294. return svg
  295. def tkinter(self,sx=0.5,sy=0.5):
  296. class ZoomLatCanv(Frame):
  297. def __init__(slf):
  298. Frame.__init__(slf,master=None)
  299. Pack.config(slf,fill=BOTH,expand=YES)
  300. slf.makeCanvas()
  301. slf.drawit()
  302. slf.master.title("Lattice")
  303. slf.master.iconname("Lattice")
  304. slf.scale = 1.0
  305. def Btn1Up(slf,event):
  306. if slf.scale < 1.0:
  307. slf.scale = 1.1 / slf.scale
  308. else:
  309. slf.scale = slf.scale * 1.1
  310. slf.canvas.scale('scale', event.x, event.y, slf.scale, slf.scale)
  311. def Btn3Up(slf,event):
  312. if slf.scale > 1.0:
  313. slf.scale = 1.1 / slf.scale
  314. else:
  315. slf.scale = slf.scale / 1.1
  316. slf.canvas.scale('scale', event.x, event.y, slf.scale, slf.scale)
  317. def makeCanvas(slf):
  318. scrW = slf.winfo_screenwidth()
  319. scrH = slf.winfo_screenheight()
  320. slf.canvas = Canvas(slf,height=scrH,width=scrW,bg='white',cursor="crosshair",
  321. scrollregion=('-50c','-50c',"50c","50c"))
  322. slf.hscroll = Scrollbar(slf,orient=HORIZONTAL, command=slf.canvas.xview)
  323. slf.vscroll = Scrollbar(slf,orient=VERTICAL, command=slf.canvas.yview)
  324. slf.canvas.configure(xscrollcommand=slf.hscroll.set, yscrollcommand=slf.vscroll.set)
  325. slf.hscroll.pack(side=BOTTOM,anchor=S,fill=X,expand=YES)
  326. slf.vscroll.pack(side=RIGHT,anchor=E,fill=Y,expand=YES)
  327. slf.canvas.pack(anchor=NW,fill=BOTH,expand=YES)
  328. Widget.bind(slf.canvas,"<Button1-ButtonRelease>",slf.Btn1Up)
  329. Widget.bind(slf.canvas,"<Button3-ButtonRelease>",slf.Btn3Up)
  330. def drawit(slf):
  331. for an in self.lattice:
  332. gn=[self.lattice[i] for i in an.down]
  333. for ag in gn:
  334. slf.canvas.create_line(an.x, an.y+an.h/2, ag.x, ag.y+an.h/2,tags='scale')
  335. for an in self.lattice:
  336. slf.canvas.create_rectangle(an.x-an.w/2, an.y, an.x+an.w/2, an.y+an.h, fill="yellow",tags='scale')
  337. slf.canvas.create_text(an.x,an.y+3*an.h/4,fill="black",text=','.join([str(l) for l in an.intent if l]),tags='scale')
  338. return ZoomLatCanv()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!