Adjacency matrices are really nice for this problem since they make "paths of length N" problems easy to reason about. Probably just wandering through the graph and keeping track of paths will give simpler code, but I guess I prefer using heavy machinery when it has nice abstraction properties... I also happen to really how you can use the structure of the matrix multiplication algorithm to do a lot of cute graph theory algorithms.

The idea is that if you have the 0/1 adjacency matrix of a graph, and you take that matrix to the Nth power, then the (i,j) entry of the result tells how many paths of length N there are from vertex i to vertex j (here the length is measured in number of edges traversed) .

The only trick is instead of just counting the paths, to keep track of all the actual paths themselves. For this you have to slightly modify the matrix multiplication algorithm...

We modify the adjacency matrix so instead of being 0/1, the (i,j) entry of the matrix is a list of paths from i to j. Then in the matrix multiplication algorithm, instead of multiplying and adding entries, we instead concatenate pairs of paths together and union all of them (respectively). Here's what the code looks like: 

use strict;

## just any old directed graph...

my $adj = [ [0,1,1,0,1],
            [1,0,0,0,1],
            [0,1,0,0,0],
            [1,1,1,0,0],
            [0,0,1,1,0] ];
my $dim = 4; ## size of the graph
my $N = 3;   ## length of paths (# of edges, not # of vertices).

## convert each entry in the adjacency matrix into a list of paths
    
for my $i (0 .. $dim) {
  for my $j (0 .. $dim) {
    $adj->[$i][$j] = $adj->[$i][$j] ? [$j] : [];
  }   
}

## compute the $N-th power of the adjacency matrix with our modified
## multiplication

my $result = $adj;
for (2 .. $N) {
   print_paths($result);
   print "========\n";
   $result = matrix_mult($result, $adj);
}

print_paths($result);

## the i,j entry of the matrix is a list of all the paths from i to j,
+ but
## without "i," at the beginning, so we must add it

sub print_paths {
    my $M = shift;
    my @paths;
    for my $i (0 .. $dim) {
      for my $j (0 .. $dim) {
        push @paths, map { "$i,$_" } @{ $M->[$i][$j] };
      }
    }
    print map "$_\n", sort @paths;
}

## modified matrix multiplication. instead of multiplication, we
## combine paths from i->k and k->j to get paths from i->j (this is wh
+y
## we include the endpoint in the path, but not the starting point).
## then instead of addition, we union all these paths from i->j

sub matrix_mult {
    my ($A, $B) = @_;
    my $result;
    for my $i (0 .. $dim) {
      for my $j (0 .. $dim) {
        my @result;
        for my $k (0 .. $dim) {
          push @result, combine_paths( $A->[$i][$k], $B->[$k][$j] );
        }
        $result->[$i][$j] = \@result;
      }
    }
    $result;
}

## the sub to combine i->k paths and k->j paths into i->j paths --
## we simply concatenate with a comma in between.

sub combine_paths {
    my ($x, $y) = @_;
    my @result; 
    
    for my $i (@$x) {
      for my $j (@$y) {
        push @result, "$i,$j";
      } 
    }   
    @result;
}

[download]
Output snippet: 
0,1
0,2
...
========
0,1,0
0,1,4
0,2,1
0,4,2
...
========
...
0,4,2,1
0,4,3,0
0,4,3,1
0,4,3,2
1,0,1,0
1,0,1,4
1,0,2,1
...

[download]

blokhead

In reply to Re: find all paths of length n in a graph by blokhead
in thread find all paths of length n in a graph by davidj

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, details, 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, summary, 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.