For the problem at hand, you could modify a copy of the 2-D array if you replace the initial line of your sub with these four lines:

sub add_edge {
    my @graph;
    for ( @_ ) {
        push @graph, [ @$_ ];
    }
    ...
[download]

(But I would be inclined to add some checks, and Carp if the input list is empty or includes anything that isn't an array ref.)