<div dir="ltr">Oi Blabos,<div><br></div><div>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.</div>
<div><div><br></div><div>[ ]'s<br><div class="gmail_extra"><br><br><div class="gmail_quote">2013/9/20 Blabos de Blebe <span dir="ltr"><<a href="mailto:blabos@gmail.com" target="_blank">blabos@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Opa,<div><br></div><div>Nos capítulos anteriores...</div><div><br></div><div>Eu procurei ajuda sobre como fazer uma conta e como executar essa conta de forma assíncrona em relação à aplicação web.</div>
<div><br></div><div>Os donos dos resultados dessa conta relacionam-se entre si de forma que eu modelei esse relacionamento através de um grafo direcionado.</div><div><br></div><div>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.</div>
<div><br></div><div>É a partir dessa informação que eu *começo* o meu trabalho.</div><div><br></div><div>Obrigado a todos que contribuíram com sugestões que eu já usei, e com sugestões que ainda vou usar.</div>
<div><br></div><div>[]'s</div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">2013/9/19 Wagner Arbex <span dir="ltr"><<a href="mailto:arbex@arbex.pro.br" target="_blank">arbex@arbex.pro.br</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Opa, tb fiquei curioso sobre a sua aplicação, Blabos.<br>
<br>
Fiz uma aplicação, na mão, em que precisava achar os componentes<br>
conexos e os ciclos e, depois, fiz uma outra versão usando as rotinas<br>
do módulo Graph-0.96 (<a href="http://search.cpan.org/perldoc?Graph" target="_blank">http://search.cpan.org/perldoc?Graph</a>), que vc tb<br>
citou. Ainda não gostei do que fiz e estou trabalhando em uma versão<br>
mais "sofisticada", tentando aplicar aprendizado de máquina, fazendo<br>
com que a rotina "adquira conhecimento" sobre os dados que recolhe ao<br>
longo de cada componente conexo que percorre.<br>
<br>
Posso estar enganado, mas não me lembro de ter visto ninguém falando<br>
sobre grafos a lista, por isso estou fiquei curioso qto à sua<br>
aplicação.<br>
<br>
Acho que existem outras questões que vc pode querer considerar no<br>
caminho entre dois vértices em um grafo. P. ex., só existe um caminho<br>
entre qq dois nós? Interessa saber se existe outro caminho? O que está<br>
sendo procurado é qq caminho ou um caminho específico, p. ex., o<br>
caminho mais curto ou caminho mais rápido? Existem "pesos" nas arestas<br>
entre os dois nós? Lembrando que uma árvore é um caso particular de<br>
grafo, o grafo é realmente um grafo ou uma árvore?<br>
<br>
Gostei da conversa e se eu achar que posso ajudar, vou tentar<br>
contribuir com alguns centavos.<br>
<br>
[]s, W.<br>
<br>
2013/9/19 Hernan Lopes <<a href="mailto:hernanlopes@gmail.com" target="_blank">hernanlopes@gmail.com</a>>:<br>
<div><div>> Blabos, o que vc quer fazer?<br>
><br>
> 2013/9/19 Blabos de Blebe <<a href="mailto:blabos@gmail.com" target="_blank">blabos@gmail.com</a>><br>
>><br>
>> E aí pessoal,<br>
>><br>
>> Estou precisando calcular a distância entre nós em um grafo direcionado.<br>
>><br>
>> É aquele algoritmo clássico que tem no Cormen ou qualquer livro decente do<br>
>> ramo.<br>
>><br>
>> No cpan eu achei de interessante:<br>
>><br>
>> <a href="https://metacpan.org/module/JHI/Graph-0.96/lib/Graph.pod" target="_blank">https://metacpan.org/module/JHI/Graph-0.96/lib/Graph.pod</a><br>
>> <a href="https://metacpan.org/module/Paths::Graph" target="_blank">https://metacpan.org/module/Paths::Graph</a><br>
>> <a href="https://metacpan.org/module/Boost::Graph" target="_blank">https://metacpan.org/module/Boost::Graph</a><br>
>> <a href="https://metacpan.org/module/DBIx::Path" target="_blank">https://metacpan.org/module/DBIx::Path</a><br>
>><br>
>> Gostaria de ouvir a opinião de vcs a respeito, e se tiverem outras<br>
>> sugestões, sou todo ouvidos.<br>
>><br>
>> []'s<br>
>><br>
>><br>
>><br>
>> =begin disclaimer<br>
>> Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
>> SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
>> L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
>> =end disclaimer<br>
>><br>
><br>
><br>
> =begin disclaimer<br>
> Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
> SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
> L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
> =end disclaimer<br>
><br>
<br>
<br>
<br>
</div></div><span><font color="#888888">--<br>
Wagner Arbex, DSc<br>
Bioinformática e modelagem matemática e computacional de biossistemas<br>
<br>
<a href="http://www.arbex.pro.br/" target="_blank">http://www.arbex.pro.br/</a><br>
</font></span><div><div>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
</div></div></blockquote></div><br></div>
</div></div><br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Bruno C. Buss<br><a href="http://www.brunobuss.net" target="_blank">http://www.brunobuss.net</a>
</div></div></div></div>