Senthil Senthil - 7 months ago 10
Perl Question

Recursive function in perl

I have a file like

abc->bcd, efg, hij
bcd->ijk, lmn, ipl
efg->kfg, iop, nkl
lmn->opq, stv, imn


the nested output should be created from this like

abc
bcd
ijk
lmn
opq
stv
imn
ipl
efg
kfg
iop
nkl
hij


I am not very sure how to handle this in perl with recursive function to find any level of nesting. Anyone's help much appreciated.

I have tried with following code, but it gives only one level

my $k = 0;
while ($k <=$#array1)
{
if ($array1[$k]=~m/(.[^->]*)->(.[^\n]*)/)
{
$val = $1;
$val1 = $2;
push @check, $val;
print $val;
my @array2=split /,/,$val1;
foreach my $newid (@array2)
{
push @check1, $newid;
print $newid, "\n";
}
}
$k++;


}

Answer

It's another directed graph! They seem popular recently

You need the Graph module, which will allow you to build a tree of edges and vertices (nodes and connections) and then traverse it to obtain your printout

This program does exactly that with your sample data. Once the graph is built, I test whether it's cyclic to avoid an endless loop and then call my recursive subroutine print_vertex for all source vertices

A source vertex is one that has successors but no predecessors (children but no parent). So it's a root of the tree. I've used a for loop in case the data has more than one root, but your data has only one such vertex: abc

use strict;
use warnings qw/ all FATAL /;
use feature 'say';

use Graph;

my $g = Graph->new(directed => 1);

while ( <DATA> ) {
    my ($from, @to) = /[^\s>,-]+/g;
    $g->add_edge($from, $_) for @to;
}

if ( my @cycle = $g->find_a_cycle ) {
    die sprintf "Graph contains a cycle: %s\n", join(' >> ', @cycle, $cycle[0]);
}

print_vertex($_) for $g->source_vertices;


sub print_vertex {
    my ($v, $indent) = (@_, 0);
    printf "%s%s\n", '  ' x $indent, $v;
    print_vertex($_, $indent+1) for $g->successors($v);
}


__DATA__
abc->bcd, efg, hij
bcd->ijk, lmn, ipl
efg->kfg, iop, nkl
lmn->opq, stv, imn

output

abc
  efg
    iop
    kfg
    nkl
  bcd
    lmn
      stv
      opq
      imn
    ijk
    ipl
  hij
Comments