Hash keys for standard hashes are strings. Your object got stringified when you used it as a key. The object itself was never stored in the hash.

Since you only use a hash to enforce uniqueness (i.e. you're not using the value), it's easy to fix. Replace
$self->{_edges}{$key} = 1;
with
$self->{_edges}{$key} = $key;
and replace
my @tmp = keys %{$_[0]->{'_edges'}};
with
my @tmp = values %{$_[0]->{'_edges'}};

By the way, @tmp is a poor name for variable. Why not use @edges?