Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Finding Eulerian Path

by neversaint (Deacon)
on Oct 27, 2010 at 09:15 UTC ( #867666=perlquestion: print w/ replies, xml ) Need Help??
neversaint has asked for the wisdom of the Perl Monks concerning the following question:

Dear Masters,
I have a code that try to find the Eulerian path like this. But somehow it doesn't work. What's wrong with the code?
use strict; use warnings; use Data::Dumper; use Carp; my %graphs = ( 1 => [2,3], 2 => [1,3,4,5], 3 =>[1,2,4,5], 4 => [2, +3,5], 5 => [2,3,4]); my @path = eulerPath(%graphs); sub eulerPath { my %graph = @_; # count the number of vertices with odd degree my @odd = (); foreach my $vert ( sort keys %graph ) { my @edg = @{ $graph{$vert} }; my $size = scalar(@edg); if ( $size % 2 != 0 ) { push @odd, $vert; } } push @odd, ( keys %graph )[0]; if ( scalar(@odd) > 3 ) { return "None"; } my @stack = ( $odd[0] ); my @path = (); while (@stack) { my $v = $stack[-1]; if ( $graph{$v} ) { my $u = ( @{ $graph{$v} } )[0]; push @stack, $u; # Find index of vertice v in graph{$u} my @graphu = @{ $graph{$u} }; # This is line 54. my ($index) = grep $graphu[$_] eq $v, 0 .. $#graphu; delete @{ $graph{$u} }[$index]; delete @{ $graph{$v} }[0]; } else { push @path, pop(@stack); } } print Dumper \@path; return @path; }
The error I get is:
Use of uninitialized value in hash element at euler.pl line 54
I expect it to return the output like this:
$VAR = [5, 4, 3, 5, 2, 3, 1, 2, 4];
Actually I try to mimic the working code in Python:
def eulerPath(graph): # counting the number of vertices with odd degree odd = [ x for x in graph.keys() if len(graph[x])&1 ] print odd odd.append( graph.keys()[0] ) if len(odd)>3: return None stack = [ odd[0] ] path = [] # main algorithm while stack: v = stack[-1] if graph[v]: u = graph[v][0] stack.append(u) # deleting edge u-v #print graph[u][ graph[u].index(v) ] #print graph[u].index(v) del graph[u][ graph[u].index(v) ] del graph[v][0] else: path.append( stack.pop() ) return path stack_ = eulerPath({ 1:[2,3], 2:[1,3,4,5], 3:[1,2,4,5], 4:[2,3,5], + 5:[2,3,4] }) print stack_


---
neversaint and everlastingly indebted.......

Comment on Finding Eulerian Path
Select or Download Code
Re: Finding Eulerian Path
by youlose (Scribe) on Oct 27, 2010 at 09:42 UTC
    Hi,

    you are deleting elements from arrays with delete

    but perldoc tells us:
    delete() may also be used on arrays and array slices, but its behavior is less straightforward. Although exists() will return false for deleted entries, deleting array elements never changes indices of existing values; use shift() or splice() for that. However, if all deleted elements fall at the end of an array, the array's size shrinks to the position of the highest element that still tests true for exists(), or to 0 if none do. Be aware that calling delete on array values is deprecated and likely to be removed in a future version of Perl.

    So, refactor your code and replace delete with proper code with splice

Re: Finding Eulerian Path
by jethro (Monsignor) on Oct 27, 2010 at 09:47 UTC
    my $u = ( @{ $graph{$v} } )[0];

    $u = $graph{v}[0] is valid perl code, by the way ;-).

Re: Finding Eulerian Path
by Fletch (Chancellor) on Oct 27, 2010 at 14:22 UTC

    Graph and/or chapter 8 of Mastering Algorithms with Perl (ISBN 9781565923980) might also be of interest.

    The cake is a lie.
    The cake is a lie.
    The cake is a lie.

      The splice/shift trick worked. Just replace the 2 lines of delete with:
      splice @{ $graph{$u} }, $index, 1; shift @{ $graph{$v} };
      and it worked great!
        And Forgot to add this modification too, in the if() statement:
        if ( $graph{$v} ) {
        to:
        if ( @{$graph{$v}} ) {

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://867666]
Approved by marto
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (14)
As of 2014-07-24 13:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (160 votes), past polls