melhor forma de representar um grafo em Python

[Marcelo Valle]

Galera, 

Estou tentando implementar o algoritmo de Kruskal em Python. Eu posso escolher a melhor forma de representar o grafo em questao, que deve ser nao direcional e com pesos. 

Como voces representariam isso em Python? Criariam uma classe propria?

Abracos,

Marcelo.

[Danilo J. S. Bellini]

2017-08-05 12:24 GMT-03:00 Marcelo Valle <mvalle...@bloomberg.net>:

Estou tentando implementar o algoritmo de Kruskal em Python. Eu posso escolher a melhor forma de representar o grafo em questao, que deve ser nao direcional e com pesos. 

Como voces representariam isso em Python? Criariam uma classe propria?

Acho que basta um dicionário {frozenset({node, node}): weight} ou uma lista [(weight, {node, node})]. São convenientes para implementar Kruskal, desde que você mantenha também um set de nós pertencentes ao grafo durante as iterações do algoritmo.

Se puder usar algo menos "feito do zero na unha", tem o Graph do NetworkX: http://networkx.readthedocs.io/en/latest/tutorial.html

--

Danilo J. S. Bellini
---------------
"It is not our business to set up prohibitions, but to arrive at conventions." (R. Carnap)

[Juan Lopes]

Para o algoritmo de Kruskal, você não precisa de nenhuma representação clássica de grafos (nem matriz de adjacência, nem lista de adjacência). Para Kruskal você só precisa da lista de arestas ordenada por peso e, claro, de alguma estrutura que saiba responder "em qual componente conexo" cada vértice está num determinado momento (bem como realizar a conexão de componentes em tempo sublinear). Geralmente, para este fim, usa-se a estrutura de dados conhecida como UNION-FIND.

--
--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasil+unsubscribe@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasil+unsubscribe@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

--

https://github.com/juanplopes

[Juan Lopes]

Marcelo,

Se quiser uma inspiração, aqui tem uma implementação de Kruskal em C++ que fiz uns anos atrás:

https://github.com/juanplopes/icpc/blob/master/uva/11857.cpp

Nesse problema específico eu só estou interessado no maior peso na árvore geradora mínima. Mas é fácil adaptar para obter a árvore em si.

--

https://github.com/juanplopes

[Marcelo Valle]

Danilo e Juan, ajudou muito, valeu!

Juan, minha principal duvida eh justamente esse union find. 

Eu travei um pouco aqui - https://github.com/mvallebr/algo_training/blob/master/greedy/airline_company/airline_kruskal.py#L60

Talvez seja interessante eu criar minha propria estrutura uma vez para tentar entender melhor, mas nao achei que seria tao complicado... Basicamente, eu tenho que manter uma lista de sub arvores.

Vou dar uma olhada na sua solucao Juan!

Abracos,

Marcelo.

python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.

Para mais opções, acesse https://groups.google.com/d/optout.

--

https://github.com/juanplopes

--

https://github.com/juanplopes

[Marcelo Valle]

Acho que consegui resolver. A solucao errada estah nesse link - https://github.com/mvallebr/algo_training/blob/4076afacb5520b2ff833da4c765bb0538af552fe/greedy/airline_company/airline_kruskal.py#L60

A minha solucao, que parece estar correta, estah nesse - https://github.com/mvallebr/algo_training/blob/master/greedy/airline_company/airline_kruskal.py

Aceito quais comentarios :D 

Nao sei se eh possivel deixar o codigo mais simples de forma facil. Eu havia entendido errado o algoritmo a primeira vez que li sobre ele. Eh realmente muito importante implementar uma vez para pegar bem a ideia!

[]s

[Danilo J. S. Bellini]

Aproveitei a thread e fiz um Gist com duas implementações! =)

https://gist.github.com/danilobellini/0c0097e7b816aff27f3370b5f123c1e9

A primeira talvez seja mais fácil para entender o algoritmo de Kruskal, a segunda faz a mesma coisa de maneira otimizada, representando os conjuntos disjuntos de nós como uma floresta (o que costuma ser chamado de "union-find").

[Juan Lopes]

Marcelo, acho que sua implementação não está efetuando path compression (durante o "find"). Por isso, alguém pode fazer um grafo que faz o algoritmo rodar num pior caso de O(m n) operações, em vez de O(m log n).

Além disso, acho que sua implementação seria mais simples se você só guardasse uma lista com as arestas, [(node1, node2, weight)...], ordenando-a por weight antes de executar o algoritmo.

python-brasil+unsubscribe@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasil+unsubscribe@googlegroups.com.

[Marcelo Valle]

Juan, 

Percebi que estava guardando o atributo `nodes` a toa. Removi do codigo. 

Alem disso, percebi que meu codigo nao estava guardando os ranks, lendo esse link descobri para que servem - https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Codigo atualizado - https://github.com/mvallebr/algo_training/blob/master/greedy/airline_company/airline_kruskal.py

Juan, pode me confirmar que meu codigo estah agora fazendo o compression agora? 

A parte da tupla seria mais simples esteticamente, certo? Voce acha que eu compliquei criando uma classe pro grafo? Fiquei em duvida com relacao a isso mesmo.

Abracos,

Marcelo.

[Marcelo Valle]

Danilo, 

Achei fantasticas suas implementacoes, a primeira realmente parecia pseudo codigo, mostrando com teoria dos conjuntos :D

Contudo, algumas coisas me deixaram confuso:

• `sorted(graph, key=graph.__getitem__)` -> nao seria o mesmo que `sorted(graph.keys())` ?
  
• `nodes = list(set.union(*map(set, graph)))` -> algum motivo especial para converter para lista?
• Entendi porque a implementacao 1 funciona, achei bem legal comparar os sets para verificar se a arvore onde se encontram eh a mesma, mas nao entendi o porque se ser frozenset. Qual a vantagem?

Gostei demais da segunda implementacao, pois voce simplesmente usou um dicionario para representar o grafo e o resto instanciou dentro do metodo :D Bem mais inteligente que criar uma classe, como eu fiz. 

Obrigado pela contribuicao, ficou realmente super simples! Voce fez quase tudo o que fiz no meu programa em um unico metodo! :D Vou tentar reescrever seguindo o mesmo principio, pra fixar bem.

Abracos,

Marcelo.

[Marcelo Valle]

Agora saquei o que o Juan tinha falado :D Faltava mesmo o path compression.

Ainda nao ficou bonito como o do Danilo, mas acho que ja simplificou pacas - https://github.com/mvallebr/algo_training/blob/master/greedy/airline_company/airline_kruskal_simpler.py

Algumas funcoes sao por conta da entrada e saida, estou usando o hacker rank.

Galera, obrigado demais por ajudar!

[]s

[Danilo J. S. Bellini]

2017-08-05 22:08 GMT-03:00 Marcelo Valle <mvalle...@bloomberg.net>:

Achei fantasticas suas implementacoes, a primeira realmente parecia pseudo codigo, mostrando com teoria dos conjuntos :D

Valew! =D

 

Contudo, algumas coisas me deixaram confuso:

• `sorted(graph, key=graph.__getitem__)` -> nao seria o mesmo que `sorted(graph.keys())` ?

Não, sorted(graph) é o mesmo que sorted(graph.keys()), mas eu queria ordenar as chaves do dicionário pelos respectivos valores, não pelas próprias chaves do dicionário. Para isso usei o método __getitem__ como função "chave" da ordenação {quanta chave! isto devia ser um parêntesis...}. É possível fazer um sorted com "key" a partir do sorted sem "key":

def sorted_alternative(iterable, key):
    input_list = list(iterable)
    pairs = [(key(k), idx) for idx, k in enumerate(input_list)]
    return [input_list[idx] for unused, idx in sorted(pairs)]

 

Apesar de que pelo sorted(graph, key=lambda e: e[2]) em seu novo código, acho que você já havia entendido =)

• `nodes = list(set.union(*map(set, graph)))` -> algum motivo especial para converter para lista?

Nenhum. Eu tinha feito isso inicialmente por ter pensado em usar índices ao invés dos próprios nós, e para permitir que as chaves do dicionário de entrada fossem tuplas, mas abandonei essa ideia no meio do caminho e esse foi um resíduo. Nesse caso, acho que é muito mais simples fazer apenas um:

nodes = frozenset.union(*graph)

Já atualizei lá no Gist.

• Entendi porque a implementacao 1 funciona, achei bem legal comparar os sets para verificar se a arvore onde se encontram eh a mesma, mas nao entendi o porque se ser frozenset. Qual a vantagem?

Para ser chave de um dicionário, é necessário que o objeto seja hashable, o que é o caso do frozenset mas não do set. É a mesma ideia que permite que tuplas sejam chave de dicionário mas não permite que listas sejam.

 

Gostei demais da segunda implementacao, pois voce simplesmente usou um dicionario para representar o grafo e o resto instanciou dentro do metodo :D Bem mais inteligente que criar uma classe, como eu fiz.

Agradeço, mas não necessariamente uma solução monolítica é melhor ou mais inteligente. No fundo o que me parece ser mais importante é não misturar duas estruturas de dados em uma única "classe". A floresta de conjuntos disjuntos de nós é uma coisa, o grafo é outra. São coisas vinculadas, porém distintas.

Aproveitando, em sua implementação anterior, por ter usado os pesos como chave do dicionário, havia uma otimização "implícita". Quando há pesos repetidos, o número de elementos sendo ordenados diminui, e você poderia ter uma ordenação mais eficiente que o fatídico O(n log n) das ordenações por comparação, já que o valor de n será menor (será o número de pesos distintos, não o número total de arestas). Aliás, a ordenação é justamente o passo mais caro no algoritmo de Kruskal: ele não é linear mas, se a estrutura de entrada já estiver previamente ordenada, para todos os casos práticos é como se fosse linear.
 

Obrigado pela contribuicao, ficou realmente super simples! Voce fez quase tudo o que fiz no meu programa em um unico metodo! :D Vou tentar reescrever seguindo o mesmo principio, pra fixar bem.

Olha eu levando as pessoas para o mau caminho =X... não abandone a ideia de fazer uma versão orientada a objetos! =)

2017-08-05 22:40 GMT-03:00 Marcelo Valle <mvalle...@bloomberg.net>:

Agora saquei o que o Juan tinha falado :D Faltava mesmo o path compression.

Há mais de um path compression, o two-pass que armazena uma pilha para deixar tudo "flat" (recursivo, como você fez), o two-pass que não precisa de uma pilha (por usar a próprio estrutura que armazena os parents), e os one-pass por "splitting" (divide a branch em 2 em cada find) e "halving" (uma única branch com metade da altura). Esse artigo faz uma análise enorme das diversas variantes, acho que vale a pena você ver as tabelas ao final:

http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Union-Find-Tarjan.pdf

No meu Gist, na primeira solução usei "collapsing with naive linking" (não-otimizada) e na segunda usei "one-pass path compression by halving, linking by rank".

Ainda nao ficou bonito como o do Danilo, mas acho que ja simplificou pacas - https://github.com/mvallebr/algo_training/blob/master/greedy/airline_company/airline_kruskal_simpler.py

Ao usar uma função geradora, é estranho ela devolver uma lista vazia em um return. Talvez seja relevante fazer ele devolver um grafo, não apenas um gerador de arestas, mas teria de ver qual representação seria mais conveniente para seu problema. É excelente que seu find_root não utilize uma variável global, mas esse pode ser um início para tornar a coisa orientada a objetos: uma classe para a floresta de conjuntos disjuntos poderia ter esse método, e possuir o container de parent nodes como atributo.

O NetworkX já possui o algoritmo de Kruskal implementado, aproveitei para colocar uma terceira solução no Gist, usando o NetworkX ao invés de implementar o algoritmo.

--

[Marcelo Valle (BLOOMBERG/ LONDON)]

Hey Danilo, 

Pelo desculpas pela demora, obrigado pelos ultimos insights!

Sobre orientacao a objetos, nao fique preocupado, nao quis dizer que nao vejo valor em OO, mas atualmente tenho me tornado um defensor ferrenho de simplicidade de codigo e dos principios de XP, como YAGNI. Se um projeto realmente precisa de OO, eh legal ter, mas eh muito legal ver como o Kruskal, que estava uma coisa mirabolante na minha cabeca, pode ser implementado em um unico metodo, dependendo da necessidade.

Eu cai na questao da melhor estrutura por conta do meu plano de estudos de algoritmos, mas adorei o networkX que voce apresentou. Adoraria saber de aplicacoes reais atualmente usando esse framework, pareceu bem interessante.

Deu vontade de criar um pet project usando graph databases, soh pra aprender mais... O duro eh achar tempo :D

Cara, valeu demais pelos insights!

Abracos,

Marcelo.

--
--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

<< ideas don't deserve respect >>