API tools faq
paste
Guest User

Untitled

a guest
Mar 20th, 2018
119
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.54 KB | None | 0 0
raw download clone embed print report
  1. '''
  2. En esta version modifique:
  3. 1ero. ClanWithNonVisible
  4. 2do. ClanWith
  5.  
  6. Como FindUnionDecomposition pero que la clase Edge devuelva from y to, esto para corregir la funcion pack.
  7. OjO ver quiza habra que modificar el howClansAreSeen*
  8. '''
  9. def EdgeOf(FromTo):
  10. here = False
  11. j=0
  12. while not here and j< len(EdgesNodes):
  13. if FromTo == str(EdgesNodes[j]):
  14. here = True
  15. else:
  16. j+=1
  17. if here:
  18. return EdgesNodes[j]
  19. else:
  20. print 'Edge not found'
  21.  
  22. '''
  23. Para trabajar con un grafo dirigido la funcion tendria que cosiderar las aristas del nodo a los elementos del clan
  24. Copia los nodos del clan a una nueva lista y elimina el clan no visible, OurClanList.
  25. Obtienen los elementos de tipo Edge que van de node a OurClanList
  26. y ve nodo a nodo, si las aristas del nodo no visible y de node hacia un mismo nodo, estan en la misma clase de equivalencia.
  27. '''
  28. def ClanWithNonVisible(NonVisible,ClanList,node):
  29. NodeToOurClan = []
  30. NewEdges =[]
  31.  
  32. OurClanList = ClanList[:]
  33. OurClanList.remove(NonVisible)
  34.  
  35. for i in OurClanList:
  36. NodeToOurClan.append(EdgeOf(str(i)+','+node))
  37.  
  38. #print 'Del nodo a los restantes del clan:'
  39. #for i in NodeToOurClan:
  40. # print str(i)
  41.  
  42. #Ver si estos colores son los mismos desde el nodo no visible
  43. TheyAreClans = True
  44. j=0
  45. while TheyAreClans and j <len(OurClanList):
  46. n = EdgeOf(str(OurClanList[j])+','+str(NonVisible))
  47. if Find(n)== Find(NodeToOurClan[j]):
  48. j+=1
  49. else:
  50. TheyAreClans = False
  51.  
  52. return TheyAreClans
  53. '''
  54. Input: clan.nodes lista de strings y node un str.
  55. Output: True/False, str: el nodo con el que node hace clan
  56. Busca si alguno de los vertices existentes tiene Edges hacia el resto de los nodos que esten en la misma clase de equivalencia que las edges que conectan con node (desde cada vertice del clan)
  57.  
  58. '''
  59. def ClanWith(ClanList,node):
  60. print 'ClanWith'
  61. NewEdges = []
  62. ClanToNode =[]
  63. for i in ClanList:
  64. #%print 'in ClanList:', i
  65. ClanToNode.append(EdgeOf(str(i)+','+node))#esto en lugar de #% los ve a todos y no tendria porque tronar
  66. #%NewEdges.append(str(i)+','+node)
  67. #NewEdges son los strings de las aristas que van de los elementos del clan al nodo
  68.  
  69. #%for i in NewEdges:
  70. #% print i
  71. #% here = False
  72. #% j=0
  73. #% while not here and j< len(EdgesNodes):
  74. #% if i == str(EdgesNodes[j]):
  75. #% here = True
  76. #% else:
  77. #% j+=1
  78. #% if here:
  79. #% ClanToNode.append(EdgesNodes[j])
  80.  
  81. #NodeToClan son los Edge de los elementos del clan al nodo
  82. print 'Aristas encontradas:'
  83. for i in ClanToNode:
  84. print str(i)
  85. i=0
  86. ClanFound= False
  87. while not ClanFound and i<len(ClanList):
  88. ActNode = ClanList[i]
  89. same=True
  90. j=0
  91. while same and j <len(ClanList):
  92. if i!=j:
  93. n = EdgeOf(str(ClanList[j])+','+str(ClanList[i]))
  94. if Find(n)== Find(ClanToNode[j]): #ClanToNode[j] =str(ClanList[j])+','+node)
  95. j+=1
  96. else:
  97. same = False
  98. else:
  99. j+=1
  100. if same==False:
  101. i+=1
  102. else:#elif j == len(ClanList):Solo puede hacer clan con un elemento y por lo tanto sale al encontrarlo
  103. ClanFound=True
  104. if ClanFound:
  105. return ClanFound, ClanList[i] #True/False,SomeNode
  106. else:
  107. return False,''
  108.  
  109.  
  110. '''
  111. Input: Lista de Edges NonVisibleClans
  112. Output: Devuelve los nodos ya visibles, separados segun el color por el que son vistos (*comprobar si es asi)
  113. y de vuelve los nodo como nodos individuales, str...
  114. '''
  115. def Split(NonVisibleClans,node):
  116. print 'Split: ', NonVisibleClans
  117. SplitEdges=[]
  118. SplitR=[]
  119. SplitNodes =[]
  120. SplitNonVisible=[]
  121. SplitD={}
  122.  
  123. NewNodes = []
  124. NewClans = []
  125. for i in CCT[0]:
  126. SplitD.setdefault(i, [])
  127.  
  128. for Clan in NonVisibleClans:
  129. print Clan
  130. #for clan in Clan:
  131. # print clan
  132. # SplitEdges.append(str(clan)+','+node)
  133. SplitEdges.append(str(Clan)+','+node)
  134. print SplitEdges
  135.  
  136. for i in range(len(SplitEdges)):
  137. print 'Arista a buscar', SplitEdges[i]
  138. here = False
  139. j = 0
  140. while not here and j< len(EdgesNodes):
  141. if SplitEdges[i] == str(EdgesNodes[j]):
  142. here = True
  143. else:
  144. j+=1
  145. if here:
  146. print 'Arista encontrada:'
  147. SplitD[Find(EdgesNodes[j])].append(str(EdgesNodes[j].EdgeFrom()))
  148. #SplitR.append(str(EdgesNodes[j].EdgeFrom()))
  149. for i in SplitD.values():
  150. if i!=[] and i not in SplitR:
  151. SplitR.append(i)
  152.  
  153. else:
  154. print 'Arista no encontrada, split sobre el nodo', NonVisibleClans[i]
  155. SplitR.extend(Split(NonVisibleClans[i],node)[0])
  156.  
  157. for i in SplitR:#lista de listas
  158. print 'el nodo/clan es: ', i,'con tamanio: ', len(i)
  159. if len(i)==1:
  160. SplitR.insert(SplitR.index(i),i[0])
  161. SplitR.remove(i)
  162. if i[0] not in NewNodes:
  163. NewNodes.append(i[0])
  164. print 'por lo tanto es un nodo'
  165. else:
  166. print 'por lo tanto es un clan'
  167. if i not in NewClans:
  168. NewClans.append(i)
  169. #print 'Nuevos nodos', NewNodes
  170. #print 'Nuevos clanes', NewClans
  171. return SplitR,NewNodes,NewClans
  172. #return SplitR
  173.  
  174.  
  175. def ClanGenerator(NodeList):
  176. if len(NodeList)== 2:
  177. NewClan = MyClan('complete')
  178. NewClan.add_nodes_from(NodeList)
  179. else:#if len(i)>2 :
  180. print NodeList
  181. print 'tamanio de i',len(NodeList),'i[0]',NodeList[0],',',NodeList[1],'i[1]'
  182. same = True
  183. InitialColor = Find(EdgeOf(str(NodeList[0])+','+str(NodeList[1])))
  184. n = 0
  185. while same and n <len(NodeList)-1:
  186. j = n+1
  187. while same and j < len(NodeList):
  188. if Find(EdgeOf(str(NodeList[n])+','+str(NodeList[j])))== InitialColor :
  189. j+=1
  190. else:
  191. same = False
  192. if j==len(i):
  193. n+=1
  194. if same:
  195. NewClan = MyClan('complete')
  196. else:
  197. NewClan = MyClan('primitive')
  198. NewClan.add_nodes_from(i)
  199. return NewClan
  200.  
  201.  
  202. '''
  203. Input: NodeList Lista de str, nodos a compactar
  204. Output: Actualiza EdgesNodes, agregando las aristas que se generan al compactar los nodos de entrada
  205. como decidir si se compacta o no: se compactara cuando en ese momento se tenga almenos un nodo que los haga clan, i.e. que ya los este compactando.
  206. '''
  207. def Pack(NodeList):
  208. print 'Make a clan to:'
  209. for k in NodeList:
  210. print k
  211.  
  212. Edges = []
  213. for i in EdgesNodes:
  214. frm = i.EdgeFrom()
  215. to = i.EdgeTo()
  216. for j in NodeList:
  217. #if str(j) == frm and '[' not in to and to not in NodeList and i not in Edges:
  218. if str(j) == frm and '[' not in to and i not in Edges:
  219. notinNodeList = True
  220. c=0
  221. while notinNodeList and c<len(NodeList):
  222. if to in NodeList[c]:
  223. notinNodeList = False
  224. else:
  225. c+=1
  226. if notinNodeList:
  227. Edges.append(i)
  228.  
  229. print '_______elementos de NodeList en:____________'
  230. for i in Edges:
  231. print str(i), Find(i)
  232.  
  233. i = 0
  234.  
  235. while i < len(Edges):
  236. edge = str(Edges[i])
  237. to = Edges[i].EdgeTo()
  238. j = i+1
  239. pack = True
  240. ine = False
  241. InitialColor = Find(Edges[i])
  242. while pack and j<len(Edges):
  243. thisto = Edges[j].EdgeTo()
  244. if to == thisto:
  245. if InitialColor == Find(Edges[j]):
  246. ine = True
  247. j+=1
  248. else:
  249. pack = False
  250. else:
  251. j+=1
  252. if pack and ine:
  253. k = Edge(str(NodeList),',',to)
  254. l = Edge( to,',',str(NodeList))
  255. EdgesNodes.append(k)
  256. EdgesNodes.append(l)
  257. MakeSet(k)
  258. MakeSet(l)
  259. Union(Edges[i],k)
  260. Union(Edges[i],l)
  261. elif pack == False:
  262. #Eliminar todas las Edges con ese to
  263. #Edges.remove(Edges[j])
  264. l=j
  265. while l< len(Edges):
  266. thisto = Edges[l].EdgeTo()
  267. if to == thisto:
  268. Edges.remove(Edges[l])
  269. l+=1
  270. i+=1
  271.  
  272. #print '--------Aristas finales----------'
  273. #for i in EdgesNodes:
  274. # print str(i), Find(i)
  275.  
  276.  
  277.  
  278.  
  279. '''
  280. Input: Lista de objetos Edge
  281. Output: Devuelve true si todas las aristas en EdgeList tienen el mismo color
  282. '''
  283. def EdgesHaveSameColor(EdgeList):
  284. Same = True
  285. InitialColor= Find(EdgeList[0])
  286. i = 1
  287. while Same and i < len(EdgeList):
  288. if InitialColor != Find(EdgeList[i]):
  289. Same = False
  290. else:
  291. i+=1
  292. return Same
  293.  
  294.  
  295.  
  296. '''
  297. Input: MyClan Clan,str node
  298. Output: 2 Lists of Edge type y dos listas de string q representa los nodos no visibles y los visibles.
  299. SameColorAsClan, VisibleClans, NonVisibleClans
  300. '''
  301. def HowClansAreSeen(Clan,node):#MyClan Clan, str node
  302. NewEdges=[]
  303. EdgesNodesList =[]
  304.  
  305. SameColorAsClan=[]
  306. VisibleClans=[]
  307. NonVisibleClans=[]
  308. SameColorTo = []
  309. for i in Clan.nodes:
  310. NewEdges.append(str(i)+','+node)
  311.  
  312.  
  313. for i in range(len(NewEdges)):
  314. print NewEdges[i]
  315. here = False
  316. j=0
  317. while not here and j< len(EdgesNodes):
  318. if NewEdges[i] == str(EdgesNodes[j]):
  319. here = True
  320. else:
  321. j+=1
  322. if here:
  323. EdgesNodesList.append(EdgesNodes[j])
  324. #print str(EdgesNodes[j]),Find(EdgesNodes[j])
  325. else:
  326. to = Clan.nodes[i]
  327. NonVisibleClans.append(to)
  328. #print to
  329. #for i in NewEdges:
  330. # for edge in EdgesNodes:
  331. # if i==str(edge):
  332. # print i
  333. # EdgesNodesList.append(edge)
  334.  
  335. if Clan.clantype == 'complete':
  336. #encuentra el color del clan
  337. e = str(Clan.nodes[0])+','+str(Clan.nodes[1])
  338. j = 0
  339. i = EdgesNodes[j]
  340. while e != str(i) and j<len(EdgesNodes):
  341. i = EdgesNodes[j]
  342. j+=1
  343. colorclan =Find(i)
  344.  
  345. for c in range(len(EdgesNodesList)):
  346. #try:
  347. if colorclan != Find(EdgesNodesList[c]):
  348. VisibleClans.append(EdgesNodesList[c])
  349. #p =str(EdgesNodesList[c])
  350. #VisiblePoints.append(p[:p.index(',')])
  351. else:
  352. SameColorAsClan.append(EdgesNodesList[c])
  353. #except:
  354. # NonVisibleClans.append(EdgesNodesList[c])
  355. else:
  356. for c in range(len(EdgesNodesList)):
  357. #try:
  358. #Find(EdgesNodesList[c])
  359. VisibleClans.append(EdgesNodesList[c])
  360. #p =str(EdgesNodesList[c])
  361. #VisiblePoints.append(p[:p.index(',')])
  362. #except:
  363. # NonVisibleClans.append(EdgesNodesList[c])
  364.  
  365. #print 'color clan: ', colorclan
  366. #print 'visible clans:'
  367. #for i in VisibleClans:
  368. # print str(i)
  369. #print 'non visible clans:'
  370. #for i in NonVisibleClans:
  371. # print str(i)
  372. #print 'same color as clans:'
  373. #for i in SameColorAsClan:
  374. # print str(i)
  375. return SameColorAsClan,VisibleClans, NonVisibleClans #,VisiblePoints
  376.  
  377. #Hacer Pack al final y cuando se crean nuevos clanes
  378. def AddNode(Clan,node): #MyClan Clan, str node
  379. print 'Clan nodes: ',Clan.nodes
  380. print 'Clan type: ',Clan.clantype
  381. if len(Clan.nodes)==1:
  382. #print Clan.nodes[0]
  383. if '[' not in str(Clan.nodes[0]):
  384. Clan.add_node(node)
  385. #print 'un nodo habia'
  386. else:
  387. #print 'un clan habia'
  388. ActualNode = Clan.nodes[0]
  389. for i in ActualNode:
  390. Clan.add_node(i)
  391. Clan.remove_node(ActualNode)
  392. AddNode(Clan,node)
  393. #Pack(Clan.nodes)#la regla del compactar no se cumple aqui, pero lo voy a dejar
  394. else:
  395. HCAS = HowClansAreSeen(Clan,node)
  396. SameColorAsClan = HCAS[0]
  397. VisibleClans = HCAS[1]
  398. NonVisibleClans = HCAS[2]
  399.  
  400. if Clan.clantype=='complete':
  401. if len(SameColorAsClan)==len(Clan.nodes):
  402. print 'El nodo ve a todos los elementos del mismo color que el color del clan'
  403. Clan.add_node(node)
  404. #Pack(Clan.nodes)#la regla del compactar no se cumple aqui, pero lo voy a dejar
  405.  
  406. elif len(SameColorAsClan)!= 0:
  407. ListNodesSameColor = []
  408. ListNodesDiferentColor = []
  409.  
  410. for i in SameColorAsClan:
  411. ListNodesSameColor.append(i.EdgeFrom())
  412. print 'El nodo ve a algunos elementos del clan del mismo color que el color del clan'
  413. print 'los elementos son:'
  414. print ListNodesSameColor
  415.  
  416. NodesInClan = Clan.nodes[:]
  417. for i in NodesInClan:
  418. if str(i) not in ListNodesSameColor:
  419. ListNodesDiferentColor.append(i)
  420. print 'Elementos del clan que no son vistos del mismo color:', ListNodesDiferentColor
  421.  
  422. ClanNotSameColor = MyClan('complete')
  423. for i in ListNodesDiferentColor:
  424. Clan.remove_node(i)
  425. if '[' in i: #Se trata de un clan
  426. ci = i.replace('[','')
  427. ci = ci.replace(']','')
  428. ci = ci.split(', ')
  429. print ci
  430. clan_i = Clan.getclanwithnodes(ci)
  431. ClanNotSameColor.add_clan(ci)
  432. else:
  433. ClanNotSameColor.add_node(i)
  434.  
  435. #for i in Clan.nodes:
  436. # if type(i) == list:
  437. # l = str(i)
  438. # else:
  439. # l = i
  440. # if l in ListNodesDiferentColor:
  441. # Clan.remove_node(i)
  442.  
  443. #print '\\\\\\\\\\'
  444. #print Clan.nodes
  445. print '*********************'
  446. AddNode(ClanNotSameColor,node)
  447.  
  448. print ClanNotSameColor.nodes
  449. print '++++++'
  450. print Clan.nodes
  451. Clan.add_clan(ClanNotSameColor)
  452. print 'clan final', Clan.nodes
  453. Pack(ClanNotSameColor.nodes)
  454. #Pack(Clan.nodes)#la regla del compactar no se cumple aqui, pero lo voy a dejar
  455. print '************************************* compacta a: ', ClanNotSameColor.nodes
  456.  
  457. elif len(NonVisibleClans)!=0:
  458. print 'El nodo no puede ver a ',len(NonVisibleClans) ,' elementos del clan y estos son:', NonVisibleClans
  459. Clan.add_node(node)
  460. Clan.remove_nodes_from(NonVisibleClans)
  461. Clan.clantype = 'primitive'
  462. print 'Nodos del Clan antes del Split: ', Clan.nodes
  463. #for i in NonVisibleClans:
  464. # print 'nodo en NonVisibleClans: ', i
  465. # Clan.add_nodes_from(Split(i,node))
  466. S=Split(NonVisibleClans,node)
  467. #Clan.add_nodes_from(S)
  468. print 'Nuevos nodos', S[1]
  469. Clan.add_nodes_from(S[1])
  470. print 'Nuevos clanes', S[2]
  471. #Clan.add_nodes_from(S[2])
  472. for i in S[2]:
  473. CG = ClanGenerator(i)
  474. Clan.add_clan(CG)
  475.  
  476. #print 'Elementos de Split:', S
  477. #AddSplitedNodes(S[0],Clan)
  478. #Clan.add_nodes_from(S[1])
  479. print 'Nodos del Clan despues del Split: ', Clan.nodes,'***'
  480. else:
  481. if EdgesHaveSameColor(VisibleClans):
  482. print 'El nodo ve con el mismo color a todos los elementos del clan, y este color es distintos al color del clan.'
  483. NodesInVisibleClans =Clan.nodes[:]
  484. Clan.add_node(node)
  485. Clan.remove_nodes_from(NodesInVisibleClans)
  486. NewClan = MyClan('complete')
  487. NewClan.add_nodes_from(NodesInVisibleClans)
  488. Clan.add_clan(NewClan)
  489. Pack(NodesInVisibleClans)
  490. #Pack(Clan.nodes)#la regla del compactar no se cumple aqui, pero lo voy a dejar
  491. print 'Los nodos del clan resultante son: ', Clan.nodes, '\n **********************************mismos que se compactaron'
  492. else:#Si ve a k nodos del mismo color estos se deben agrupar y no se estan agrupando... revisar esto con un ejemplo
  493. print 'los ve de distinto color'
  494. #l = Split(Clan.nodes(),node)
  495. Nodes = Clan.nodes[:]
  496. Clan.remove_nodes_from(Nodes)
  497. Clan.add_node(node)
  498. Clan.clantype = 'primitive'
  499. #NewClansList =[]
  500. #for i in l:
  501. # if len(i)>1:#if '[' in i:
  502. # print 'formar un nuevo clan con i ',i,' y pack them'
  503. # NewClan = MyClan()
  504. # NewCla.add_nodes_from(i)
  505. # else:
  506. # Clan.add_node(i)
  507. S=Split(Nodes,node)
  508. #Clan.add_nodes_from(S)
  509. print 'Nuevos nodos', S[1]
  510. Clan.add_nodes_from(S[1])
  511. print 'Nuevos clanes', S[2]
  512. #Clan.add_nodes_from(S[2])
  513. for i in S[2]:
  514. CG = ClanGenerator(i)
  515. Clan.add_clan(CG)
  516.  
  517. #print 'Elementos de Split: ',S
  518. #AddSplitedNodes(S[0],Clan)
  519. #Clan.add_nodes_from(S[1])
  520. print 'Nodos en el Clan despues de Split', Clan.nodes
  521. #No se hace pack ya que se compactara hasta que llegue un fondo que los vea a todos igual
  522.  
  523. else:#primitive
  524. if len(NonVisibleClans) != 0:
  525. print 'Hay elementos no visibles y son:'
  526. for n in NonVisibleClans:
  527. print n
  528. print 'si el tamani del non visible es uno, ver si hace clan con este, sino colocarlo como uno mas y hacer split'
  529. if len(NonVisibleClans) == 1 and ClanWithNonVisible(NonVisibleClans[0],Clan.nodes,node):
  530. print 'hay un nodo/clan no visible y hace clan con el, es:', NonVisibleClans[0]
  531. print 'buscarlo en: ', Clan.nodes
  532. ClanAux = Clan.getclanwithnodes(NonVisibleClans[0])
  533. AddNode(ClanAux,node)#Aqui se hace pack segun donde deba compactarse
  534. Clan.remove_node(NonVisibleClans[0])
  535. Clan.add_clan(ClanAux)
  536. else:
  537. print 'Hay un nodo/clan (pero no forma clan con el) o mas nodos/clanes no visibles desde node'
  538. Clan.add_node(node)
  539. Clan.remove_nodes_from(NonVisibleClans)
  540. S = Split(NonVisibleClans,node)
  541. #Clan.add_nodes_from(S)
  542. print 'Nuevos nodos', S[1]
  543. Clan.add_nodes_from(S[1])
  544. print 'Nuevos clanes', S[2]
  545. #Clan.add_nodes_from(S[2])
  546. for i in S[2]:
  547. CG = ClanGenerator(i)
  548. Clan.add_clan(CG)
  549. #print 'Elementos de Split: ',S
  550. #AddSplitedNodes(S[0],Clan)
  551. #Clan.add_nodes_from(S[1])
  552. print 'Nodos en el Clan despues de Split', Clan.nodes
  553.  
  554.  
  555.  
  556. elif EdgesHaveSameColor(VisibleClans):
  557. print 'El nodo ve a todos los elementos del clan primitive del mismo color.'
  558. NodesInVisibleClans =Clan.nodes[:]
  559.  
  560. Clan.remove_nodes_from(NodesInVisibleClans)
  561. Clan.add_node(node)
  562. Clan.clantype = 'complete'
  563.  
  564. NewClan= MyClan('primitive')
  565. NewClan.add_nodes_from(NodesInVisibleClans)
  566. Clan.add_clan(NewClan)
  567. Pack(NodesInVisibleClans)#Se compactan porque ya el node los esta compactando.
  568. else:
  569. print 'Buscar si hace clan con alguno y sino colocarlo como un nodo mas'
  570. #ClanWith(VisibleClans,node)
  571. CW =ClanWith(Clan.nodes,node)
  572. if CW[0]:
  573. print 'hizo clan con un node/clan'
  574. if '[' in CW[1]:
  575. print 'hizo clan con un clan'
  576. AuxClan = Clan.getclanwithnodes(CW[1])
  577. Clan.remove_clan(AuxClan)
  578.  
  579. else:
  580. print 'hizo clan con un nodo'
  581. AuxClan=MyClan('complete')
  582. AuxClan.add_node(CW[1])
  583. Clan.remove_node(CW[1])
  584.  
  585. AddNode(AuxClan,node)
  586. Pack(AuxClan.nodes)
  587. Clan.add_clan(AuxClan)
  588.  
  589. else:
  590. print 'no hizo clan, solo se agrega el nodo y el clan se mantiene primitive'
  591. Clan.add_node(node)
  592. #Pack(Clan.nodes)
  593. class MyClan:
  594.  
  595. def __init__ (self,typeof):
  596. self.clantype = typeof
  597. self.nodes=[]
  598. self.clanlist = []
  599.  
  600. def nodes(self):
  601. return self.nodes
  602.  
  603. def remove_node(self,node):
  604. self.nodes.remove(node)
  605.  
  606. def add_node(self,node):
  607. self.nodes.append(node)
  608.  
  609. def add_nodes_from(self,nodelist):
  610. for n in nodelist:
  611. self.nodes.append(n)
  612.  
  613. def remove_nodes_from(self,nodelist):
  614. for n in nodelist:
  615. self.nodes.remove(n)
  616.  
  617. def add_clan(self, clan):
  618. self.add_node(clan.nodes)
  619. self.clanlist.append(clan)
  620.  
  621. def remove_clan(self,clan):
  622. self.remove_node(clan.nodes)
  623. self.clanlist.remove(clan)
  624.  
  625. def getclanwithnodes(self,nodes):
  626. for k in self.clanlist:
  627. print 'lista de nodes en clanes:', k.nodes, type(k.nodes)
  628. print 'los nodos que se buscan:',nodes, type(nodes)
  629.  
  630. found = False
  631. c = 0
  632. while not found and c < len(self.clanlist):
  633. #if nodes == self.clanlist[c].nodes:
  634. if nodes == str(self.clanlist[c].nodes):
  635. found = True
  636. else:
  637. c+=1
  638. if found:
  639. return self.clanlist[c]
  640. else:
  641. print 'no se encontro el clan'
  642.  
  643. class Edge:
  644. def __init__ (self, labelFrom,sep,labelTo):
  645. self.label = labelFrom+sep+labelTo
  646. self.labelFrom = labelFrom
  647. self.labelTo = labelTo
  648.  
  649. def __str__(self):
  650. return self.label
  651.  
  652. def EdgeFrom(self):
  653. return self.labelFrom
  654.  
  655. def EdgeTo(self):
  656. return self.labelTo
  657.  
  658.  
  659.  
  660. """
  661. MakeSet(x) initializes the decomposition
  662. Find(x) returns representative object of the set containing x
  663. Union(x,y) makes two sets containing x and y respectively into one set
  664. """
  665.  
  666. def MakeSet(x):
  667. x.parent = x
  668. x.rank = 0
  669.  
  670. def Union(x, y):
  671. xRoot = Find(x)
  672. yRoot = Find(y)
  673. if xRoot.rank > yRoot.rank:
  674. yRoot.parent = xRoot
  675. elif xRoot.rank < yRoot.rank:
  676. xRoot.parent = yRoot
  677. elif xRoot != yRoot: # Unless x and y are already in same set, merge them
  678. yRoot.parent = xRoot
  679. xRoot.rank = xRoot.rank + 1
  680.  
  681. def Find(x):
  682. if x.parent == x:
  683. return x
  684. else:
  685. x.parent = Find(x.parent)
  686. return x.parent
  687. ''''''''''''''''''
  688.  
  689. def ElementInX(x,ElementsList): #regresa los elementos de ElementsList que tienen raiz x
  690. xRoot=Find(x)
  691. l=[]
  692. for i in range(xRoot.rank+1):
  693. l.append([])
  694. for element in ElementsList:
  695. if str(Find(element))== str(x):
  696. l[element.rank].append(str(element))
  697. return l
  698.  
  699. def ConstructColorTrees(ColorMatrix,EdgesNodes):
  700. ListColors = []
  701. ListParents= []
  702. for i in range(len(ColorMatrix)):
  703. for j in range(len(ColorMatrix[i])):
  704. FromTo=str(i)+','+str(j)
  705. n = Edge(str(i),',',str(j))
  706. #n = Edge(FromTo)
  707. EdgesNodes.append(n)
  708. MakeSet(n)
  709. if ColorMatrix[i][j] in ListColors:
  710. Index= ListColors.index(ColorMatrix[i][j])
  711. Union(ListParents[Index],n)
  712. else:
  713. ListParents.append(n)
  714. ListColors.append(ColorMatrix[i][j])
  715.  
  716. for i in ListParents:
  717. print ElementInX(i,EdgesNodes)
  718. return ListParents,ListColors
  719. #Usa Pack 1
  720. #MyGraph_1=[['None','black','blue','black','black','black','black'],['black','None','red','black','black','black','black'],['blue','red','None','black','black','black','black'],['black','black','black','None','blue','blue','blue'],['black','black','black','blue','None','black','red'],['black','black','black','blue','black','None','blue'],['black','black','black','blue','red','blue','None']]
  721. #Usa Split/Pack/ClanWith uno no visible
  722. #MyGraph_1=[['None','black','black','red','black','red','red'],['black','None','blue','red','black','red','black'],['black','blue','None','red','black','red','red'],['red','red','red','None','black','red','blue'],['black','black','black','black','None','blue','black'],['red','red','red','red','blue','None','red'],['red','black','red','blue','black','red','None']]
  723. #Pack/ClanWith un nodo visible(el ultimo) 3
  724. #MyGraph_1=[['None','red','blue','blue'],['red','None','black','black'],['blue','black','None','black'],['blue','black','black','None']]
  725. #Pack/ClanWith un clan visible(el ultimo) 4
  726. #MyGraph_1=[['None','red','blue','blue','blue','blue'],['red','None','black','black','black','black'],['blue','black','None','red','red','black'],['blue','black','red','None','red','black'],['blue','black','red','red','None','black'],['blue','black','black','black','black','None']]
  727. #Pack/ClanWith un clan visible(el ultimo) 5
  728. #MyGraph_1=[['None','red','blue','blue','blue','blue'],['red','None','black','black','black','black'],['blue','black','None','red','red','red'],['blue','black','red','None','red','red'],['blue','black','red','red','None','red'],['blue','black','red','red','red','None']]
  729. #primitive y el ultimo nodo no ve a varios nodos 6
  730. #MyGraph_1=[['None','red','blue','black','red','blue','black'],['red','None','black','red','blue','black','red'],['blue','black','None','blue','black','red','blue'],['black','red','blue','None','red','blue','black'],['red','blue','black','red','None','black','blue'],['blue','black','red','blue','black','None','red'],['black','red','blue','black','blue','red','None']]
  731. #2 clanes no visibles 7
  732. #MyGraph_1=[['None','red','red','red','black','red','red','red','black'],['red','None','red','red','red','red','red','red','black'],['red','red','None','black','red','red','red','black','red'],['red','red','black','None','red','red','red','black','black'],['black','red','red','red','None','red','red','red','red'],['red','red','red','red','red','None','black','red','red'],['red','red','red','red','red','black','None','red','red'],['red','red','black','black','red','red','red','None','black'],['black','black','red','black','red','red','red','black','None']]
  733. EdgesNodes =[]
  734. CCT=ConstructColorTrees(MyGraph_1,EdgesNodes)
  735.  
  736. '''
  737. EdgesNodes tiene objetos Edge, sobre los cuales operan directamente MakeSet, y asi Find y Union
  738. '''
  739.  
  740. ActualClan = MyClan('complete')
  741. ActualClan.add_node(str(0))
  742. for i in range(1,len(MyGraph_1)):
  743. AddNode(ActualClan,str(i))
  744. #ActualClan.add_node(str(i))
  745.  
  746. print ActualClan.nodes
Add Comment
Please, Sign In to add comment
Public Pastes
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!