Perl-Sensitive Sunglasses PerlMonks

### Finding Eulerian Path

by neversaint (Deacon)
 on Oct 27, 2010 at 09:15 UTC 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.......

Replies are listed 'Best First'.
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}} ) {

Create A New User
Node Status?
node history
Node Type: perlquestion [id://867666]
Approved by marto
help
Chatterbox?
 [Eily]: This sounds like the perfect medium to send "don't let anything distract you" [LanX]: hippo you asked about translating Asterix ? [Eily]: Maybe the puns in his dialogues were somehow kept through translation, but I can tell he lost his accent [LanX]: qui? [Eily]: Astérix 1nickt gives up on finding a Perl YAML parser that supports hash merging. In 2017. [LanX]: Oh yes true, he lost his accent! xD

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (14)
As of 2017-05-24 14:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favorite model of computation is ...

Results (184 votes). Check out past polls.