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:
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:
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.