Advertisement
Guest User

Untitled

a guest
Mar 13th, 2011
179
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement