Beefy Boxes and Bandwidth Generously Provided by pair Networks vroom
go ahead... be a heretic

How do I use Graph::Traversal?

by thor (Priest)
on Jul 06, 2005 at 23:26 UTC ( #472970=perlquestion: print w/ replies, xml ) Need Help??
thor has asked for the wisdom of the Perl Monks concerning the following question:

Greetings fellow monks,

I find myself in a situation where I have a data set that's well represented by a Graph. Knowing that CPAN has Graph, I use it. I now want to traverse the graph, but I'm finding the results are not what I expect. Here's a test script:

use strict; use warnings; use Graph; use Graph::Traversal::DFS; my $graph = Graph->new(); $graph->add_edges( ['A','B'], ['B','C'], ['C','D'], ['D','E'], ['A','b'], ['b','c'], ['c','d'], ['d','e']); my $trav = Graph::Traversal::DFS->new($graph); print join("\n", $trav->dfs()); __END__ E D e d c b C B A
I realize that the algorithm is non-deterministic, but it should at least return the correct result. I'd expect that it'd print 'A' and then all the capital letters followed by all the lower-case letters, or vice versa. The docs are unusually sparse. Am I missing something here?


Feel the white light, the light within
Be your own disciple, fan the sparks of will
For all of us waiting, your kingdom will come

Comment on How do I use Graph::Traversal?
Download Code
Re: How do I use Graph::Traversal?
by runrig (Abbot) on Jul 06, 2005 at 23:34 UTC
    You are doing a Depth First Search, so 'E' is the first result. Perhaps what you want is a Breadth First Search?

    Update: that still wouldn't give you what you expect though...I think BFS would return A, B, b, C, c, D, d, E, e).

    Last Update?: What you want is DFS, but use $t->preorder instead of $t->dfs. This returns (A, b, c, d, e, B, C, D, E) which maybe acceptably close to what you are expecting.

    Aha, and use the next_alphabetic option:

    my $trav = Graph::Traversal::DFS->new($graph, next_alphabetic=>1); my $v; print "$v\n" while $v = $trav->preorder; __END__ A B C D E b c d e
      I wish I could use the next_alphabetic. However, my example script is a paper tiger; it doesn't reflect the nature of my data (which is not ordered alphabetically). Looking at my actual data and the Graph module, topological_sort might get the job done.


      Feel the white light, the light within
      Be your own disciple, fan the sparks of will
      For all of us waiting, your kingdom will come

        A topo sort is not strict enough for what you want (it just guarantees parents are returned before children), and in this example returns (A, B, C, D, b, c, d, e, E). Is there any way to force an alphabetical order on your vertices? I'd try adding a fixed length prefix to every vertex as you're adding edges, if at all possible. E.g., start with $p = "0000" (or however many places necessary), and just do $p++ before adding vertex "${p}_$v". And then strip the prefix as each vertex is returned before you need to use it.
Re: How do I use Graph::Traversal?
by Joost (Canon) on Jul 07, 2005 at 00:05 UTC

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://472970]
Approved by Old_Gray_Bear
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (5)
As of 2014-04-19 00:31 GMT
Find Nodes?
    Voting Booth?

    April first is:

    Results (473 votes), past polls