Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
neversaint,
Per our conversation, here is an example of finding all paths using a depth-first search. It is unoptimized and with all the copying of arrays and hashes - I wouldn't expect it to be a top performer as is. I am thinking about the self-pruning approach I alluded to earlier as I have to convince myself it will still work with a directed graph (which I now realize this is). If it works, I will post it as well.
#!/usr/bin/perl use constant LAST => -1; use constant PATH => 0; use constant SEEN => 1; use strict; use warnings; my %graph = ( F => [qw/B C E/], A => [qw/B C/], D => [qw/B/], C => [qw/A E F/], E => [qw/C F/], B => [qw/A E F/] ); my $routes = find_paths('B', 'E', \%graph); print "@$_\n" for @$routes; sub find_paths { my ($beg, $end, $graph) = @_; my @solution; my @work; for (@{$graph->{$beg}}) { push @solution, [$beg, $end] if $_ eq $end; push @work, [[$beg, $_], {$beg => undef, $_ => undef}]; } while (@work) { my $item = pop @work; my ($path, $seen) = @{$item}[PATH, SEEN]; for my $node (@{$graph->{$path->[LAST]}}) { next if exists $seen->{$node}; my @new_path = (@$path, $node); if ($node eq $end) { push @solution, \@new_path; next; } my %new_seen = (%$seen, $node => undef); push @work, [\@new_path, \%new_seen]; } } return \@solution; }

Update: Assuming you can create a function to convert your node name to an integer (preferrably 0 based) then the following should be a lot faster assuming copying strings is faster than arrays and hashes.

#!/usr/bin/perl use strict; use warnings; my %graph = ( F => [qw/B C E/], A => [qw/B C/], D => [qw/B/], C => [qw/A E F/], E => [qw/C F/], B => [qw/A E F/] ); my $routes = find_paths('B', 'E', \%graph); print "$_\n" for @$routes; sub find_paths { my ($beg, $end, $graph) = @_; my (@work, @solution); for (@{$graph->{$beg}}) { if ($_ eq $end) { push @solution, "$beg->$end"; next; } my $seen = ''; vec($seen, node_to_int($_), 1) = 1; vec($seen, node_to_int($beg), 1) = 1; push @work, ["$beg->$_", $_, $seen]; } while (@work) { my $item = pop @work; my ($path, $curr, $seen) = @$item; for my $node (@{$graph->{$curr}}) { my $bit = node_to_int($node); next if vec($seen, $bit, 1); if ($node eq $end) { push @solution, "$path->$end"; next; } my $new_seen = $seen; vec($new_seen, $bit, 1) = 1; push @work, ["$path->$node", $node, $new_seen]; } } return \@solution; } sub node_to_int { my ($node) = @_; return ord($node) - 65; }

Update 2: Here is a version using short-circuiting. I am not happy with it since you need to enumerate over an array of bitstrings to determine if the path can be pruned rather than doing a lookup. I may post my own SoPW to see if anyone can come up with a better way. I have tried this on a very limited test set so it could very well be flawed. I would be interested to know how it fairs performance wise on real data as well as if it can be found to be flawed.

#!/usr/bin/perl use strict; use warnings; my %graph = ( R => [qw/L J Z/], L => [qw/R J X/], J => [qw/R L X Z/], Z => [qw/R J X/], X => [qw/L J Z F D/], F => [qw/X D/], D => [qw/Q F X/], Q => [qw/B U D/], B => [qw/Q P M/], P => [qw/B U/], U => [qw/Q P S/], M => [qw/B S/], S => [qw/U M/], ); my $routes = find_paths('D', 'M', \%graph); print "$_\n" for @$routes; sub find_paths { my ($beg, $end, $graph) = @_; my (@work, @solution, %done); for (@{$graph->{$beg}}) { if ($_ eq $end) { push @solution, "$beg->$end"; next; } my $seen = ''; vec($seen, node_to_int($_), 1) = 1; vec($seen, node_to_int($beg), 1) = 1; push @work, ["$beg->$_", $_, $seen]; } while (@work) { my $item = pop @work; my ($path, $curr, $seen) = @$item; my $ok; for my $node (@{$graph->{$curr}}) { my $bit = node_to_int($node); next if vec($seen, $bit, 1) || ($done{$node} && path_compl +eted($seen, $done{$node})); $ok = 1; if ($node eq $end) { push @solution, "$path->$end"; next; } my $new_seen = $seen; vec($new_seen, $bit, 1) = 1; push @work, ["$path->$node", $node, $new_seen]; } update_completed_paths($path, $seen, \%done) if ! $ok; } return \@solution; } sub node_to_int { my ($node) = @_; return ord($node) - 65; } sub update_completed_paths { my ($path, $seen, $done) = @_; my @order = split /->/, $path; for my $idx (reverse 0 .. $#order - 1) { local $_ = $order[$idx]; vec($seen, node_to_int($_), 1) = 0; push @{$done->{$_}}, $seen; } } sub path_completed { my ($path, $completed) = @_; for (@$completed) { my $and = $_ & $path; return 1 if $and eq $_; } return; }

Cheers - L~R


In reply to Re: Finding All Paths From a Graph From a Given Source and End Node by Limbic~Region
in thread Finding All Paths From a Graph From a Given Source and End Node by neversaint

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others pondering the Monastery: (6)
    As of 2020-04-03 07:04 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      The most amusing oxymoron is:
















      Results (26 votes). Check out past polls.

      Notices?