Re: finding head and tail in data structure

[budi pearl]

On Thu, Jan 10, 2013 at 5:19 PM, David Precious <dav...@preshweb.co.uk>wrote:

> On Thu, 10 Jan 2013 17:01:43 +0700
> budi perl <budipe...@gmail.com> wrote:
> You can't have the same hash key twice; you've duplicated 427 there.
>
> Also, you don't need to quote the left side of a fat comma, so you can
> just as easily say e.g. ABEP => 441.
>
>
> > Expected results:
> >
> > ROUTE-252: 427 - ABEP - 441 - 427 - 444 - MGWQ - CDEF
> > ROUTE-432: Error: can not follow the route!
> [...]
> > Can someone shed some light how to find head then follow the path
> > as above? Many thanks.
>
> What have you tried so far?  What have you got stuck on?
>
> How do you know where the start of the route is?  (Rememeber, hash keys
> will come back in essentially random order; so, where do you start?)
>
> If you need to start following from the first key you defined, you'll
> need to either have an arrayref of hashrefs to iterate over, or store
> the starting point as well as the routes.
>
>
Here it is:

#!/usr/bin/perl
#
use strict;
use Data::Dumper;

my %MYROUTES = (
    "ROUTE-252" => {
    #  src => dest
       CX77 => "ABEP",
       ABEP => 441,
       441 => 427,
       427 => 444,
       444 => "MGWQ",
       MGWQ => "CDEF"
    },

    "ROUTE-432" => {
       AAA => "BBB",
       BBB => "CCC",
       CCC => "DDD",
       DDD => "EEE",
       EEE => "FFF",
       XXX => "YYY",
       YYY => "ZZZ",
    }
);

#print Dumper %MYROUTES;

foreach my $id (keys %MYROUTES) {
    print "$id \n";

    # finding the starting point
    my %found = ();
    my $node = \%{$MYROUTES{$id}};
    foreach my $src (keys %{$node}) {
        print "\t$src : ";
        $found{$src} = 0;
        foreach my $key (keys %{$node}) {
            print " $node->{$key} ";
            $found{$src}++ if $src eq $node->{$key};
        }
        print "\n";
    }

    # trace the path
    my $sum = 0;
    foreach(keys %found) {
        print "FOUND: $_ -> $found{$_} ";
        $sum += $found{$_};
    }
    print "\n";

    my $size = scalar keys %found;

    print "size: $size , sum: $sum\n";
    if ($sum == ($size - 1)) {
        print "$id: has complete path\n";
    } else {
        my $total_route =  $size - $sum;
        print "$id: has missing path, got $total_route different routes\n";
    }
}

# should do recursively to print the route?
sub get_next {
    my ($s, $n) = @_;
    if ($n->{$s}) {
        return 1;
    } else {
        return 0;
    }
}

[budi@diavel bin]$ ./printroute.pl
ROUTE-252
        427 :  444  441  ABEP  CDEF  MGWQ  427
        ABEP :  444  441  ABEP  CDEF  MGWQ  427
        CX77 :  444  441  ABEP  CDEF  MGWQ  427
        MGWQ :  444  441  ABEP  CDEF  MGWQ  427
        444 :  444  441  ABEP  CDEF  MGWQ  427
        441 :  444  441  ABEP  CDEF  MGWQ  427
FOUND: CX77 -> 0 FOUND: ABEP -> 1 FOUND: 427 -> 1 FOUND: 444 -> 1 FOUND:
MGWQ -> 1 FOUND: 441 -> 1
size: 6 , sum: 5
ROUTE-252: has complete path
ROUTE-432
        XXX :  YYY  DDD  CCC  FFF  EEE  ZZZ  BBB
        CCC :  YYY  DDD  CCC  FFF  EEE  ZZZ  BBB
        BBB :  YYY  DDD  CCC  FFF  EEE  ZZZ  BBB
        EEE :  YYY  DDD  CCC  FFF  EEE  ZZZ  BBB
        DDD :  YYY  DDD  CCC  FFF  EEE  ZZZ  BBB
        YYY :  YYY  DDD  CCC  FFF  EEE  ZZZ  BBB
        AAA :  YYY  DDD  CCC  FFF  EEE  ZZZ  BBB
FOUND: XXX -> 0 FOUND: BBB -> 1 FOUND: CCC -> 1 FOUND: DDD -> 1 FOUND: EEE
-> 1 FOUND: AAA -> 0 FOUND: YYY -> 1
size: 7 , sum: 5
ROUTE-432: has missing path, got 2 different routes

Looks ok to me, but ugly and need a way to print the full path.
Thanks!


--budi