home *** CD-ROM | disk | FTP | other *** search
/ CD Actual Thematic 7: Programming / CDAT7.iso / Share / Editores / Perl5 / perl / lib / site / Graph / Kruskal.pm
Encoding:
Perl POD Document  |  1997-08-10  |  11.5 KB  |  449 lines
  1.  
  2. #  Copyright (c) 1995, 1996, 1997 by Steffen Beyer. All rights reserved.
  3. #  This package is free software; you can redistribute it and/or modify
  4. #  it under the same terms as Perl itself.
  5.  
  6. package Graph::Kruskal;
  7.  
  8. use strict;
  9. use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS $VERSION
  10.             $number_of_edges $number_of_vortices @V @E @T);
  11.  
  12. require Exporter;
  13.  
  14. @ISA = qw(Exporter);
  15.  
  16. @EXPORT = qw();
  17.  
  18. @EXPORT_OK = qw(define_vortices define_edges
  19.                 heapify makeheap heapsort
  20.                 find union kruskal example);
  21.  
  22. %EXPORT_TAGS = (all => [@EXPORT_OK]);
  23.  
  24. $VERSION = '2.0';
  25.  
  26. use Carp;
  27.  
  28. $number_of_vortices = 0;
  29. $number_of_edges = 0;
  30.  
  31. sub example
  32. {
  33.     my($costs) = 0;
  34.     my($k);
  35.  
  36.     print "\n";
  37.     print "+++ Kruskal's Algorithm for Minimal Spanning Trees in Graphs +++";
  38.     print "\n";
  39.  
  40.     &define_vortices(2,3,5,7,11,13,17,19,23,29,31);
  41.  
  42.     print "\nVortices:\n\n";
  43.  
  44.     for ( $k = 1; $k <= $#V; ++$k )
  45.     {
  46.         if (defined $V[$k]) { print "$k\n"; }
  47.     }
  48.  
  49.     &define_edges( 2,13,3, 3,13,2, 5,13,1, 3,5,2, 3,29,21, 23,29,3,
  50.      23,31,2, 5,31,15, 5,7,10, 2,11,2, 7,11,2, 7,19,5, 11,19,2,
  51.      7,31,4, 3,17,3, 17,23,3, 7,17,3 );
  52.  
  53.     print "\nEdges:\n\n";
  54.  
  55.     for ( $k = 1; $k <= $#E; ++$k )
  56.     {
  57.         print ${$E[$k]}{'from'}, " <-> ", ${$E[$k]}{'to'}, " = ",
  58.             ${$E[$k]}{'cost'}, "\n";
  59.     }
  60.  
  61.     &kruskal();
  62.  
  63.     print "\nEdges in minimal spanning tree:\n\n";
  64.  
  65.     for ( $k = 1; $k <= $#T; ++$k )
  66.     {
  67.         print ${$T[$k]}{'from'}, " <-> ", ${$T[$k]}{'to'}, " = ",
  68.             ${$T[$k]}{'cost'}, "\n";
  69.         $costs += ${$T[$k]}{'cost'};
  70.     }
  71.  
  72.     print "\nTotal costs: $costs\n\n";
  73. }
  74.  
  75. sub define_vortices
  76. {
  77.     undef @V;
  78.     $number_of_vortices = 0;
  79.     foreach (@_)
  80.     {
  81.         ($_ > 0) || croak "Graph::Kruskal::define_vortices(): vortex number not positive\n";
  82.         $V[$_] = -1;
  83.         ++$number_of_vortices;
  84.     }
  85. }
  86.  
  87. sub define_edges
  88. {
  89.     my($from,$to,$cost);
  90.  
  91.     undef @E;
  92.     $number_of_edges = 0;
  93.     while (@_)
  94.     {
  95.         $from = shift || croak "Graph::Kruskal::define_edges(): missing 'from' vortex number\n";
  96.         $to   = shift || croak "Graph::Kruskal::define_edges(): missing 'to' vortex number\n";
  97.         $cost = shift || croak "Graph::Kruskal::define_edges(): missing edge 'cost' value\n";
  98.         defined $V[$from] || croak "Graph::Kruskal::define_edges(): vortex '$from' not previously defined\n";
  99.         defined $V[$to]   || croak "Graph::Kruskal::define_edges(): vortex '$to' not previously defined\n";
  100.         ($from != $to)    || croak "Graph::Kruskal::define_edges(): vortices 'from' and 'to' are the same\n";
  101.         $E[++$number_of_edges] =
  102.             { 'from' => $from, 'to' => $to, 'cost' => $cost };
  103.     }
  104. }
  105.  
  106. sub heapify             # complexity: O(ld n)
  107. {
  108.     my($i,$n) = @_;
  109.     my($i2,$i21,$j,$swap);
  110.  
  111.     while ($i < $n)
  112.     {
  113.         $j   = $i;
  114.         $i2  = $i * 2;
  115.         $i21 = $i2 + 1;
  116.         if ($i2 <= $n)
  117.         {
  118.             if (${$E[$i]}{'cost'} > ${$E[$i2]}{'cost'})
  119.             {
  120.                 $j = $i2;
  121.                 if ($i21 <= $n)
  122.                 {
  123.                     if (${$E[$i2]}{'cost'} > ${$E[$i21]}{'cost'}) { $j = $i21; }
  124.                 }
  125.             }
  126.             else
  127.             {
  128.                 if ($i21 <= $n)
  129.                 {
  130.                     if (${$E[$i]}{'cost'} > ${$E[$i21]}{'cost'}) { $j = $i21; }
  131.                 }
  132.             }
  133.         }
  134.         if ($i != $j)
  135.         {
  136.             $swap  = $E[$i];
  137.             $E[$i] = $E[$j];
  138.             $E[$j] = $swap;
  139.             $i = $j;
  140.         }
  141.         else { $i = $n; }
  142.     }
  143. }
  144.  
  145. sub makeheap            # complexity: O(n ld n)
  146. {
  147.     my($n) = @_;
  148.     my($k);
  149.  
  150.     for ( $k = $n - 1; $k > 0; --$k ) { &heapify($k, $n); }
  151. }
  152.  
  153. # The following subroutine isn't used by this algorithm, it is only included
  154. # here for the sake of completeness:
  155.  
  156. sub heapsort            # complexity: O(n ld n)
  157. {
  158.     my($n) = @_;
  159.     my($k,$swap);
  160.  
  161.     for ( $k = $n - 1; $k > 0; --$k ) { &heapify($k, $n); }
  162.  
  163.     for ( $k = $n; $k > 1; --$k )
  164.     {
  165.         $swap  = $E[1];
  166.         $E[1]  = $E[$k];
  167.         $E[$k] = $swap;
  168.         &heapify(1, $k - 1);
  169.     }
  170. }
  171.  
  172. sub find
  173. {
  174.     my($i) = @_;
  175.     my($j,$k,$t);
  176.  
  177.     $j = $i;
  178.     while ($V[$j] > 0) { $j = $V[$j]; } # find root element (= set identifier)
  179.     $k = $i;
  180.     while ($k != $j)                    # height compression of the tree
  181.     {
  182.         $t = $V[$k];
  183.         $V[$k] = $j;
  184.         $k = $t;
  185.     }
  186.     return($j);
  187. }
  188.  
  189. sub union
  190. {
  191.     my($i,$j) = @_;
  192.     my($x);
  193.  
  194.     $x = $V[$i] + $V[$j];    # calculate number of elements in resulting set
  195.     if ($V[$i] > $V[$j])     # which of the two sets contains more elements?
  196.     {
  197.         $V[$i] = $j;         # merge them
  198.         $V[$j] = $x;         # update number of elements
  199.     }
  200.     else
  201.     {
  202.         $V[$j] = $i;         # merge them
  203.         $V[$i] = $x;         # update number of elements
  204.     }
  205. }
  206.  
  207. sub kruskal             # complexity: O(n ld n)   ( where n := |{ Edges }| )
  208. {
  209.     my($n) = $number_of_edges;
  210.     my($v) = $number_of_vortices;
  211.     my($i,$j,$swap);
  212.     my($t) = 0;
  213.  
  214.     undef @T;
  215.     &makeheap($number_of_edges);        # complexity: O(n ld n)
  216.     while (($v > 1) && ($n > 0))
  217.     {
  218.         $swap  = $E[1];
  219.         $E[1]  = $E[$n];
  220.         $E[$n] = $swap;
  221.         &heapify(1, $n - 1);            # complexity: n O(ld n) = O(n ld n)
  222.         $i = find(${$E[$n]}{'from'});   # complexity: n ( 2 find + 1 union ) =
  223.         $j = find(${$E[$n]}{'to'});     #             O( G(n) n ) <= O(n ld n)
  224.         if ($i != $j)
  225.         {
  226.             union($i,$j);
  227.             $T[++$t] = $E[$n];
  228.             --$v;
  229.         }
  230.         --$n;
  231.     }
  232.     return(@T);
  233. }
  234.  
  235. 1;
  236.  
  237. __END__
  238.  
  239. =head1 NAME
  240.  
  241. Graph::Kruskal - Kruskal's Algorithm for Minimal Spanning Trees in Graphs
  242.  
  243. Computes the Minimal Spanning Tree of a given graph according to
  244. some cost function defined on the edges of the graph.
  245.  
  246. =head1 SYNOPSIS
  247.  
  248. =over 4
  249.  
  250. =item *
  251.  
  252. C<use Graph::Kruskal qw(define_vortices define_edges>
  253. C<heapify makeheap heapsort find union kruskal example);>
  254.  
  255. =item *
  256.  
  257. C<use Graph::Kruskal qw(:all);>
  258.  
  259. =item *
  260.  
  261. C<&define_vortices(2,3,5,7,11,13,17,19,23,29,31);>
  262.  
  263. Define a list of vortices (integers > 0)
  264.  
  265. =item *
  266.  
  267. C<&define_edges( 2,13,3, 3,13,2, 5,13,1, 3,5,2, 3,29,21 );>
  268.  
  269. Define (non-directed) edges on the vortices previously defined (always
  270. in triplets: "from" vortice, "to" vortice and cost of that edge)
  271.  
  272. =item *
  273.  
  274. C<&heapify($i,$n);>
  275.  
  276. Main subroutine for sorting the edges according to their costs
  277.  
  278. =item *
  279.  
  280. C<&makeheap($n);>
  281.  
  282. Routine to initialize sorting of the edges
  283.  
  284. =item *
  285.  
  286. C<&heapsort($n);>
  287.  
  288. The famous heapsort algorithm (not needed for Kruskal's algorithm as a whole
  289. but included here for the sake of completeness) for sorting the edges
  290. according to their costs
  291.  
  292. =item *
  293.  
  294. C<&find($i);>
  295.  
  296. =item *
  297.  
  298. C<&union($i,$j);>
  299.  
  300. Disjoint (!) sets are stored as trees in an array in this algorithm. Each
  301. element of some set (a cell in the array) contains a pointer to (the number
  302. of) another element, up to the root element that does not point anywhere,
  303. but contains the (negative) number of elements the set contains. The number
  304. of the root element is also used as an identifier for the set.
  305.  
  306. Example:
  307.  
  308.             i  : |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
  309.     -------------+-----+-----+-----+-----+-----+-----+-----+-----+
  310.      parent[i] : | -4  | -3  |  1  |  2  |  1  | -1  |  3  |  4  |
  311.  
  312. This array contains the three sets S1, S2 and S6:
  313.  
  314.                     1           2           6
  315.                    / \          |
  316.                   3   5         4
  317.                  /              |
  318.                 7               8
  319.  
  320. "find" returns the number of the root element (= the identifier of the set)
  321. of the tree in which the given element is contained:
  322.  
  323.       find(a) := i  so that  a in Si
  324.  
  325. It also reduces the height of that tree by changing all the pointers from
  326. the given element up to the root element to point DIRECTLY to the root
  327. element.
  328.  
  329. Example:
  330.  
  331.     find(7) returns "1" and modifies the array as follows:
  332.  
  333.             i  : |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
  334.     -------------+-----+-----+-----+-----+-----+-----+-----+-----+
  335.      parent[i] : | -4  | -3  |  1  |  2  |  1  | -1  |  1  |  4  |
  336.  
  337.                     1           2           6
  338.                    /|\          |
  339.                   3 5 7         4
  340.                                 |
  341.                                 8
  342.  
  343. "union" takes the identifiers of two sets (= the numbers of their respective
  344. root elements) and merges the two sets by appending one of the two trees to
  345. the other. It always appends the SMALLER set to the LARGER one (to keep the
  346. height of the resulting tree as small as possible) and updates the number of
  347. elements contained in the resulting set which is stored in the root element's
  348. cell of the array.
  349.  
  350. Example:
  351.  
  352.     union(2,6) does the following:
  353.  
  354.             i  : |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
  355.     -------------+-----+-----+-----+-----+-----+-----+-----+-----+
  356.      parent[i] : | -4  | -4  |  1  |  2  |  1  |  2  |  1  |  4  |
  357.  
  358.                     1           2
  359.                    /|\         / \
  360.                   3 5 7       4   6
  361.                               |
  362.                               8
  363.  
  364.     complexity for O(n) "find" operations: O( G(n) n )
  365.  
  366.     complexity for one "union" operation: O(1)
  367.  
  368.     complexity for O(n) ( "find" + "union" ) operations: O( G(n) n )
  369.  
  370.     where  G(n) := min{ j | F(j) >= n }
  371.  
  372.     and    F(j) := 1            for j = 0
  373.            F(j) := 2 ^ F(j-1)   for j > 0
  374.  
  375.     also,  G(n) <= ld n         for all n
  376.  
  377. =item *
  378.  
  379. C<&kruskal();>
  380.  
  381. This routine carries out the computations associated with Kruskal's algorithm.
  382.  
  383. Returns an array of hashes (each hash containing the keys "from", "to" and
  384. "cost" and the corresponding values) representing the minimal spanning tree
  385. of the graph previously defined by calls to "define_vortices" and
  386. "define_edges".
  387.  
  388. The result can also be found in @Graph::Kruskal::T.
  389.  
  390. See the implementation of the subroutine "example" to see how to access this
  391. array directly (remember to fully qualify the name of this array in your
  392. program, i.e., use "@Graph::Kruskal::T" instead of just "@T", since this array
  393. is not exported - or your program will not work!)
  394.  
  395. =item *
  396.  
  397. C<&example();>
  398.  
  399. Demonstrates how to use the various subroutines in this module.
  400.  
  401. Computes the minimal spanning tree of a sample graph.
  402.  
  403. Just say "use Graph::Kruskal qw(example);" and "&example();" in a little
  404. Perl script to see it "in action".
  405.  
  406. =back
  407.  
  408. =head1 DESCRIPTION
  409.  
  410. This algorithm computes the Minimal Spanning Tree of a given graph
  411. according to some cost function defined on the edges of that graph.
  412.  
  413. Input: A set of vortices which constitute a graph (some cities on a map,
  414. for example), a set of edges (i.e., roads) between the vortices of the
  415. (non-directed and connected) graph (i.e., the edges can be traveled in
  416. either direction, and a path must exist between any two vortices), and
  417. the cost of each edge (for instance, the geographical distance).
  418.  
  419. Output: A set of edges forming a spanning tree (i.e., a set of edges linking
  420. all vortices, so that a path exists between any two vortices) which is free
  421. of circles (because it's a tree) and which is minimal in terms of the cost
  422. function defined on the set of edges.
  423.  
  424. See Aho, Hopcroft, Ullman, "The Design and Analysis of Computer Algorithms"
  425. for more details on the algorithm.
  426.  
  427. =head1 SEE ALSO
  428.  
  429. Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3),
  430. Set::IntegerRange(3), Set::IntegerFast(3), Bit::Vector(3).
  431.  
  432. =head1 VERSION
  433.  
  434. This man page documents "Graph::Kruskal" version 2.0.
  435.  
  436. =head1 AUTHOR
  437.  
  438. Steffen Beyer <sb@sdm.de>.
  439.  
  440. =head1 COPYRIGHT
  441.  
  442. Copyright (c) 1995, 1996, 1997 by Steffen Beyer. All rights reserved.
  443.  
  444. =head1 LICENSE
  445.  
  446. This package is free software; you can redistribute it and/or modify
  447. it under the same terms as Perl itself.
  448.  
  449.