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

[Bruno Buss]

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 at 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 at 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 at gmail.com>:
>> > Blabos, o que vc quer fazer?
>> >
>> > 2013/9/19 Blabos de Blebe <blabos at 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 at 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 at 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 at 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 at pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>


-- 
Bruno C. Buss
http://www.brunobuss.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130920/51cd351c/attachment.html>