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