Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Mar 13th, 2011  |  syntax: None  |  size: 1.55 KB  |  views: 78  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #!/usr/bin/perl
  2.  
  3. #  Code assumes input graph is a binary tree as stated in
  4. #  the problem, NOT a binary *search* tree. Requres log n
  5. #  time and space, where n is the number of nodes in the tree.
  6. #
  7. #  Example to compute LCA(3,6) in the tree in the diagram:
  8. #  perl lca '8: 3 10; 3: 1 6; 6: 4 7; 10: 14; 14: 13' 3 6
  9.  
  10. use strict;
  11. use warnings;
  12.  
  13. my($rawtree, $node1, $node2) = @ARGV;
  14.  
  15. print "LCA($node1, $node2) = ",
  16.   LeastCommonAncestor(InvertGraph(ParseGraph($rawtree)), $node1, $node2);
  17.  
  18. sub LeastCommonAncestor {
  19.   my ($invertedtree, $node1, $node2) = @_;
  20.  
  21.   my %parentsofnode1 = map { $_ => 1 } Descendants($invertedtree, $node1);
  22.  
  23.   foreach my $parentofnode2 (Descendants($invertedtree, $node2)) {
  24.     if ($parentsofnode1{$parentofnode2}) {
  25.       return $parentofnode2;
  26.     }
  27.   }
  28.   die "can't happen in a tree\n";
  29. }
  30.  
  31.  
  32. sub ParseGraph {
  33.   my ($rawgraph) = @_;
  34.   my %graph;
  35.   foreach (split /\s*;\s*/, $rawgraph) {
  36.     my ($node, $successors) = /^\s*([^:\s]*):\s*(.*)/;
  37.     $node =~ s/^\s+//;
  38.     $graph{$node} = { map { $_ => 1 } split /\s+/, $successors };
  39.   }
  40.   return \%graph;
  41. }
  42.  
  43. sub InvertGraph {
  44.   my ($graph) = @_;
  45.   my %invertedgraph;
  46.   foreach my $src (keys %$graph) {
  47.     foreach my $dst (keys %{ $graph->{$src} }) {
  48.       $invertedgraph{$dst}{$src} = 1;
  49.     }
  50.   }
  51.   return \%invertedgraph;
  52. }
  53.  
  54. sub Descendants {
  55.   my ($dag, $node) = @_;
  56.  
  57.   return (
  58.     $node,
  59.     map { Descendants($dag, $_) } Successors($dag, $node),
  60.   );
  61. }
  62.  
  63.  
  64. sub Successors {
  65.   my ($graph, $node) = @_;
  66.  
  67.   return keys %{ $graph->{$node} };
  68. }