4

Possuo uma lista de artigos com suas respectivas tags:

artigo1 ['a','b','c']
artigo2 ['a','d','f']
artigo3 ['z','d','f']
...

Preciso criar um grafo que irá relacionar todos os artigos pelas tags. No final terei que ter essa estrutura (Não pode ser outra):

artigo1: ['artigo2']
artigo2: ['artigo1','artigo3']
artigo3: ['artigo2']
...

Inicialmente fiz dois for:

for i in range(0,len(vertices)):
    for j in range(i,len(vertices)):
        for tag in vertices[i].tags:
            if(tag in vertices[j].tags):
                vertices[i].neighbor.append(vertices[j].uid)
                vertices[j].neighbor.append(vertices[i].uid)

Funcionar funciona porém meu arquivo possui 5.500.000 de artigos e irá gastar uma eternidade pois a complexidade é O((n^2)/2). Existe uma forma melhor de realizar essa computação?

2
  • Tem como melhorar sim. Eu fiz um construtor de grafo em Java usando chaves e mapas. Vou mandar a ideia aqui, mas não código final. A velocidade assintótica vai depender basicamente da estrutura para guardar e para resgatar os dados Commented 8/02/2018 às 22:27
  • Não sei se te ajuda, mas já deu uma olhada no igraph? Link: igraph.org/python Commented 9/02/2018 às 2:42

1 Resposta 1

3

Conforme eu tinha comentado, eu fiz um esquema de montagem de grafos em Java baseado em mapas, desde que cada nó tivesse uma chave que o identificasse. O seu caso é ligeiramente diferente, pois cada nó aqui tem várias chaves que o identificam. Você também pode ver como um grafo bipartido a sua questão em específico. Vou focar no grafo bipartido.

A propósito, enquanto escrevia esta resposta, percebi que o seu problema é algo básico para sistemas de bancos de dados dever tratar. Percebi que os bancos de dados tratam do seu problema como uma relação entre duas tabelas, muitos para muitos. E as arestas entre as duas entidades é representada na tabela de ligação. Veja mais aqui. Imagina se para toda ligação entre 2 entidades muitos-muitos fosse de velocidade quadrática?

Você tem dois tipos de dados. O primeiro tipo de dado é artigo. O segundo tipo de dado é tag. Um artigo possui várias tags, e uma tag pode estar em vários artigos. Mas aqui não há ligação tag -- tag ou artigo -- artigo.

Ainda é possível existir essas ligações e continuar com um grafo bipartido em termos. Mas para isso precisamos considerar que existem ligações de tipos distintos e que o grafo é bipartido na classe de ligações tags pertencentes a artigos.

Um exemplo de grafo bipartido:

grafo bipartido

Você já tem aqui a navegação entre os artigos e as tags, nessa direção. Mas para fazer a navegação completa você precisa navegar das tags para os artigos. Como fazer isso? Que tal com um multimapa? Resumindo, um multimapa é uma estrutura de dados que, para uma única chave, retorna uma coleção de elementos.

Tratei de como implementar um multimapa nesta resposta, com uma análise do que é essa estrutura de dados nesta outra resposta.

Então, montamos o multimapa mm_tags_artigos conforme esta resposta e podemos acessar todos os artigos relacionados a uma determinada tag fazendo um acesso a mapa. O seu exemplo traria exatamente:

mm_tags_artigos['a'] ==> [ artigo1 , artigo2 ]
mm_tags_artigos['b'] ==> [ artigo1 ]
mm_tags_artigos['c'] ==> [ artigo1 ]
mm_tags_artigos['d'] ==> [ artigo2 , artigo3 ]
mm_tags_artigos['f'] ==> [ artigo2 , artigo3 ]
mm_tags_artigos['z'] ==> [ artigo3 ]

Então, como saber quais são os artigos relacionados a um outro? Bem, pegamos todas as arestas a duas posições de distâncias no grafo bipartido. Como o grafo é bipartido, tudo a uma distância par de arestas de um artigo é um artigo também. Ao pegar todos os artigos a dois saltos de distância do meu artigo alvo, teremos o seguinte conjunto:

Descrição matemática de artigos a dois saltos de distância

Aqui, S_artigo é o conjunto formado por todos os artigos que se relacionam diretamente com as tags do artigo artigo. Claro, aqui o próprio artigo também seria retornado, então bastaria remover o artigo que se deseja saber os relacionados desse conjunto.

Basicamente, após ter o multimapa montado, bastaria da seguinte linha que então você obteria todos os artigos relacionados ao artigo x (obrigado ao @AndersonCarlosWoss por me mostrar o itertools.chain):

[artigo_vizinho for artigo_vizinho, g in groupby(sorted(chain(*[mm_tag_artigo[tag] for tag in x.neighbors]), key = str)) if artigo_vizinho != x]

Isso vai retornar uma lista com todos os artigos vizinhos, alcançados a partir das tags de x. Explicando cada passo, de dentro pra fora:

mm_tag_artigo[tag]

Estou pegando uma lista com todos os artigo que possuem a tag tag. mm_tag_artigo é o multimapa que, dada uma tag, retorna a lista de artigos associada a ela.

[mm_tag_artigo[tag] for tag in x.neighbors]

Para cada tag que x contenha, eu retorno uma lista com seus vizinhos. Se x fosse o artigo2 do exemplo, os elementos seriam mais ou menos esses:

[
  # para a tag 'a'
  [artigo1, artigo2],

  # para a tag 'd'
  [artigo2, artigo3],

  # para a tag 'f'
  [artigo2, artigo3]
]

Se fosse artigo1:

[
  # para a tag 'a'
  [artigo1, artigo2],

  # para a tag 'b'
  [artigo1],

  # para a tag 'c'
  [artigo1]
]
*[mm_tag_artigo[tag] for tag in x.neighbors]

Usando o operador explode antes da lista, para que cada elemento da lista seja passado como um argumento distinto da função que chama.

chain(*[mm_tag_artigo[tag] for tag in x.neighbors])

Aqui estou juntando as listas obtidas em um único iterável. Para x = artigo2, obteríamos algo nesse formato:

[ artigo1, artigo2, artigo2, artigo3, artigo2, artigo3 ]

Já para x = artigo1:

[ artigo1, artigo2, artigo1, artigo1 ]

Documentação do chain: https://docs.python.org/3/library/itertools.html#itertools.chain

sorted(chain(*[mm_tag_artigo[tag] for tag in x.neighbors]), key = str)

Agora estou ordenando o resultado obtido. Talvez objetos do tipo artigo não sejam diretamente ordenáveis, então estou usando como chave classificatória sua representação de string para realizar a ordenação (key = str). Fiz testes para quando não há sobrescrita do método __str__ da classe de artigos, portanto ele imprime uma string distinta para cada objeto.

Documentação do sorted: https://docs.python.org/3/library/functions.html#sorted

Claro, se o método __str__ de um artigo for sobrescrito de modo a permitir dois objetos distintos com a mesma representação, aí danou o próximo passo.

A intenção de ordenar aqui é apenas para poder agrupar os objetos unicamente, que isso é feito no próximo passo:

groupby(sorted(chain(*[mm_tag_artigo[tag] for tag in x.neighbors]), key = str))

Estou agrupando os elementos de modo que eu consiga obter apenas um de cada, sem precisar de repetições. Note que essa função funciona em tempo linear, como se fosse o comando uniq do Unix, agrupando apenas elementos consecutivos.

Documentação do groupby: https://docs.python.org/3/library/itertools.html#itertools.groupby

artigo_vizinho for artigo_vizinho, g in groupby(sorted(chain(*[mm_tag_artigo[tag] for tag in x.neighbors]), key = str))

A função groupby retorna uma lista de tuplas, sendo elas:

  • o elemento agrupador
  • o grupo formado por aquele elemento

Não nos interessa o grupo, então estou descartando-o, ficando apenas com o agrupador, que no caso é um artigo chamado de artigo_vizinho.

artigo_vizinho for artigo_vizinho, g in groupby(sorted(chain(*[mm_tag_artigo[tag] for tag in x.neighbors]), key = str)) if artigo_vizinho != x

Apenas condicionando pegar os artigos vizinhos, sem repetir o artigo x.

[artigo_vizinho for artigo_vizinho, g in groupby(sorted(chain(*[mm_tag_artigo[tag] for tag in x.neighbors]), key = str)) if artigo_vizinho != x]

Bem, transformando esse resultado obtido em lista. Não tem muito porquê disso, mania minha mesmo.

Só como detalhe, não se esqueça de que sorted é built-in, já está disponível para o Python, enquanto que chain e groupby precisam ser importados, eles estão no módulo itertools. Para usar do jeito que usei, importe assim: from itertools import chain, groupby.

Veja funcionando no ideone.

5
  • Eu entendi toda a ideia de sua resposta, estava pensando algo parecido, mas eu parei até em criar o multimapa. A unica coisa que não entendi foi o '*' e o fato da necessidade de ordenar(Talvez seria pro chain?). Commented 9/02/2018 às 11:36
  • 1
    @ViniciusMorais o ordenar na verdade é por conta do groupby. Tem mais detalhes na documentação. Sobre o *, tente os seguintes experimentos: chain([1,2,3], [4,5,6]) (simulando com o asterisco); chain([ [1,2,3], [4,5,6] ]) (simulando sem o asterisco) Commented 9/02/2018 às 12:04
  • 1
    Outra coisa, qual seria a nova complexidade? Commented 9/02/2018 às 12:23
  • @ViniciusMorais puts, esqueci disso! Mal aí... dependendo da eficiência da busca e da inserção do dicionário, acho que é o(n + e log e + e), onde e é a quantidade de arestas média por vértice. Tem alternativa com tempo assintótico menor ainda, usando um grafo apenas de artigos, não um grafo bipartido, mas a alternativa é um passo de abstração a mais e não consegui digitar ontem, estava cansado Commented 9/02/2018 às 12:44
  • Muito obrigado. Commented 9/02/2018 às 14:43

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .