#!/usr/bin/perl -w

# Who:    Javed Aslam
# What:   markovIterate.pl
# When:   11/04/09

# Usage

if (@ARGV == 0) {
  print STDERR "\nUsage: markovIterate.pl interations transition_matrix\n\n";
  exit;
  }

# Process arguments

$count = shift;

$link_file = shift;

# Get the data from the link file

print STDERR "Processing transition matrix...\n\n";

open(FILE, $link_file) or
  die "Failed to open $link_file: $!\n\n";

$outID = 0;
while (<FILE>) {
  $outID++;
  @fields = split(" ");
  $graphHash{$outID} = {};
  $inID = 0;
  foreach $prob (@fields) {
    $inID++;
    $graphHash{$outID}->{$inID} = $prob;
    }
  }

$nodes = $outID;

close(FILE) or
  die "Couldn't close $link_file: $!\n\n";

# Now solve for stationary distribution by iterating

foreach $outID (keys %graphHash) {
  $oldStatDist{$outID} = 1/$nodes;
  print "$oldStatDist{$outID} ";
  }
print "\n";

for ($i=1; $i<=$count; $i++) {

  foreach $outID (keys %graphHash) {
    $newStatDist{$outID} = 0;
    }

  foreach $outID (keys %graphHash) {
    $href = $graphHash{$outID};              # get hash reference for out-links
    %outlinkHash = %$href;                   # get out-link hash
    foreach $outlink (keys %outlinkHash) {
      $newStatDist{$outlink} += $oldStatDist{$outID}*$outlinkHash{$outlink};
      }
    }

  # Print StatDists

  foreach $outID (sort keys %newStatDist) {
    print "$newStatDist{$outID} ";
    }
  print "\n";

  # Update old StatDist values

  foreach $outID (keys %newStatDist) {
    $oldStatDist{$outID} = $newStatDist{$outID};
    }

  }