#!/usr/bin/perl
use strict;
use Graph::Undirected;
use Graph::Traversal::DFS;
my $g = Graph::Undirected->new;
$g->add_edge('a', 'b');
$g->add_edge('b', 'c');
$g->add_edge('c', 'd');
$g->add_edge('c', 'z');
$g->add_edge('d', 'e');
$g->add_edge('c', 'q');
$g->add_edge('q', 'r');
$g->add_edge('r', 's');
$g->add_edge('r', 'x');
# what I'd like this to return is
# a, b, c, d, e
# c, q, r, s
# c, z
# see, since c is a branch point, I want c to be part of the set returned
# by the program.
# this current code starts at 'a' and cruises along the depth first tree
# but it doesnt exhaustively find all the branches and produce the above
# output.
my $old_node;
my $count = 0;
my @pre;
#this returns all paths
#the call to print in post is only made at terminal nodes for each possible path from a branch
#at this point @pre is a complete path from start to the terminal node
#you can replace "print join()" with any desired action you want to perform on @pre, including making a copy
my $startnode = 'a';
my @branches;
my $latestbranch = undef;
my $t = Graph::Traversal::DFS->new($g,
pre => sub {
push @pre,$_[0];
#save all branch point (ie nodes with degree > 2)
if($g->degree($_[0])>2){
#keep track of previous branch point or zero
$latestbranch = @branches ? @branches[$#branches] : 0;
push @branches,$#pre;
}
},
post => sub {
#degree==1 for terminal nodes only and possibly root node
if($g->degree($_[0]) == 1 && $_[0] ne $startnode){
my @path;
#only print full path past the latest branch once
#after first time. set to undef
if(defined $latestbranch){
@path = @pre[$latestbranch..$#pre];
$latestbranch=undef;
}
#each subsequence time just print the path from the last branch point
else{
my $index = @branches[$#branches]
; @path = @pre[$index..$#pre];
}
print join(',',@path),"\n";
}
#remove the branch point on post traversal
if(@branches[$#branches] == $#pre){
pop @branches;
}
pop @pre;
},
next_alphabetic=>1,
start => $startnode);
$t->dfs;
exit;