[SP-pm] Distância entre nós em um grafo

[Blabos de Blebe]

Opa,

@Buss @Carlos, correto e correto.

Nesse caso específico eu conscientemente abri mão da eficiência em prol do
"já esta implementado". Foram 4 linhas usando o DBIx::Class + Graph, desde
buscar todos os dados até encontrar o menor path.

Não é a melhor solução, mas é uma solução suficientemente boa dentro dos
parâmetros que eu preciso neste momento.

Eu to usando SQLite por enquanto, mas o Postgres não tem algo assim
embutido não?

Fico grato por estar numa lista onde sempre encontro várias dicas cada uma
melhor que a outra.

[]'s


2013/9/20 Bruno Buss <bruno.buss em gmail.com>

> Oi Blabos,
>
> Pelo o que você disse, no seu grafo as arestas não tem peso (ou todas tem
> o mesmo peso, e.g. 1) e o que você quer fazer é contar a distância entre 2
> nós do grafo, então você pode utilizar um algoritmo mais simples como uma
> busca em largura para calcular a distância entre dois nós. Se sua
> representação do grafo for através de lista de adjacências, a BFS roda em
> tempo linear no tamanho do grafo - O(n + m) - enquanto a melhor
> implementação conhecida para o Dijkstra, com heap de fibonacci, fica em
> (n*logn + m) apesar de ser bem mais complexa de implementar.
>
> [ ]'s
>
>
> 2013/9/20 Blabos de Blebe <blabos em gmail.com>
>
>> Opa,
>>
>> Nos capítulos anteriores...
>>
>> Eu procurei ajuda sobre como fazer uma conta e como executar essa conta
>> de forma assíncrona em relação à aplicação web.
>>
>> Os donos dos resultados dessa conta relacionam-se entre si de forma que
>> eu modelei esse relacionamento através de um grafo direcionado.
>>
>> Eu só precisava saber a quantos nós cada um deles está um do outro, eu
>> nem preciso do path em si. Um simples scalar( Graph::SP_Dijkstra( a, b ) )
>> - 1 já me dá isso.
>>
>> É a partir dessa informação que eu *começo* o meu trabalho.
>>
>> Obrigado a todos que contribuíram com sugestões que eu já usei, e com
>> sugestões que ainda vou usar.
>>
>> []'s
>>
>>
>> 2013/9/19 Wagner Arbex <arbex em arbex.pro.br>
>>
>>> Opa, tb fiquei curioso sobre a sua aplicação, Blabos.
>>>
>>> Fiz uma aplicação, na mão, em que precisava achar os componentes
>>> conexos e os ciclos e, depois, fiz uma outra versão usando as rotinas
>>> do módulo Graph-0.96 (http://search.cpan.org/perldoc?Graph), que vc tb
>>> citou. Ainda não gostei do que fiz e estou trabalhando em uma versão
>>> mais "sofisticada", tentando aplicar aprendizado de máquina, fazendo
>>> com que a rotina "adquira conhecimento" sobre os dados que recolhe ao
>>> longo de cada componente conexo que percorre.
>>>
>>> Posso estar enganado, mas não me lembro de ter visto ninguém falando
>>> sobre grafos a lista, por isso estou fiquei curioso qto à sua
>>> aplicação.
>>>
>>> Acho que existem outras questões que vc pode querer considerar no
>>> caminho entre dois vértices em um grafo. P. ex., só existe um caminho
>>> entre qq dois nós? Interessa saber se existe outro caminho? O que está
>>> sendo procurado é qq caminho ou um caminho específico, p. ex., o
>>> caminho mais curto ou caminho mais rápido? Existem "pesos" nas arestas
>>> entre os dois nós? Lembrando que uma árvore é um caso particular de
>>> grafo, o grafo é realmente um grafo ou uma árvore?
>>>
>>> Gostei da conversa e se eu achar que posso ajudar, vou tentar
>>> contribuir com alguns centavos.
>>>
>>> []s, W.
>>>
>>> 2013/9/19 Hernan Lopes <hernanlopes em gmail.com>:
>>> > Blabos, o que vc quer fazer?
>>> >
>>> > 2013/9/19 Blabos de Blebe <blabos em gmail.com>
>>> >>
>>> >> E aí pessoal,
>>> >>
>>> >> Estou precisando calcular a distância entre nós em um grafo
>>> direcionado.
>>> >>
>>> >> É aquele algoritmo clássico que tem no Cormen ou qualquer livro
>>> decente do
>>> >> ramo.
>>> >>
>>> >> No cpan eu achei de interessante:
>>> >>
>>> >> https://metacpan.org/module/JHI/Graph-0.96/lib/Graph.pod
>>> >> https://metacpan.org/module/Paths::Graph
>>> >> https://metacpan.org/module/Boost::Graph
>>> >> https://metacpan.org/module/DBIx::Path
>>> >>
>>> >> Gostaria de ouvir a opinião de vcs a respeito, e se tiverem outras
>>> >> sugestões, sou todo ouvidos.
>>> >>
>>> >> []'s
>>> >>
>>> >>
>>> >>
>>> >> =begin disclaimer
>>> >>    Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>>> >>  SaoPaulo-pm mailing list: SaoPaulo-pm em pm.org
>>> >>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
>>> >> =end disclaimer
>>> >>
>>> >
>>> >
>>> > =begin disclaimer
>>> >    Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>>> >  SaoPaulo-pm mailing list: SaoPaulo-pm em pm.org
>>> >  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
>>> > =end disclaimer
>>> >
>>>
>>>
>>>
>>> --
>>>    Wagner Arbex, DSc
>>>    Bioinformática e modelagem matemática e computacional de biossistemas
>>>
>>>    http://www.arbex.pro.br/
>>> =begin disclaimer
>>>    Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>>>  SaoPaulo-pm mailing list: SaoPaulo-pm em pm.org
>>>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
>>> =end disclaimer
>>>
>>
>>
>> =begin disclaimer
>>    Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>>  SaoPaulo-pm mailing list: SaoPaulo-pm em pm.org
>>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
>> =end disclaimer
>>
>>
>
>
> --
> Bruno C. Buss
> http://www.brunobuss.net
>
> =begin disclaimer
>    Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
>  SaoPaulo-pm mailing list: SaoPaulo-pm em pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>
-------------- Pr�xima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130920/4e257f5b/attachment-0001.html>