Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

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

Replies are listed 'Best First'.
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

      Greetings, I'm exploring the Graph::Traversal::DFS in order to compute all possible paths of a directed graph. This solution here: Seems to do what I want: provides all paths of a $tree variable as an array of array references. The problem is that the code is too obscure for me understand at the moment and I've already implemented in my code elsewhere and would like to continue using it. All paths shouldn't be a major computational problem in this case because the graphs will be relatively simple and I could get the components first as a simplification. Here's a simple example for a set of vertices called Group 26:

       print qq[$_->{dna}\t$_->{score}\n] foreach @{$RNA_SEQ{$RNA[0]}->{alignments}};

      opera_scaffold_55153 28.9909638554217

      opera_scaffold_12001 26.5813253012048

      opera_scaffold_221202 19.6159638554217

      opera_scaffold_220117 15.210843373494

      opera_scaffold_184033 1.35542168674699

      # The relationship among the vertices is in an array of hash reference called @E. # Each element of @E looks like this:
      {v1 => $vertex1, v2 => $vertex2, rna => $rna, state => 1 } # build a directed graph with this data, vertices have a weight ( scor +e ) my $g = Graph->new(); for my $edge ( @E ) { my %weights = map { $_->{dna} => $_->{score} } @{$RNA_SEQ{$edge->{ +rna}}->{alignments}}; $g->add_weighted_vertices( $edge->{v1}, $weights{$edge->{v1}}, $ed +ge->{v2}, $weights{$edge->{v2}}); $g->add_edge ( $edge->{v1}, $edge->{v2} ); } # Print out the graph to see what it looks like foreach ( @E ) { my $w1 = $g->get_vertex_weight($_->{v1}); my $w2 = $g->get_vertex_weight($_->{v2}); print qq[$_->{v1} --> $_->{v2}\t$w1 $w2\n]; } # Output the edges of the graph with weights for each vertex

      opera_scaffold_55153 --> opera_scaffold_221202 28.9909638554217 19.6159638554217

      opera_scaffold_221202 --> opera_scaffold_184033 19.6159638554217 1.35542168674699

      opera_scaffold_184033 --> opera_scaffold_220117 1.35542168674699 15.210843373494

      opera_scaffold_220117 --> opera_scaffold_12001 15.210843373494 26.5813253012048

      # traverse the graph using DFS my $t = Graph::Traversal::DFS->new($g); my @v = $t->preorder; print qq[Preorder:\n]; print qq[$_\t] foreach @v;

      Preorder: opera_scaffold_221202 opera_scaffold_184033 opera_scaffold_220117 opera_scaffold_12001 opera_scaffold_55153

      @v = $t->postorder; print qq[Postorder:\n]; print qq[$_\t] foreach @v;

      Postorder: opera_scaffold_12001 opera_scaffold_220117 opera_scaffold_184033 opera_scaffold_221202 opera_scaffold_55153

      my @r = $t->roots; print qq[Roots:\n]; print qq[$_\t] foreach @r;

      Roots: opera_scaffold_221202 opera_scaffold_55153

      Postorder gives me what I want in this example, albeit in the reverse order. However this is a simple example in which the graph has just one single path.

      Group 16 looks like this:

      Graph Edges:

      opera_scaffold_131077 --> opera_scaffold_45770 2.43611177454024 54.8841652734655

      opera_scaffold_102945 --> opera_scaffold_23837 13.8762837353714 19.871029376642


      opera_scaffold_45770 opera_scaffold_102945 opera_scaffold_23837 opera_scaffold_131077


      opera_scaffold_45770 opera_scaffold_23837 opera_scaffold_102945 opera_scaffold_131077


      opera_scaffold_45770 opera_scaffold_102945 opera_scaffold_131077

      Clearly not what I'm looking for. There's two paths in this graph represented by the two edges: opera_scaffold_131077 --> opera_scaffold_45770 and opera_scaffold_102945 --> opera_scaffold_23837 Again, I need a way that, given a graph, I can get back all possible paths. At that point I need to determine the cumulative score for each path, and then choose the one with the highest score. Graph::Traversal seems to offer a lot of options but I'm not sure how to use them all and the documentation isn't very good. Can anyone offer some help on this problem PLEASE. THANKS!.

        o.k that last one was a poor example as I could have computed the components first. The solution is required for other logical possibilities, such as:

        v1 -> v2

        v2 -> v3

        v2 -> v5

        v3 -> v4

        The paths would then be:

        v1 -> v2 ->v3 -> v4

        v1 -> v2 -> v3

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 romping around the Monastery: (7)
As of 2016-10-26 11:03 GMT
Find Nodes?
    Voting Booth?
    How many different varieties (color, size, etc) of socks do you have in your sock drawer?

    Results (340 votes). Check out past polls.