#!/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;