#!/usr/bin/perl -w
#################################################
#
# Find a path of links connecting two web sites.
#
# To run this, just type its name (findLinksPath.pl) at the command line.
# (The file "GetLinks.pm" must be in the same directory.)
# The use is asked for two urls and a search depth; hitting Enter
# gives some reasonable default values.
#
# A sample session looks like this:
#
# -----------------------------------------
# [mahoney@cs web-links]$ findLinkPath.pl
# 
#  Find a path of links connecting two web sites. 
# 
#    Enter initial URL [http://www.marlboro.edu/] : 
#    Enter final URL [http://www.marlboro.edu/~norsen/physics.html] : 
#    Enter maximum search depth [4] : 
# 
#    Searching breadth first to depth 4
#    from 'http://www.marlboro.edu/' 
#    to 'http://www.marlboro.edu/~norsen/physics.html'.
# 
#    -- Depth 0 --  Exploring 1 node (0 already examined).
#        Expanding node 'http://www.marlboro.edu/'
#    -- Depth 1 --  Exploring 13 nodes (1 already examined).
#        Expanding node 'http://www.marlboro.edu/about/'
#        Expanding node 'http://www.marlboro.edu/admissions/'
#        Expanding node 'http://www.marlboro.edu/academics/'
#    Done.
# 
#  The path is 
#   0 : http://www.marlboro.edu/
#   1 : http://www.marlboro.edu/academics/
#   2 : http://www.marlboro.edu/~norsen/physics.html
# 
# [mahoney@cs web-links]$ 
# -----------------------------------------
#
# See Russell&Norvig's AI: a Modern Approach,Exercise 3.14 on page 92.
#
#   Jim Mahoney
#   v 0.2  Feb 10, 2003
#
######################################
use strict;
use warnings;

use GetLinks;           # imports @links = getLinks($url) subroutine.
my $VERBOSE           = 1;
my $DEBUG             = 1;

my $defaultInitialURL = "http://www.marlboro.edu/";
my $defaultFinalURL   = "http://www.marlboro.edu/~norsen/physics.html";
my $defaultMaxDepth   = 4;

print "\n Find a path of links connecting two web sites. \n\n";

# Talk to the nice user.
print "   Enter initial URL [$defaultInitialURL] : ";
my $initialURL = getUserURL()     || $defaultInitialURL;
print "   Enter final URL [$defaultFinalURL] : ";
my $finalURL   = getUserURL()     || $defaultFinalURL;
print "   Enter maximum search depth [4] : ";
chomp(my $maxDepth = <>);
$maxDepth = $maxDepth || $defaultMaxDepth;

# Check the inputs for reasonability.
if ($initialURL eq $finalURL) {
  die " Error - same URL given for initial and final URLs.\n";
}
$maxDepth = $defaultMaxDepth if $maxDepth <=0;

print "\n";
print "   Searching breadth first to depth $maxDepth\n";
print "   from '$initialURL' \n";
print "   to '$finalURL'.\n\n";

# Since acquiring the links is expensive in time, 
# I'm going to try to keep all the nodes in memory, and thus
# do a breadth first search.  I haven't yet tested what
# happens when we run out of space...
#
# A better approach would be a bi-directional search,
# perhaps using google to find sites with links that
# point towards our goal.  I can see how to do that
# by parsing Google's output - and even have notes at the
# bottom of this page on formats - but I also see that
# Google has a www.google.com/robots.txt file indicating
# that they would not happy to have their site used in 
# this manner.  Hmmm.

my $pastNodes    = [];    # url's above the current depth - already searched.
my $presentNodes = [];    # url's current depth, actively being searched.
my $futureNodes  = [      # url's to search at the next depth down.
                    Node->new( url=>$initialURL, depth=>0 ),
                   ];   
my $currentDepth = 0;

while ($currentDepth <= $maxDepth) {
  $currentDepth++;

  # At this new depth, put the various nodes into their appropriate categories.
  push @$pastNodes, @$presentNodes;
  $presentNodes = $futureNodes;
  $futureNodes = [];
  if ($VERBOSE) {
    my $nNow  = scalar(@$presentNodes) || 0;
    my $nPast = scalar(@$pastNodes) || 0;
    print "   -- Depth ", $currentDepth-1," -- ";
    print " Exploring $nNow node" , $nNow eq 1 ? '' : 's' , 
          " ($nPast already examined).\n";
  }
  
  foreach my $node (@$presentNodes) {
    print "       Expanding node '", $node->url, "'\n" if $VERBOSE;
    my @links = getLinks( $node->url );
    foreach my $link (@links) {
      print "       found '$link' " if $DEBUG;
      goalCheck($link, $node);
      unless (seenAlready($link)){
        print " - new \n" if $DEBUG;
        push @$futureNodes, Node->new( url    => $link, 
                                       depth  => $currentDepth, 
                                       parent => $node );
      }
    }
  }
}

# ====== subroutines ==========================

# ------------------------------------------------------
{ # Node object data structure and methods.
  package Node;

  sub new {
    my $class = shift;
    my $self = { @_ };
    bless $self, $class;
    return $self;
  }

  sub url {
    my $self = shift;
    return $self->{url};
  }

  sub parent {
    my $self = shift;
    return $self->{parent};
  }

  sub depth {
    my $self = shift;
    return $self->{depth};
  }

}

# ------------------------------------------------------
# Return true if the given url is in the given list of nodes, i.e.
# in any of $pastNodes,$currentNodes, or $futureNodes.
sub seenAlready {
  my ($url) = @_;
  return 1 if urlInNodeList($url, $pastNodes);
  return 1 if urlInNodeList($url, $presentNodes);
  return 1 if urlInNodeList($url, $futureNodes);
  return 0;
}
sub urlInNodeList {
  my ($url, $nodes) = @_;
  for my $node (@$nodes) {
    if ($node->url eq $url){
      print " - old\n" if $DEBUG;
      return 1;
    }
  }
  return 0;
}

# ------------------------------------------------------
# If we've found an answer, print it out and exit.
sub goalCheck {
  my ($link, $parentNode) = @_;
  my $goalDepth = $parentNode->depth + 1;
  return 0 unless $link eq $finalURL;
  # -- found answer! --
  print "   Done.\n\n The path is \n";
  my @path = ();
  while ($parentNode) {
    unshift @path, $parentNode;
    $parentNode = $parentNode->parent;
  }
  
  foreach my $node (@path) {
    print "  " . $node->depth, " : " , $node->url . "\n";
  }
  print "  " , $goalDepth ,  " : " , $finalURL . "\n";
  print "\n";
  exit;
}

# ------------------------------------------------------
# Return a URL typed in from the keyboard.
# If the user just hits enter, return the empty string.
# Otherwise, prepend "http://" if needed.
sub getUserURL {
  chomp(my $userInput = <>);
  return '' unless $userInput;
  $userInput = "http://" . $userInput unless $userInput =~ m{^http://};  
  return $userInput;
}


# ------------------------------------------------------
# Google Notes
# 
#  To find pages that link to a given page:
#     search?as_lq=url
#     url is in form "<font color=#008000>url -"
#  or
#     search?q=link:         query for pages with given link
#     &start=number    return results starting at number+1
#     &safe=off        porn filtering
#     &ie=UTF-8        encoding
#     &num=100         how many per page, max 100
#     
# how many found  "- <b>100</b> of about <b>828</b>"
