Dúvida na implementação de grafos sem dicionários

[RicardoCostaTW]

Boa Pessoal,

Tenho agora um trabalho para fazer, na cadeira de Web Semantica que consiste na criação de um grafo e implementações sobre ele de adicionar, remover, pesquisa e listar, mas sem recurso a dicionarios. O que me recomendam? Se não posso usar dicionários, não vou poder utilizar matrizes?

Edited March 21, 2013 at 03:40 PM by RicardoCostaTW

[Pedro C.]

Tudo o que um dicionário faz é emulável a partir de lista (acho eu pelo menos). Um pequeno tutorial que mostra as operações que falaste mas para listas:

In [10]: key_list = ['a','b','c','d']  # Estou a criar uma lista com nomes

In [11]: info_list = [3,9,13,7]  # Outra com o atributo desses nomes

In [12]: key_list.index('b') # Pergunto em que indice está o nome 'b' (pesquisar?)
Out[12]: 1

In [13]: info_list[1]  # Verifico qual é o atributo desse indice e consequentemente do 'b'.
Out[13]: 9

In [14]: del(key_list[1])  # Removo o indice do 'b'

In [15]: del(info_list[1]) # E também o seu atributo

In [16]: key_list,info_list  # listo os dois
Out[16]: (['a', 'c', 'd'], [3, 13, 7])

In [17]: key_list.append('e') # Vou acrescentar um novo nome 'e'.

In [18]: info_list.append(19) # E um novo atributo a esse nome.

In [19]: key_list,info_list  # listo novamente as listas. Repara que o append acrescenta sempre à ultima casa pelo que não dás cabo dos indices dos anteriores.
Out[19]: (['a', 'c', 'd', 'e'], [3, 13, 7, 19])

Espero que ajude.

[RicardoCostaTW]

Olá Pedro,

Desde já obrigado pela resposta. A minha dúvida é a seguinte.. Supondo que num grafo tenho o ponto A(id_pessoa), B(Ricardo) e a linha que os une ser o predicado "nome" , como faço isso com listas.

[Pedro C.]

Bem, se o fizeres com listas então terias de ter uma lista que guardasse essas informações todas ou então teres uma lista para ids, outra para nomes e outra para linhas. Desde que mantenhas uma indexação adequada as coisas correm bem tal como no exemplo que meti acima.

Depedendo do nivel de sofisticação do teu código podes simplificar mais se construires os teus próprios objectos em classes, por exemplo. Uma classe seria construida desta maneira:

class grafo:
   def __init__(self,ID,name,connection):
       self.ID = ID
       self.name = name
       self.connection = connection

   def indexation_ID(self,ID):
       index = []
       for i in xrange(len(self.ID)):
           if self.ID[i]==ID:
               index.append(i)
       return index

   def call_by_ID(self,ID):
       index = self.indexation_ID(ID)
       names = []
       connections = []
       for i in xrange(len(index)):
           names.append(self.name[index[i]])
           connections.append(self.connection[index[i]])
       return names,connections

   def remove_by_ID(self,ID):
       index = self.indexation_ID(ID)
       c = 0
       for i in xrange(len(index)):
           del self.name[index[i]-c]
           del self.connection[index[i]-c]
           del self.ID[index[i]-c]
           c = c + 1

   def new(self,ID,name,connection):
       self.name.append(name)
       self.connection.append(connection)
       self.ID.append(ID)

No código a seguir já estou a fazer uso dela. Estou a criar o objecto g (da classe grafo) e vou chamando a pequena api que tenho dentro dela. Repara como ele é dinâmico.

ID = [1,2,3,4,3,2,6,7,8,9]
name = ['a','b','c','d','e','f','g','h','i','j']
connection = ['ab','ac','bc','ab','ac','bc','ab','ac','bc','ij']

g = grafo(ID,name,connection)
g.new(19,'e','bc')
print g.call_by_ID(3)
g.remove_by_ID(3)
print g.call_by_ID(3)

O resultado do script é:

(['c', 'e'], ['bc', 'ac'])
([], [])

Se isto não chegar para resolveres o problema então sugiro que apresentes o código com dicionários para que as pessoas possam sugerir-te como fazeres as coisas com outro tipo de objectos.

[RicardoCostaTW]

eu tinha feito assim, mas o prof começou a dizer que era melhor com listas e não sei o que, ei:

class grafo(object):
   def __init__(self):
       self.spo = {}
       self.pos = {}
       self.osp = {}
   def add(self ,suj, pred, obj):
        self.addToIndex(self.spo, suj, pred, obj)
        self.addToIndex(self.pos, pred, obj, suj)
        self.addToIndex(self.osp,obj, suj, pred)


   def addToIndex(self, index, a, b, c):
       if a not in index:
           index[a]={b:set([c])}
       elif b not in index[a]:
           index[a][b]=set([c])
       else:
           index[a][b].add(c)
   def returnId_person(self,name):
       pessoa = self.triples((None,"name",name))
       id = None
       for x,y,z in pessoa:
           id = self.getSubject(y,z)
       return id

   def returnNameFromID(self,id):
       id = self.triples((id,"name",None))
       name = None
       for x,y,z in id:
           name = self.getObject(x,y)
       return name
   ############################################# functions date ######################################################
   def listaPessoas(self):
       pessoas = self.triples((None,"name",None))
       nameList = list()

       for x,y,z in pessoas:
           nameList.append(z)
       return nameList
   def actividadePessoa(self, name):
          id = self.returnId_person(name)
          atividade  = self.triples((id,"activity",None))
          for x,y,z in atividade:
              atividadePessoa = self.getObject(x,y)
          return atividadePessoa

   def pessoasMesmaActividade(self, actividade):
       pessoas = list()
       atividade = self.triples((None,"activity",actividade))
       for x,y,z in atividade:
           pessoas.append(self.returnNameFromID(x))
       return pessoas
   def pessoaMesmaReligiao(self, religiao):
       pessoas = list()
       rel = self.triples((None,"religion",religiao))
       for x,y,z in rel:
           pessoas.append(self.returnNameFromID(x))
       return pessoas

   ##################################################################################################################

   def loadFromCSV(self):
       manageFiles.readFile()
       manageFiles.writeFile()
       manageFiles.getNomesFile()
       f = open("user.csv", "rb")
       reader = csv.reader(f)
       for sub, pred, obj in reader:
           sub=unicode(sub, "UTF-8")
           pred = unicode(pred, "UTF-8")
           obj=unicode(obj, "UTF-8")
           self.add(sub,pred,obj)
       f.close()
   def getObject(self, sub, pred):
       try:
           return(self.triples((sub, pred, None)).next()[2])
       except:
           return None

   def getPredicate(self, obj, sub):
       try:
           return(self.triples((sub, None, obj)).next()[1])
       except:
           return None

   def getSubject(self, pred, obj):
       try:
           return(self.triples((None, pred, obj)).next()[0])
       except:
           return None
   def triples(self, (sub, pred, obj)):
       try:
           if sub != None:
               if pred != None:
                   if obj != None:
                       if obj in self.spo[sub][pred]:
                           yield (sub, pred, obj)
                   else:
                       for retObj in self.spo[sub][pred]:
                           yield (sub, pred, retObj)
               else:
                   if obj != None:
                       for retPred in self.osp[obj][sub]:
                           yield (sub, retPred, obj)
                   else:
                       for retPred, objSet in self.spo[sub].items():
                           for retObj in objSet:
                               yield (sub, retPred, retObj) 
           else:
               if pred != None:
                   if obj != None:
                       for retSub in self.pos[pred][obj]:
                           yield (retSub, pred, obj)
                   else:
                       for retObj, subSet in self.pos[pred].items():
                           for retSub in subSet:
                               yield (retSub, pred, retObj)
               else:
                   if obj != None:
                       for retSub, predSet in self.osp[obj].items():
                           for retPred in predSet:
                               yield (retSub, retPred, obj)
                   else:
                       for retSub, predSet in self.spo.items():
                           for retPred, objSet in predSet.items():
                               for retObj in objSet:
                                   yield (retSub, retPred, retObj)
       except KeyError:
           pass

Edited March 21, 2013 at 11:12 PM by thoga31
GeSHi

[Pedro C.]

Ricardo não sei se estou a perceber bem onde queres chegar. No código que tu meteste não só fazes uso de dicionários como também de listas. Se tu queres emular a utilização de um dicionário faz uma classe que faça essa emulação e em vez de chamares as { } de dicionário chamas a classe gerida por listas.

Outra hipótes é reformulares o teu código para estar com listas desde o principio.

De qualquer maneira qual é a operação que queres fazer com listas que não consegues?, ou então qual é a operação que fazes com dicionários que não consegues fazer sem eles?

[RicardoCostaTW]

Refiz o código todo, se me podesses dar um feedback agradecia:

import csv
class grafo():
ID = 0

class predicado(grafo):
idPredicado = 0
predicado = None
conj_objectos = list()
def __init__(self,idPessoa, pred, conj_objectos = list()):

		predicado.idPredicado +=1
		self.ID = idPessoa
		self.predicado = pred
		self.conj_objectos = conj_objectos

listaPessoas = list() #lista principal
atividades = ['natacao','futebol']
nome = ['ricardo']
pessoa1 = list()
pessoa1.append(predicado(1,"nome", nome))
pessoa1.append(predicado(1,"atividade", atividades))
listaPessoas.append(pessoa1)

#####################################################################################################################################
def lista(lista = list()):
k = 0
while k<len(lista):
	for x in lista.__getitem__(k):
		 for y in x.conj_objectos:
			print x.ID
			print x.predicado
			print y
	k+=1
#listaPredicados = se a pessoa quiser escolher varios perdicados na mesma funcao
def inserePessoa(id, pred, atividades,listaPes = list()):
atividadeLista = [atividades]
k = 0
while k<len(listaPes):
	for x in listaPes.__getitem__(k):
		  if x.ID == id:
			  if x.predicado:
				  listaPes.__getitem__(k).append(predicado(id,pred,atividadeLista))
				  return
		  else :
				  pessoa = list()
				  pessoa.append(predicado(id,pred,atividadeLista))
				  listaPes.append(pessoa)
				  return

	k+=1

def loadFromCSV():
	f = open("user.csv", "rb")
	reader = csv.reader(f)
	for sub, pred, obj in reader:
		sub=unicode(sub, "UTF-8")
		pred = unicode(pred, "UTF-8")
		obj=unicode(obj, "UTF-8")
		inserePessoa(sub,pred,obj,listaPessoas)
	f.close()

def apagaPessoa(nomePessoa, listaPes = list()):

k=0
while k<len(listaPes):
	for x in listaPes.__getitem__(k):
		 for y in x.conj_objectos:
			 if y == nomePessoa:
				 print nomePessoa
				 del listaPes[k]
				 return
	k+=1
#########################################################################################################################################

loadFromCSV()
inserePessoa(3,"religiao","catolica",listaPessoas)
inserePessoa(4,"nome","joao",listaPessoas)
apagaPessoa("joao",listaPessoas)
lista(listaPessoas)  

raw_input()

Achas que está razoável?

Edited March 22, 2013 at 09:46 PM by RicardoCostaTW
GeSHi

[Pedro C.]

Se funciona para aquilo que tu pretendes suponho que sim. Não consigo experimentar porque ele faz a leitura de um ficheiro que não tenho.

De qualquer maneira aponto alguns pontos que me parecem desnecessários:

a) Não vejo vantagem em teres uma classe grafo dado que apenas a estas a usar como input da classe predicado e apenas tem uma variável lá dentro que até é constante.

b) A meu ver o loadFromCSV devia ter a variável listaPessoas como argumento e não partir do principio que é uma variável global (aliás tu usas um método diferente para a inserePessoas ou apagaPessoas na qual a variável listaPessoas já entra como argumento e não como variável global).

c) Não tens algumas das funções que dizias ser necessário como pesquisar por exemplo.

d) Pessoalmente para fins de leitura e reutilização do código eu tentaria criar mesmo o objecto classe listaPessoas e lá dentro é que metia as funções para gestão da classe.

Consegues dizer-me um caso possível em que o teu programa iria ser usado?, e se sim, para que fins? A partir dai o código é construido consoante a necessidade.

Dando um exemplo possível para o que estou a pedir:

-> tenho um ficheiro que vem em linhas diferentes o nome de uma pessoa, seguido da sua preferência religiosa, e finalmente os desportos que pratica. Preciso de fazer um script que guarde estas informações e agora saber qual é preferência religiosa maioritária das pessoas que praticam natação. Ou então qual é o desporto mais praticado entre budistas. Ou então qual o nome mais comum entre os participantes...., e por ai adiante.

[RicardoCostaTW]

Anotei tudo 👍

Vou seguir os teus conselhos

[RicardoCostaTW]

Pedro C , percebes alguma coisa de como retirar inferências de grafos?

[Pedro C.]

Assumo que te refiras a inferência estatística. Raras vezes trabalhei com grafos mas a matemática há de ser semelhante. O que pretendes fazer?

[RicardoCostaTW]

Olá Pedro,

Pretendo por exemplo:

Tenho um idPessoa->peso->1kg

Tirar uma inferênciapor exemplo 1kg é igual a 1000gramas

[Pedro C.]

Podes criar uma classe para o próprio peso no qual fica inserido o seu valor e a sua unidade. A classe calcularia automáticamente a conversão de 1 kg para outras unidades:

['g',cg',dg','kg','hg','dg','t'] -> ['grama','centigrama','decigrama','quilograma','hectagrama','decagrama','tonelada'] -> [1000,100,10,1,0.1,0.01,0.001]

E depois era uma questão de teres uma função na qual entraria o valor e a unidade para ele ver se era igual ou não ao valor de comparação. Isto serve?