home *** CD-ROM | disk | FTP | other *** search
/ CD Actual Thematic 7: Programming / CDAT7.iso / Share / Editores / Perl5 / perl / lib / site / Math / MatrixBool.pm < prev    next >
Encoding:
Perl POD Document  |  1997-08-10  |  46.1 KB  |  1,950 lines
  1.  
  2. #  Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.
  3. #  This package is free software; you can redistribute it and/or
  4. #  modify it under the same terms as Perl itself.
  5.  
  6. package Math::MatrixBool;
  7.  
  8. use strict;
  9. use vars qw(@ISA @EXPORT @EXPORT_OK $VERSION);
  10.  
  11. require Exporter;
  12.  
  13. @ISA = qw(Exporter);
  14.  
  15. @EXPORT = qw();
  16.  
  17. @EXPORT_OK = qw();
  18.  
  19. $VERSION = '4.2';
  20.  
  21. use Carp;
  22.  
  23. use Bit::Vector;
  24.  
  25. use overload
  26.      'neg' => '_complement',
  27.        '~' => '_complement',
  28.     'bool' => '_boolean',
  29.        '!' => '_not_boolean',
  30.       '""' => '_string',
  31.      'abs' => '_number_of_elements',
  32.        '+' => '_addition',
  33.        '*' => '_multiplication',
  34.        '|' => '_union',
  35.        '-' => '_difference',
  36.        '&' => '_intersection',
  37.        '^' => '_exclusive_or',
  38.       '+=' => '_assign_addition',
  39.       '*=' => '_assign_multiplication',
  40.       '|=' => '_assign_union',
  41.       '-=' => '_assign_difference',
  42.       '&=' => '_assign_intersection',
  43.       '^=' => '_assign_exclusive_or',
  44.       '==' => '_equal',
  45.       '!=' => '_not_equal',
  46.        '<' => '_true_sub_set',
  47.       '<=' => '_sub_set',
  48.        '>' => '_true_super_set',
  49.       '>=' => '_super_set',
  50.      'cmp' => '_compare',
  51.        '=' => '_clone',
  52. 'fallback' =>   undef;
  53.  
  54. sub new
  55. {
  56.     croak "Usage: \$new_matrix = Math::MatrixBool->new(\$rows,\$columns);"
  57.       if (@_ != 3);
  58.  
  59.     my $proto = shift;
  60.     my $class = ref($proto) || $proto || 'Math::MatrixBool';
  61.     my $rows = shift;
  62.     my $cols = shift;
  63.     my $object;
  64.     my $matrix;
  65.  
  66.     croak "Math::MatrixBool::new(): number of rows must be > 0"
  67.       if ($rows <= 0);
  68.  
  69.     croak "Math::MatrixBool::new(): number of columns must be > 0"
  70.       if ($cols <= 0);
  71.  
  72.     $matrix = Bit::Vector->new($rows * $cols);
  73.     if ((defined $matrix) && ref($matrix) && (${$matrix} != 0))
  74.     {
  75.         $object = [ $matrix, $rows, $cols ];
  76.         bless($object, $class);
  77.         return($object);
  78.     }
  79.     else
  80.     {
  81.         croak
  82.   "Math::MatrixBool::new(): unable to create new 'Math::MatrixBool' object";
  83.     }
  84. }
  85.  
  86. sub new_from_string
  87. {
  88.     croak "Usage: \$new_matrix = Math::MatrixBool->new_from_string(\$string);"
  89.       if (@_ != 2);
  90.  
  91.     my $proto  = shift;
  92.     my $class  = ref($proto) || $proto || 'Math::MatrixBool';
  93.     my $string = shift;
  94.     my($line,$values);
  95.     my($rows,$cols);
  96.     my($row,$col);
  97.     my($warn);
  98.     my($object);
  99.  
  100.     $warn = 0;
  101.     $rows = 0;
  102.     $cols = 0;
  103.     $values = [ ];
  104.     while ($string =~ m!^\s* \[ \s+ ( (?: (?: 0|1 ) \s+ )+ ) \] \s*? \n !x)
  105.     {
  106.         $line = $1;
  107.         $string = $';
  108.         $values->[$rows] = [ ];
  109.         @{$values->[$rows]} = split(' ', $line);
  110.         $col = @{$values->[$rows]};
  111.         if ($col != $cols)
  112.         {
  113.             unless ($cols == 0) { $warn = 1; }
  114.             if ($col > $cols) { $cols = $col; }
  115.         }
  116.         $rows++;
  117.     }
  118.     if ($string !~ m!^\s*$!)
  119.     {
  120.         croak "Math::MatrixBool::new_from_string(): syntax error in input string";
  121.     }
  122.     if ($rows == 0)
  123.     {
  124.         croak "Math::MatrixBool::new_from_string(): empty input string";
  125.     }
  126.     if ($warn)
  127.     {
  128.         warn "Math::MatrixBool::new_from_string(): missing elements will be set to zero!\n";
  129.     }
  130.     $object = Math::MatrixBool::new($class,$rows,$cols);
  131.     for ( $row = 0; $row < $rows; $row++ )
  132.     {
  133.         for ( $col = 0; $col < @{$values->[$row]}; $col++ )
  134.         {
  135.             if ($values->[$row][$col] != 0)
  136.             {
  137.                 $object->[0]->Bit_On( $row * $cols + $col );
  138.             }
  139.         }
  140.     }
  141.     return($object);
  142. }
  143.  
  144. sub Dim  #  Returns dimensions of a matrix
  145. {
  146.     croak "Usage: (\$rows,\$columns) = \$matrix->Dim();"
  147.       if (@_ != 1);
  148.  
  149.     my($matrix) = @_;
  150.  
  151.     return( $matrix->[1], $matrix->[2] );
  152. }
  153.  
  154. sub Empty
  155. {
  156.     croak "Usage: \$matrix->Empty();"
  157.       if (@_ != 1);
  158.  
  159.     my($object) = @_;
  160.  
  161.     $object->[0]->Empty();
  162. }
  163.  
  164. sub Fill
  165. {
  166.     croak "Usage: \$matrix->Fill();"
  167.       if (@_ != 1);
  168.  
  169.     my($object) = @_;
  170.  
  171.     $object->[0]->Fill();
  172. }
  173.  
  174. sub Flip
  175. {
  176.     croak "Usage: \$matrix->Flip();"
  177.       if (@_ != 1);
  178.  
  179.     my($object) = @_;
  180.  
  181.     $object->[0]->Flip();
  182. }
  183.  
  184. sub Zero
  185. {
  186.     croak "Usage: \$matrix->Zero();"
  187.       if (@_ != 1);
  188.  
  189.     my($object) = @_;
  190.  
  191.     $object->[0]->Empty();
  192. }
  193.  
  194. sub One  #  Fills main diagonal
  195. {
  196.     croak "Usage: \$matrix->One();"
  197.       if (@_ != 1);
  198.  
  199.     my($object) = @_;
  200.     my($rows,$cols) = ($object->[1],$object->[2]);
  201.     my($i,$k);
  202.  
  203.     $object->[0]->Empty();
  204.     $k = ($rows <= $cols) ? $rows : $cols;
  205.     for ( $i = 0; $i < $k; $i++ )
  206.     {
  207.         $object->[0]->Bit_On( $i * $cols + $i );
  208.     }
  209. }
  210.  
  211. sub Bit_On
  212. {
  213.     croak "Usage: \$matrix->Bit_On(\$row,\$column);"
  214.       if (@_ != 3);
  215.  
  216.     my($object,$row,$col) = @_;
  217.     my($rows,$cols) = ($object->[1],$object->[2]);
  218.  
  219.     croak "Math::MatrixBool::Bit_On(): row index out of range"
  220.       if (($row < 1) || ($row > $rows));
  221.     croak "Math::MatrixBool::Bit_On(): column index out of range"
  222.       if (($col < 1) || ($col > $cols));
  223.  
  224.     $object->[0]->Bit_On( --$row * $cols + --$col );
  225. }
  226.  
  227. sub Insert
  228. {
  229.     Bit_On(@_);
  230. }
  231.  
  232. sub Bit_Off
  233. {
  234.     croak "Usage: \$matrix->Bit_Off(\$row,\$column);"
  235.       if (@_ != 3);
  236.  
  237.     my($object,$row,$col) = @_;
  238.     my($rows,$cols) = ($object->[1],$object->[2]);
  239.  
  240.     croak "Math::MatrixBool::Bit_Off(): row index out of range"
  241.       if (($row < 1) || ($row > $rows));
  242.     croak "Math::MatrixBool::Bit_Off(): column index out of range"
  243.       if (($col < 1) || ($col > $cols));
  244.  
  245.     $object->[0]->Bit_Off( --$row * $cols + --$col );
  246. }
  247.  
  248. sub Delete
  249. {
  250.     Bit_Off(@_);
  251. }
  252.  
  253. sub bit_flip
  254. {
  255.     croak "Usage: \$boolean = \$matrix->bit_flip(\$row,\$column);"
  256.       if (@_ != 3);
  257.  
  258.     my($object,$row,$col) = @_;
  259.     my($rows,$cols) = ($object->[1],$object->[2]);
  260.  
  261.     croak "Math::MatrixBool::bit_flip(): row index out of range"
  262.       if (($row < 1) || ($row > $rows));
  263.     croak "Math::MatrixBool::bit_flip(): column index out of range"
  264.       if (($col < 1) || ($col > $cols));
  265.  
  266.     return( $object->[0]->bit_flip( --$row * $cols + --$col ) );
  267. }
  268.  
  269. sub flip
  270. {
  271.     return( bit_flip(@_) );
  272. }
  273.  
  274. sub bit_test
  275. {
  276.     croak "Usage: \$boolean = \$matrix->bit_test(\$row,\$column);"
  277.       if (@_ != 3);
  278.  
  279.     my($object,$row,$col) = @_;
  280.     my($rows,$cols) = ($object->[1],$object->[2]);
  281.  
  282.     croak "Math::MatrixBool::bit_test(): row index out of range"
  283.       if (($row < 1) || ($row > $rows));
  284.     croak "Math::MatrixBool::bit_test(): column index out of range"
  285.       if (($col < 1) || ($col > $cols));
  286.  
  287.     return( $object->[0]->bit_test( --$row * $cols + --$col ) );
  288. }
  289.  
  290. sub contains
  291. {
  292.     return( bit_test(@_) );
  293. }
  294.  
  295. sub in
  296. {
  297.     return( bit_test(@_) );
  298. }
  299.  
  300. sub Number_of_elements  #  returns the number of elements which are set
  301. {
  302.     croak "Usage: \$elements = \$matrix->Number_of_elements();"
  303.       if (@_ != 1);
  304.  
  305.     my($object) = @_;
  306.  
  307.     return( $object->[0]->Norm() );
  308. }
  309.  
  310. sub Norm_max  #  Maximum of sums of each row
  311. {
  312.     croak "Usage: \$norm_max = \$matrix->Norm_max();"
  313.       if (@_ != 1);
  314.  
  315.     my($object) = @_;
  316.     my($rows,$cols) = ($object->[1],$object->[2]);
  317.     my($max,$sum,$i,$j);
  318.  
  319.     $max = 0;
  320.     for ( $i = 0; $i < $rows; $i++ )
  321.     {
  322.         $sum = 0;
  323.         for ( $j = 0; $j < $cols; $j++ )
  324.         {
  325.             $sum ^= $object->[0]->bit_test( $i * $cols + $j );
  326.             # in general, this is $sum += abs( $matrix[$i][$j] );
  327.         }
  328.         if ($sum > $max) { $max = $sum; }
  329.     }
  330.     return($max);
  331. }
  332.  
  333. sub Norm_one  #  Maximum of sums of each column
  334. {
  335.     croak "Usage: \$norm_one = \$matrix->Norm_one();"
  336.       if (@_ != 1);
  337.  
  338.     my($object) = @_;
  339.     my($rows,$cols) = ($object->[1],$object->[2]);
  340.     my($max,$sum,$i,$j);
  341.  
  342.     $max = 0;
  343.     for ( $j = 0; $j < $cols; $j++ )
  344.     {
  345.         $sum = 0;
  346.         for ( $i = 0; $i < $rows; $i++ )
  347.         {
  348.             $sum ^= $object->[0]->bit_test( $i * $cols + $j );
  349.             # in general, this is $sum += abs( $matrix[$i][$j] );
  350.         }
  351.         if ($sum > $max) { $max = $sum; }
  352.     }
  353.     return($max);
  354. }
  355.  
  356. sub Addition
  357. {
  358.     croak "Usage: \$matrix1->Addition(\$matrix2,\$matrix3);"
  359.       if (@_ != 3);
  360.  
  361.     my($matrix1,$matrix2,$matrix3) = @_;
  362.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  363.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  364.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  365.  
  366.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  367.         ($cols1 == $cols2) && ($cols1 == $cols3))
  368.     {
  369.         $matrix1->[0]->ExclusiveOr($matrix2->[0],$matrix3->[0]);
  370.     }
  371.     else
  372.     {
  373.         croak "Math::MatrixBool::Addition(): matrix size mismatch";
  374.     }
  375. }
  376.  
  377. sub Multiplication
  378. {
  379.     croak "Usage: \$product_matrix = \$matrix1->Multiplication(\$matrix2);"
  380.       if (@_ != 2);
  381.  
  382.     my($matrix1,$matrix2) = @_;
  383.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  384.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  385.     my($result);
  386.  
  387.     if ($cols1 == $rows2)
  388.     {
  389.         $result = $matrix1->new($rows1,$cols2);
  390.         $result->[0]->Multiplication($rows1,$cols2,
  391.                      $matrix1->[0],$rows1,$cols1,
  392.                      $matrix2->[0],$rows2,$cols2);
  393.     }
  394.     else
  395.     {
  396.         croak "Math::MatrixBool::Multiplication(): matrix size mismatch";
  397.     }
  398.     return($result);
  399. }
  400.  
  401. sub Kleene
  402. {
  403.     croak "Usage: \$closure = \$matrix->Kleene();"
  404.       if (@_ != 1);
  405.  
  406.     my($matrix) = @_;
  407.     my($rows,$cols) = ($matrix->[1],$matrix->[2]);
  408.     my($result);
  409.  
  410.     croak "Math::MatrixBool::Kleene(): matrix is not quadratic"
  411.       if ($rows != $cols);
  412.  
  413.     $result = $matrix->new($rows,$cols);
  414.     $result->Copy($matrix);
  415.     $result->[0]->Closure($rows,$cols);
  416.  
  417.     return($result);
  418. }
  419.  
  420. sub Union
  421. {
  422.     croak "Usage: \$matrix1->Union(\$matrix2,\$matrix3);"
  423.       if (@_ != 3);
  424.  
  425.     my($matrix1,$matrix2,$matrix3) = @_;
  426.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  427.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  428.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  429.  
  430.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  431.         ($cols1 == $cols2) && ($cols1 == $cols3))
  432.     {
  433.         $matrix1->[0]->Union($matrix2->[0],$matrix3->[0]);
  434.     }
  435.     else
  436.     {
  437.         croak "Math::MatrixBool::Union(): matrix size mismatch";
  438.     }
  439. }
  440.  
  441. sub Intersection
  442. {
  443.     croak "Usage: \$matrix1->Intersection(\$matrix2,\$matrix3);"
  444.       if (@_ != 3);
  445.  
  446.     my($matrix1,$matrix2,$matrix3) = @_;
  447.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  448.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  449.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  450.  
  451.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  452.         ($cols1 == $cols2) && ($cols1 == $cols3))
  453.     {
  454.         $matrix1->[0]->Intersection($matrix2->[0],$matrix3->[0]);
  455.     }
  456.     else
  457.     {
  458.         croak "Math::MatrixBool::Intersection(): matrix size mismatch";
  459.     }
  460. }
  461.  
  462. sub Difference
  463. {
  464.     croak "Usage: \$matrix1->Difference(\$matrix2,\$matrix3);"
  465.       if (@_ != 3);
  466.  
  467.     my($matrix1,$matrix2,$matrix3) = @_;
  468.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  469.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  470.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  471.  
  472.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  473.         ($cols1 == $cols2) && ($cols1 == $cols3))
  474.     {
  475.         $matrix1->[0]->Difference($matrix2->[0],$matrix3->[0]);
  476.     }
  477.     else
  478.     {
  479.         croak "Math::MatrixBool::Difference(): matrix size mismatch";
  480.     }
  481. }
  482.  
  483. sub ExclusiveOr
  484. {
  485.     croak "Usage: \$matrix1->ExclusiveOr(\$matrix2,\$matrix3);"
  486.       if (@_ != 3);
  487.  
  488.     my($matrix1,$matrix2,$matrix3) = @_;
  489.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  490.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  491.     my($rows3,$cols3) = ($matrix3->[1],$matrix3->[2]);
  492.  
  493.     if (($rows1 == $rows2) && ($rows1 == $rows3) &&
  494.         ($cols1 == $cols2) && ($cols1 == $cols3))
  495.     {
  496.         $matrix1->[0]->ExclusiveOr($matrix2->[0],$matrix3->[0]);
  497.     }
  498.     else
  499.     {
  500.         croak "Math::MatrixBool::ExclusiveOr(): matrix size mismatch";
  501.     }
  502. }
  503.  
  504. sub Complement
  505. {
  506.     croak "Usage: \$matrix1->Complement(\$matrix2);"
  507.       if (@_ != 2);
  508.  
  509.     my($matrix1,$matrix2) = @_;
  510.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  511.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  512.  
  513.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  514.     {
  515.         $matrix1->[0]->Complement($matrix2->[0]);
  516.     }
  517.     else
  518.     {
  519.         croak "Math::MatrixBool::Complement(): matrix size mismatch";
  520.     }
  521. }
  522.  
  523. sub equal
  524. {
  525.     croak "Usage: \$boolean = \$matrix1->equal(\$matrix2);"
  526.       if (@_ != 2);
  527.  
  528.     my($matrix1,$matrix2) = @_;
  529.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  530.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  531.  
  532.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  533.     {
  534.         return( $matrix1->[0]->equal($matrix2->[0]) );
  535.     }
  536.     else
  537.     {
  538.         croak "Math::MatrixBool::equal(): matrix size mismatch";
  539.     }
  540. }
  541.  
  542. sub subset
  543. {
  544.     croak "Usage: \$boolean = \$matrix1->subset(\$matrix2);"
  545.       if (@_ != 2);
  546.  
  547.     my($matrix1,$matrix2) = @_;
  548.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  549.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  550.  
  551.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  552.     {
  553.         return( $matrix1->[0]->subset($matrix2->[0]) );
  554.     }
  555.     else
  556.     {
  557.         croak "Math::MatrixBool::subset(): matrix size mismatch";
  558.     }
  559. }
  560.  
  561. sub inclusion
  562. {
  563.     return( subset(@_) );
  564. }
  565.  
  566. sub lexorder
  567. {
  568.     croak "Usage: \$boolean = \$matrix1->lexorder(\$matrix2);"
  569.       if (@_ != 2);
  570.  
  571.     my($matrix1,$matrix2) = @_;
  572.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  573.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  574.  
  575.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  576.     {
  577.         return( $matrix1->[0]->lexorder($matrix2->[0]) );
  578.     }
  579.     else
  580.     {
  581.         croak "Math::MatrixBool::lexorder(): matrix size mismatch";
  582.     }
  583. }
  584.  
  585. sub Compare
  586. {
  587.     croak "Usage: \$result = \$matrix1->Compare(\$matrix2);"
  588.       if (@_ != 2);
  589.  
  590.     my($matrix1,$matrix2) = @_;
  591.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  592.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  593.  
  594.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  595.     {
  596.         return( $matrix1->[0]->Compare($matrix2->[0]) );
  597.     }
  598.     else
  599.     {
  600.         croak "Math::MatrixBool::Compare(): matrix size mismatch";
  601.     }
  602. }
  603.  
  604. sub Copy
  605. {
  606.     croak "Usage: \$matrix1->Copy(\$matrix2);"
  607.       if (@_ != 2);
  608.  
  609.     my($matrix1,$matrix2) = @_;
  610.     my($rows1,$cols1) = ($matrix1->[1],$matrix1->[2]);
  611.     my($rows2,$cols2) = ($matrix2->[1],$matrix2->[2]);
  612.  
  613.     if (($rows1 == $rows2) && ($cols1 == $cols2))
  614.     {
  615.         $matrix1->[0]->Copy($matrix2->[0]);
  616.     }
  617.     else
  618.     {
  619.         croak "Math::MatrixBool::Copy(): matrix size mismatch";
  620.     }
  621. }
  622.  
  623. sub Shadow
  624. {
  625.     croak "Usage: \$other_matrix = \$some_matrix->Shadow();"
  626.       if (@_ != 1);
  627.  
  628.     my($matrix) = @_;
  629.     my($result);
  630.  
  631.     $result = $matrix->new($matrix->[1],$matrix->[2]);
  632.     return($result);
  633. }
  634.  
  635. sub Clone
  636. {
  637.     croak "Usage: \$twin_matrix = \$some_matrix->Clone();"
  638.       if (@_ != 1);
  639.  
  640.     my($matrix) = @_;
  641.     my($result);
  642.  
  643.     $result = $matrix->new($matrix->[1],$matrix->[2]);
  644.     $result->Copy($matrix);
  645.     return($result);
  646. }
  647.  
  648.                 ########################################
  649.                 #                                      #
  650.                 # define overloaded operators section: #
  651.                 #                                      #
  652.                 ########################################
  653.  
  654. sub _complement
  655. {
  656.     my($object,$argument,$flag) = @_;
  657. #   my($name) = "'~'"; #&_trace($name,$object,$argument,$flag);
  658.     my($result);
  659.  
  660.     $result = $object->new($object->[1],$object->[2]);
  661.     $result->Complement($object);
  662.     return($result);
  663. }
  664.  
  665. sub _boolean
  666. {
  667.     my($object,$argument,$flag) = @_;
  668. #   my($name) = "bool"; #&_trace($name,$object,$argument,$flag);
  669.  
  670.     return( $object->[0]->Min() < $object->[1] * $object->[2] );
  671. }
  672.  
  673. sub _not_boolean
  674. {
  675.     my($object,$argument,$flag) = @_;
  676. #   my($name) = "'!'"; #&_trace($name,$object,$argument,$flag);
  677.  
  678.     return( !($object->[0]->Min() < $object->[1] * $object->[2]) );
  679. }
  680.  
  681. sub _string
  682. {
  683.     my($object,$argument,$flag) = @_;
  684. #   my($name) = '""'; #&_trace($name,$object,$argument,$flag);
  685.     my($rows,$cols) = ($object->[1],$object->[2]);
  686.     my($i,$j,$s);
  687.  
  688.     $s = '';
  689.     for ( $i = 1; $i <= $rows; $i++ )
  690.     {
  691.         $s .= "[ ";
  692.         for ( $j = 1; $j <= $cols; $j++ )
  693.         {
  694.             if ($object->bit_test($i,$j)) { $s .= "1 "; } else { $s .= "0 "; }
  695.         }
  696.         $s .= "]\n";
  697.     }
  698.     return($s);
  699. }
  700.  
  701. sub _number_of_elements
  702. {
  703.     my($object,$argument,$flag) = @_;
  704. #   my($name) = "abs"; #&_trace($name,$object,$argument,$flag);
  705.  
  706.     return( $object->Number_of_elements() );
  707. }
  708.  
  709. sub _addition
  710. {
  711.     my($object,$argument,$flag) = @_;
  712.     my($name) = "'+'"; #&_trace($name,$object,$argument,$flag);
  713.     my($result);
  714.  
  715.     if ((defined $argument) && ref($argument) &&
  716.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  717.     {
  718.         if (defined $flag)
  719.         {
  720.             $result = $object->new($object->[1],$object->[2]);
  721.             $result->ExclusiveOr($object,$argument);
  722.             return($result);
  723.         }
  724.         else
  725.         {
  726.             $object->ExclusiveOr($object,$argument);
  727.             return($object);
  728.         }
  729.     }
  730.     else
  731.     {
  732.         croak "Math::MatrixBool $name: wrong argument type";
  733.     }
  734. }
  735.  
  736. sub _multiplication
  737. {
  738.     my($object,$argument,$flag) = @_;
  739.     my($name) = "'*'"; #&_trace($name,$object,$argument,$flag);
  740.     my($result);
  741.  
  742.     if ((defined $argument) && ref($argument) &&
  743.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  744.     {
  745.         if ((defined $flag) && $flag)
  746.         {
  747.             return( Multiplication($argument,$object) );
  748.         }
  749.         else
  750.         {
  751.             return( Multiplication($object,$argument) );
  752.         }
  753.     }
  754.     else
  755.     {
  756.         croak "Math::MatrixBool $name: wrong argument type";
  757.     }
  758. }
  759.  
  760. sub _union
  761. {
  762.     my($object,$argument,$flag) = @_;
  763.     my($name) = "'|'"; #&_trace($name,$object,$argument,$flag);
  764.     my($result);
  765.  
  766.     if ((defined $argument) && ref($argument) &&
  767.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  768.     {
  769.         if (defined $flag)
  770.         {
  771.             $result = $object->new($object->[1],$object->[2]);
  772.             $result->Union($object,$argument);
  773.             return($result);
  774.         }
  775.         else
  776.         {
  777.             $object->Union($object,$argument);
  778.             return($object);
  779.         }
  780.     }
  781.     else
  782.     {
  783.         croak "Math::MatrixBool $name: wrong argument type";
  784.     }
  785. }
  786.  
  787. sub _difference
  788. {
  789.     my($object,$argument,$flag) = @_;
  790.     my($name) = "'-'"; #&_trace($name,$object,$argument,$flag);
  791.     my($result);
  792.  
  793.     if ((defined $argument) && ref($argument) &&
  794.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  795.     {
  796.         if (defined $flag)
  797.         {
  798.             $result = $object->new($object->[1],$object->[2]);
  799.             if ($flag) { $result->Difference($argument,$object); }
  800.             else       { $result->Difference($object,$argument); }
  801.             return($result);
  802.         }
  803.         else
  804.         {
  805.             $object->Difference($object,$argument);
  806.             return($object);
  807.         }
  808.     }
  809.     else
  810.     {
  811.         croak "Math::MatrixBool $name: wrong argument type";
  812.     }
  813. }
  814.  
  815. sub _intersection
  816. {
  817.     my($object,$argument,$flag) = @_;
  818.     my($name) = "'&'"; #&_trace($name,$object,$argument,$flag);
  819.     my($result);
  820.  
  821.     if ((defined $argument) && ref($argument) &&
  822.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  823.     {
  824.         if (defined $flag)
  825.         {
  826.             $result = $object->new($object->[1],$object->[2]);
  827.             $result->Intersection($object,$argument);
  828.             return($result);
  829.         }
  830.         else
  831.         {
  832.             $object->Intersection($object,$argument);
  833.             return($object);
  834.         }
  835.     }
  836.     else
  837.     {
  838.         croak "Math::MatrixBool $name: wrong argument type";
  839.     }
  840. }
  841.  
  842. sub _exclusive_or
  843. {
  844.     my($object,$argument,$flag) = @_;
  845.     my($name) = "'^'"; #&_trace($name,$object,$argument,$flag);
  846.     my($result);
  847.  
  848.     if ((defined $argument) && ref($argument) &&
  849.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  850.     {
  851.         if (defined $flag)
  852.         {
  853.             $result = $object->new($object->[1],$object->[2]);
  854.             $result->ExclusiveOr($object,$argument);
  855.             return($result);
  856.         }
  857.         else
  858.         {
  859.             $object->ExclusiveOr($object,$argument);
  860.             return($object);
  861.         }
  862.     }
  863.     else
  864.     {
  865.         croak "Math::MatrixBool $name: wrong argument type";
  866.     }
  867. }
  868.  
  869. sub _assign_addition
  870. {
  871.     my($object,$argument,$flag) = @_;
  872. #   my($name) = "'+='"; #&_trace($name,$object,$argument,$flag);
  873.  
  874.     return( &_addition($object,$argument,undef) );
  875. }
  876.  
  877. sub _assign_multiplication
  878. {
  879.     my($object,$argument,$flag) = @_;
  880. #   my($name) = "'*='"; #&_trace($name,$object,$argument,$flag);
  881.  
  882.     return( &_multiplication($object,$argument,undef) );
  883. }
  884.  
  885. sub _assign_union
  886. {
  887.     my($object,$argument,$flag) = @_;
  888. #   my($name) = "'|='"; #&_trace($name,$object,$argument,$flag);
  889.  
  890.     return( &_union($object,$argument,undef) );
  891. }
  892.  
  893. sub _assign_difference
  894. {
  895.     my($object,$argument,$flag) = @_;
  896. #   my($name) = "'-='"; #&_trace($name,$object,$argument,$flag);
  897.  
  898.     return( &_difference($object,$argument,undef) );
  899. }
  900.  
  901. sub _assign_intersection
  902. {
  903.     my($object,$argument,$flag) = @_;
  904. #   my($name) = "'&='"; #&_trace($name,$object,$argument,$flag);
  905.  
  906.     return( &_intersection($object,$argument,undef) );
  907. }
  908.  
  909. sub _assign_exclusive_or
  910. {
  911.     my($object,$argument,$flag) = @_;
  912. #   my($name) = "'^='"; #&_trace($name,$object,$argument,$flag);
  913.  
  914.     return( &_exclusive_or($object,$argument,undef) );
  915. }
  916.  
  917. sub _equal
  918. {
  919.     my($object,$argument,$flag) = @_;
  920.     my($name) = "'=='"; #&_trace($name,$object,$argument,$flag);
  921.  
  922.     if ((defined $argument) && ref($argument) &&
  923.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  924.     {
  925.         return( $object->equal($argument) );
  926.     }
  927.     else
  928.     {
  929.         croak "Math::MatrixBool $name: wrong argument type";
  930.     }
  931. }
  932.  
  933. sub _not_equal
  934. {
  935.     my($object,$argument,$flag) = @_;
  936.     my($name) = "'!='"; #&_trace($name,$object,$argument,$flag);
  937.  
  938.     if ((defined $argument) && ref($argument) &&
  939.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  940.     {
  941.         return( !($object->equal($argument)) );
  942.     }
  943.     else
  944.     {
  945.         croak "Math::MatrixBool $name: wrong argument type";
  946.     }
  947. }
  948.  
  949. sub _true_sub_set
  950. {
  951.     my($object,$argument,$flag) = @_;
  952.     my($name) = "'<'"; #&_trace($name,$object,$argument,$flag);
  953.  
  954.     if ((defined $argument) && ref($argument) &&
  955.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  956.     {
  957.         if ((defined $flag) && $flag)
  958.         {
  959.             return( !($argument->equal($object)) &&
  960.                      ($argument->subset($object)) );
  961.         }
  962.         else
  963.         {
  964.             return( !($object->equal($argument)) &&
  965.                      ($object->subset($argument)) );
  966.         }
  967.     }
  968.     else
  969.     {
  970.         croak "Math::MatrixBool $name: wrong argument type";
  971.     }
  972. }
  973.  
  974. sub _sub_set
  975. {
  976.     my($object,$argument,$flag) = @_;
  977.     my($name) = "'<='"; #&_trace($name,$object,$argument,$flag);
  978.  
  979.     if ((defined $argument) && ref($argument) &&
  980.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  981.     {
  982.         if ((defined $flag) && $flag)
  983.         {
  984.             return( $argument->subset($object) );
  985.         }
  986.         else
  987.         {
  988.             return( $object->subset($argument) );
  989.         }
  990.     }
  991.     else
  992.     {
  993.         croak "Math::MatrixBool $name: wrong argument type";
  994.     }
  995. }
  996.  
  997. sub _true_super_set
  998. {
  999.     my($object,$argument,$flag) = @_;
  1000.     my($name) = "'>'"; #&_trace($name,$object,$argument,$flag);
  1001.  
  1002.     if ((defined $argument) && ref($argument) &&
  1003.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  1004.     {
  1005.         if ((defined $flag) && $flag)
  1006.         {
  1007.             return( !($object->equal($argument)) &&
  1008.                      ($object->subset($argument)) );
  1009.         }
  1010.         else
  1011.         {
  1012.             return( !($argument->equal($object)) &&
  1013.                      ($argument->subset($object)) );
  1014.         }
  1015.     }
  1016.     else
  1017.     {
  1018.         croak "Math::MatrixBool $name: wrong argument type";
  1019.     }
  1020. }
  1021.  
  1022. sub _super_set
  1023. {
  1024.     my($object,$argument,$flag) = @_;
  1025.     my($name) = "'>='"; #&_trace($name,$object,$argument,$flag);
  1026.  
  1027.     if ((defined $argument) && ref($argument) &&
  1028.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  1029.     {
  1030.         if ((defined $flag) && $flag)
  1031.         {
  1032.             return( $object->subset($argument) );
  1033.         }
  1034.         else
  1035.         {
  1036.             return( $argument->subset($object) );
  1037.         }
  1038.     }
  1039.     else
  1040.     {
  1041.         croak "Math::MatrixBool $name: wrong argument type";
  1042.     }
  1043. }
  1044.  
  1045. sub _compare
  1046. {
  1047.     my($object,$argument,$flag) = @_;
  1048.     my($name) = "cmp"; #&_trace($name,$object,$argument,$flag);
  1049.  
  1050.     if ((defined $argument) && ref($argument) &&
  1051.         (ref($argument) !~ /^SCALAR$|^ARRAY$|^HASH$|^CODE$|^REF$/))
  1052.     {
  1053.         if ((defined $flag) && $flag)
  1054.         {
  1055.             return( $argument->Compare($object) );
  1056.         }
  1057.         else
  1058.         {
  1059.             return( $object->Compare($argument) );
  1060.         }
  1061.     }
  1062.     else
  1063.     {
  1064.         croak "Math::MatrixBool $name: wrong argument type";
  1065.     }
  1066. }
  1067.  
  1068. sub _clone
  1069. {
  1070.     my($object,$argument,$flag) = @_;
  1071. #   my($name) = "'='"; #&_trace($name,$object,$argument,$flag);
  1072.     my($result);
  1073.  
  1074.     $result = $object->new($object->[1],$object->[2]);
  1075.     $result->Copy($object);
  1076.     return($result);
  1077. }
  1078.  
  1079. sub _trace
  1080. {
  1081.     my($text,$object,$argument,$flag) = @_;
  1082.  
  1083.     unless (defined $object)   { $object   = 'undef'; };
  1084.     unless (defined $argument) { $argument = 'undef'; };
  1085.     unless (defined $flag)     { $flag     = 'undef'; };
  1086.     if (ref($object))   { $object   = ref($object);   }
  1087.     if (ref($argument)) { $argument = ref($argument); }
  1088.     print "$text: \$obj='$object' \$arg='$argument' \$flag='$flag'\n";
  1089. }
  1090.  
  1091. 1;
  1092.  
  1093. __END__
  1094.  
  1095. =head1 NAME
  1096.  
  1097. Math::MatrixBool - Matrix of Booleans
  1098.  
  1099. Easy manipulation of matrices of booleans (Boolean Algebra)
  1100.  
  1101. =head1 SYNOPSIS
  1102.  
  1103. =over 4
  1104.  
  1105. =item *
  1106.  
  1107. C<use Math::MatrixBool;>
  1108.  
  1109. =item *
  1110.  
  1111. C<$new_matrix = new Math::MatrixBool($rows,$columns);>
  1112.  
  1113. the matrix object constructor method
  1114.  
  1115. An exception is raised if the necessary memory cannot be allocated.
  1116.  
  1117. =item *
  1118.  
  1119. C<$new_matrix = Math::MatrixBool-E<gt>new($rows,$columns);>
  1120.  
  1121. alternate way of calling the matrix object constructor method
  1122.  
  1123. =item *
  1124.  
  1125. C<$new_matrix = $some_matrix-E<gt>>C<new($rows,$columns);>
  1126.  
  1127. still another way of calling the matrix object constructor method
  1128. ($some_matrix is not affected by this)
  1129.  
  1130. =item *
  1131.  
  1132. C<$new_matrix = Math::MatrixBool-E<gt>>C<new_from_string($string);>
  1133.  
  1134. This method allows you to read in a matrix from a string (for
  1135. instance, from the keyboard, from a file or from your code).
  1136.  
  1137. The syntax is simple: each row must start with "C<[ >" and end with
  1138. "C< ]\n>" ("C<\n>" being the newline character and "C< >" a space or
  1139. tab) and contain one or more numbers, all separated from each other
  1140. by spaces or tabs.
  1141.  
  1142. Additional spaces or tabs can be added at will, but no comments.
  1143.  
  1144. Numbers are either "0" or "1".
  1145.  
  1146. Examples:
  1147.  
  1148.     $string = "[ 1 0 0 ]\n[ 1 1 0 ]\n[ 1 1 1 ]\n";
  1149.     $matrix = Math::MatrixBool->new_from_string($string);
  1150.     print "$matrix";
  1151.  
  1152. By the way, this prints
  1153.  
  1154.     [ 1 0 0 ]
  1155.     [ 1 1 0 ]
  1156.     [ 1 1 1 ]
  1157.  
  1158. But you can also do this in a much more comfortable way using the
  1159. shell-like "here-document" syntax:
  1160.  
  1161.     $matrix = Math::MatrixBool->new_from_string(<<'MATRIX');
  1162.     [  1  0  0  0  0  0  1  ]
  1163.     [  0  1  0  0  0  0  0  ]
  1164.     [  0  0  1  0  0  0  0  ]
  1165.     [  0  0  0  1  0  0  0  ]
  1166.     [  0  0  0  0  1  0  0  ]
  1167.     [  0  0  0  0  0  1  0  ]
  1168.     [  1  0  0  0  0  0  1  ]
  1169.     MATRIX
  1170.  
  1171. You can even use variables in the matrix:
  1172.  
  1173.     $c1  =  $A1 * $x1 - $b1 >= 0  ?"1":"0";
  1174.     $c1  =  $A2 * $x2 - $b2 >= 0  ?"1":"0";
  1175.     $c1  =  $A3 * $x3 - $b3 >= 0  ?"1":"0";
  1176.  
  1177.     $matrix = Math::MatrixBool->new_from_string(<<"MATRIX");
  1178.  
  1179.         [   1    0    0   ]
  1180.         [   0    1    0   ]
  1181.         [  $c1  $c2  $c3  ]
  1182.  
  1183.     MATRIX
  1184.  
  1185. (Remember that you may use spaces and tabs to format the matrix to
  1186. your taste)
  1187.  
  1188. Note that this method uses exactly the same representation for a
  1189. matrix as the "stringify" operator "": this means that you can convert
  1190. any matrix into a string with C<$string = "$matrix";> and read it back
  1191. in later (for instance from a file!).
  1192.  
  1193. If the string you supply (or someone else supplies) does not obey
  1194. the syntax mentioned above, an exception is raised, which can be
  1195. caught by "eval" as follows:
  1196.  
  1197.     print "Please enter your matrix (in one line): ";
  1198.     $string = <STDIN>;
  1199.     $string =~ s/\\n/\n/g;
  1200.     eval { $matrix = Math::MatrixBool->new_from_string($string); };
  1201.     if ($@)
  1202.     {
  1203.         print "$@";
  1204.         # ...
  1205.         # (error handling)
  1206.     }
  1207.     else
  1208.     {
  1209.         # continue...
  1210.     }
  1211.  
  1212. or as follows:
  1213.  
  1214.     eval { $matrix = Math::MatrixBool->new_from_string(<<"MATRIX"); };
  1215.     [   1    0    0   ]
  1216.     [   0    1    0   ]
  1217.     [  $c1  $c2  $c3  ]
  1218.     MATRIX
  1219.     if ($@)
  1220.     # ...
  1221.  
  1222. Actually, the method shown above for reading a matrix from the keyboard
  1223. is a little awkward, since you have to enter a lot of "\n"'s for the
  1224. newlines.
  1225.  
  1226. A better way is shown in this piece of code:
  1227.  
  1228.   while (1)
  1229.   {
  1230.       print "\nPlease enter your matrix ";
  1231.       print "(multiple lines, <ctrl-D> = done):\n";
  1232.       eval { $new_matrix =
  1233.           Math::MatrixBool->new_from_string(join('',<STDIN>)); };
  1234.       if ($@)
  1235.       {
  1236.           $@ =~ s/\s+at\b.*?$//;
  1237.           print "${@}Please try again.\n";
  1238.       }
  1239.       else { last; }
  1240.   }
  1241.  
  1242. Possible error messages of the "new_from_string()" method are:
  1243.  
  1244.     Math::MatrixBool::new_from_string(): syntax error in input string
  1245.     Math::MatrixBool::new_from_string(): empty input string
  1246.  
  1247. If the input string has rows with varying numbers of columns,
  1248. the following warning will be printed to STDERR:
  1249.  
  1250.     Math::MatrixBool::new_from_string(): missing elements will be set to zero!
  1251.  
  1252. If everything is okay, the method returns an object reference to the
  1253. (newly allocated) matrix containing the elements you specified.
  1254.  
  1255. =item *
  1256.  
  1257. C<($rows,$columns) = $matrix-E<gt>Dim();>
  1258.  
  1259. returns the dimensions (= number of rows and columns) of the given matrix
  1260.  
  1261. =item *
  1262.  
  1263. C<$matrix-E<gt>Empty();>
  1264.  
  1265. sets all elements in the matrix to "0"
  1266.  
  1267. =item *
  1268.  
  1269. C<$matrix-E<gt>Fill();>
  1270.  
  1271. sets all elements in the matrix to "1"
  1272.  
  1273. =item *
  1274.  
  1275. C<$matrix-E<gt>Flip();>
  1276.  
  1277. flips (i.e., complements) all elements in the given matrix
  1278.  
  1279. =item *
  1280.  
  1281. C<$matrix-E<gt>Zero();>
  1282.  
  1283. sets all elements in the matrix to "0"
  1284.  
  1285. =item *
  1286.  
  1287. C<$matrix-E<gt>One();>
  1288.  
  1289. fills the matrix with one's in the main diagonal and zero's elsewhere
  1290.  
  1291. Note that multiplying this matrix with itself yields the same matrix again
  1292. (provided it is quadratic)!
  1293.  
  1294. =item *
  1295.  
  1296. C<$matrix-E<gt>Bit_On($row,$column);>
  1297.  
  1298. sets a given element to "1"
  1299.  
  1300. =item *
  1301.  
  1302. C<$matrix-E<gt>Insert($row,$column);>
  1303.  
  1304. alias for "Bit_On()", deprecated
  1305.  
  1306. =item *
  1307.  
  1308. C<$matrix-E<gt>Bit_Off($row,$column);>
  1309.  
  1310. sets a given element to "0"
  1311.  
  1312. =item *
  1313.  
  1314. C<$matrix-E<gt>Delete($row,$column);>
  1315.  
  1316. alias for "Bit_Off()", deprecated
  1317.  
  1318. =item *
  1319.  
  1320. C<$boolean = $matrix-E<gt>>C<bit_flip($row,$column);>
  1321.  
  1322. flips (i.e., complements) a given element and returns its new value
  1323.  
  1324. =item *
  1325.  
  1326. C<$boolean = $matrix-E<gt>>C<flip($row,$column);>
  1327.  
  1328. alias for "bit_flip()", deprecated
  1329.  
  1330. =item *
  1331.  
  1332. C<$boolean = $matrix-E<gt>>C<bit_test($row,$column);>
  1333.  
  1334. tests wether a given element is set
  1335.  
  1336. =item *
  1337.  
  1338. C<$boolean = $matrix-E<gt>>C<contains($row,$column);>
  1339.  
  1340. tests wether a given element is set (alias for "bit_test()")
  1341.  
  1342. =item *
  1343.  
  1344. C<$boolean = $matrix-E<gt>>C<in($row,$column);>
  1345.  
  1346. alias for "bit_test()", deprecated
  1347.  
  1348. =item *
  1349.  
  1350. C<$elements = $matrix-E<gt>Number_of_elements();>
  1351.  
  1352. calculates the number of elements contained in the given matrix
  1353.  
  1354. =item *
  1355.  
  1356. C<$norm_max = $matrix-E<gt>Norm_max();>
  1357.  
  1358. calculates the "maximum"-norm of the given matrix
  1359.  
  1360. =item *
  1361.  
  1362. C<$norm_one = $matrix-E<gt>Norm_one();>
  1363.  
  1364. calculates the "1"-norm of the given matrix
  1365.  
  1366. =item *
  1367.  
  1368. C<$matrix1-E<gt>Addition($matrix2,$matrix3);>
  1369.  
  1370. calculates the sum of matrix2 and matrix3 and stores the result in matrix1
  1371. (in-place is also possible)
  1372.  
  1373. =item *
  1374.  
  1375. C<$product_matrix = $matrix1-E<gt>Multiplication($matrix2);>
  1376.  
  1377. calculates the product of matrix1 and matrix2 and returns an object reference
  1378. to a new matrix where the result is stored
  1379.  
  1380. =item *
  1381.  
  1382. C<$closure = $matrix-E<gt>Kleene();>
  1383.  
  1384. computes the reflexive transitive closure of the given matrix and returns
  1385. a new matrix containing the result. (The original matrix is not changed by
  1386. this in any way!)
  1387.  
  1388. Uses a variant of Kleene's algorithm. See L<Math::Kleene(3)> for more details
  1389. about this algorithm!
  1390.  
  1391. This algorithm is mainly used in graph theory: Each position in the matrix
  1392. corresponds to a (directed!) possible connection ("edge") between two points
  1393. ("vortices") of a graph. Each position in the matrix contains a "1" if the
  1394. corresponding edge is part of the graph and a "0" if not.
  1395.  
  1396. Computing the closure of this matrix means to find out if there is a path
  1397. from any vortice of the graph to any other (a path consisting of one or more
  1398. edges).
  1399.  
  1400. Note that there are more applications of Kleene's algorithm in other fields
  1401. as well (see also Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3)).
  1402.  
  1403. =item *
  1404.  
  1405. C<$matrix1-E<gt>Union($matrix2,$matrix3);>
  1406.  
  1407. calculates the union of matrix2 and matrix3 and stores the result in matrix1
  1408. (in-place is also possible)
  1409.  
  1410. =item *
  1411.  
  1412. C<$matrix1-E<gt>Intersection($matrix2,$matrix3);>
  1413.  
  1414. calculates the intersection of matrix2 and matrix3 and stores the result in
  1415. matrix1 (in-place is also possible)
  1416.  
  1417. =item *
  1418.  
  1419. C<$matrix1-E<gt>Difference($matrix2,$matrix3);>
  1420.  
  1421. calculates matrix2 "minus" matrix3 ( = matrix2 \ matrix3 ) and stores the
  1422. result in matrix1 (in-place is also possible)
  1423.  
  1424. Note that this is set difference, not matrix difference! Matrix difference
  1425. degenerates to (= is the same as) matrix addition in a Boolean Algebra!!
  1426.  
  1427. =item *
  1428.  
  1429. C<$matrix1-E<gt>ExclusiveOr($matrix2,$matrix3);>
  1430.  
  1431. calculates the exclusive-or (which in the case of a Boolean Algebra happens
  1432. to be the same as the addition) of matrix2 and matrix3 and stores the
  1433. result in matrix1 (in-place is also possible)
  1434.  
  1435. =item *
  1436.  
  1437. C<$matrix1-E<gt>Complement($matrix2);>
  1438.  
  1439. calculates the complement of matrix2 and stores the result in matrix1
  1440. (in-place is also possible)
  1441.  
  1442. =item *
  1443.  
  1444. C<$boolean = $matrix1-E<gt>equal($matrix2);>
  1445.  
  1446. tests if matrix1 is the same as matrix2
  1447.  
  1448. =item *
  1449.  
  1450. C<$boolean = $matrix1-E<gt>subset($matrix2);>
  1451.  
  1452. tests if matrix1 is a subset of matrix2
  1453.  
  1454. =item *
  1455.  
  1456. C<$boolean = $matrix1-E<gt>inclusion($matrix2);>
  1457.  
  1458. alias for "subset()", deprecated
  1459.  
  1460. =item *
  1461.  
  1462. C<$boolean = $matrix1-E<gt>lexorder($matrix2);>
  1463.  
  1464. tests if matrix1 comes lexically before matrix2, i.e., if (matrix1 <= matrix2)
  1465. holds, as though the two bit vectors used to represent the two matrices were
  1466. two large numbers in binary representation
  1467.  
  1468. (Note that this is an B<arbitrary> order relationship!)
  1469.  
  1470. =item *
  1471.  
  1472. C<$result = $matrix1-E<gt>Compare($matrix2);>
  1473.  
  1474. lexically compares matrix1 and matrix2 and returns -1, 0 or 1 if
  1475. (matrix1 < matrix2), (matrix1 == matrix2) or (matrix1 > matrix2) holds,
  1476. respectively
  1477.  
  1478. (Again, the two bit vectors representing the two matrices are compared as
  1479. though they were two large numbers in binary representation)
  1480.  
  1481. =item *
  1482.  
  1483. C<$matrix1-E<gt>Copy($matrix2);>
  1484.  
  1485. copies the contents of matrix2 to an B<ALREADY EXISTING> matrix1
  1486.  
  1487. =item *
  1488.  
  1489. C<$new_matrix = $some_matrix-E<gt>Shadow();>
  1490.  
  1491. returns an object reference to a B<NEW> but B<EMPTY> matrix of
  1492. the B<SAME SIZE> as some_matrix
  1493.  
  1494. =item *
  1495.  
  1496. C<$twin_matrix = $some_matrix-E<gt>Clone();>
  1497.  
  1498. returns an object reference to a B<NEW> matrix of the B<SAME SIZE> as
  1499. some_matrix; the contents of some_matrix have B<ALREADY BEEN COPIED>
  1500. to the new matrix
  1501.  
  1502. =item *
  1503.  
  1504. B<Hint: method names all in lower case indicate a boolean return value!>
  1505.  
  1506. (Except for "C<new()>" and "C<new_from_string()>", of course!)
  1507.  
  1508. =back
  1509.  
  1510. Please refer to L<"OVERLOADED OPERATORS"> below for ways of using
  1511. overloaded operators instead of explicit method calls in order to
  1512. facilitate calculations with matrices!
  1513.  
  1514. =head1 DESCRIPTION
  1515.  
  1516. This class lets you dynamically create boolean matrices of arbitrary
  1517. size and perform all the basic operations for matrices on them, like
  1518.  
  1519. =over 4
  1520.  
  1521. =item -
  1522.  
  1523. setting or deleting elements,
  1524.  
  1525. =item -
  1526.  
  1527. testing wether a certain element is set,
  1528.  
  1529. =item -
  1530.  
  1531. computing the sum, difference, product, closure and complement of matrices,
  1532.  
  1533. (you can also compute the union, intersection, difference and exclusive-or
  1534. of the underlying bit vector)
  1535.  
  1536. =item -
  1537.  
  1538. copying matrices,
  1539.  
  1540. =item -
  1541.  
  1542. testing two matrices for equality or inclusion (subset relationship), and
  1543.  
  1544. =item -
  1545.  
  1546. computing the number of elements and the norm of a matrix.
  1547.  
  1548. =back
  1549.  
  1550. Please refer to L<"OVERLOADED OPERATORS"> below for ways of using
  1551. overloaded operators instead of explicit method calls in order to
  1552. facilitate calculations with matrices!
  1553.  
  1554. =head1 OVERLOADED OPERATORS
  1555.  
  1556. Calculations with matrices can not only be performed with explicit method
  1557. calls using this module, but also through "magical" overloaded arithmetic
  1558. and relational operators.
  1559.  
  1560. For instance, instead of writing
  1561.  
  1562.     $matrix1 = Math::MatrixBool->new($rows,$columns);
  1563.     $matrix2 = Math::MatrixBool->new($rows,$columns);
  1564.     $matrix3 = Math::MatrixBool->new($rows,$columns);
  1565.  
  1566.     [...]
  1567.  
  1568.     $matrix3->Multiplication($matrix1,$matrix2);
  1569.  
  1570. you can just say
  1571.  
  1572.     $matrix1 = Math::MatrixBool->new($rows,$columns);
  1573.     $matrix2 = Math::MatrixBool->new($rows,$columns);
  1574.  
  1575.     [...]
  1576.  
  1577.     $matrix3 = $matrix1 * $matrix2;
  1578.  
  1579. That's all!
  1580.  
  1581. Here is the list of all "magical" overloaded operators and their
  1582. semantics (meaning):
  1583.  
  1584. Unary operators: '-', '~', 'abs', testing, '!', '""'
  1585.  
  1586. Binary (arithmetic) operators: '+', '*', '|', '-', '&', '^'
  1587.  
  1588. Binary (relational) operators: '==', '!=', '<', '<=', '>', '>='
  1589.  
  1590. Binary (relational) operators: 'cmp', 'eq', 'ne', 'lt', 'le', 'gt', 'ge'
  1591.  
  1592. Note that both arguments to a binary operator from the list above must
  1593. be matrices; numbers or other types of data are not permitted as arguments
  1594. and will produce an error message.
  1595.  
  1596. =over 5
  1597.  
  1598. =item '-'
  1599.  
  1600. Unary Minus ( C<$matrix2 = -$matrix1;> )
  1601.  
  1602. Same as "Complement". See "Complement" below.
  1603.  
  1604. =item '~'
  1605.  
  1606. Complement ( C<$matrix2 = ~$matrix1;> )
  1607.  
  1608. The operator '~' (or unary '-') computes the complement of the given matrix.
  1609.  
  1610. =item abs
  1611.  
  1612. Absolute Value ( C<$no_of_elem = abs($matrix);> )
  1613.  
  1614. Here, the absolute value of a matrix has been defined as the number
  1615. of elements the given matrix contains. This is B<NOT> the same as the
  1616. "norm" of a matrix!
  1617.  
  1618. =item test
  1619.  
  1620. Boolean Test ( C<if ($matrix) { ... }> )
  1621.  
  1622. You can actually test a matrix as though it were a boolean value.
  1623.  
  1624. No special operator is needed for this; Perl automatically calls the
  1625. appropriate method in this package if "$matrix" is a blessed reference
  1626. to an object of the "Math::MatrixBool" class or one of its derived
  1627. classes.
  1628.  
  1629. This operation returns "true" (1) if the given matrix is not empty and
  1630. "false" ('') otherwise.
  1631.  
  1632. =item '!'
  1633.  
  1634. Negated Boolean Test ( C<if (! $matrix) { ... }> )
  1635.  
  1636. You can also perform a negated test on a matrix as though it were a boolean
  1637. value. For example:
  1638.  
  1639.     if (! $matrix) { ... }
  1640.  
  1641.     unless ($matrix) { ... }     #  internally, same as above!
  1642.  
  1643. This operation returns "true" (1) if the given matrix is empty and "false"
  1644. ('') otherwise.
  1645.  
  1646. =item '""""'
  1647.  
  1648. "Stringification" ( C<print "$matrix";> )
  1649.  
  1650. It is possible to get a string representation of a given matrix by just
  1651. putting the matrix object reference between double quotes.
  1652.  
  1653. Note that in general the string representation of a matrix will span over
  1654. multiple lines (i.e., the string which is generated contains "\n" characters,
  1655. one at the end of each row of the matrix).
  1656.  
  1657. Example:
  1658.  
  1659.     $matrix = new Math::MatrixBool(5,6);
  1660.     $matrix->One();
  1661.     print "$matrix";
  1662.  
  1663. This will print:
  1664.  
  1665.     [ 1 0 0 0 0 0 ]
  1666.     [ 0 1 0 0 0 0 ]
  1667.     [ 0 0 1 0 0 0 ]
  1668.     [ 0 0 0 1 0 0 ]
  1669.     [ 0 0 0 0 1 0 ]
  1670.  
  1671. =item '+'
  1672.  
  1673. Addition ( C<$matrix3 = $matrix1 + $matrix2;> )
  1674.  
  1675. The '+' operator calculates the sum of two matrices.
  1676.  
  1677. Examples:
  1678.  
  1679.     $all   =  $odd + $even;
  1680.  
  1681.     $all  +=  $odd;
  1682.     $all  +=  $even;
  1683.  
  1684. Note that the '++' operator will produce an error message if applied
  1685. to an object of this class because adding a number to a matrix makes
  1686. no sense.
  1687.  
  1688. =item '*'
  1689.  
  1690. Multiplication ( C<$matrix3 = $matrix1 * $matrix2;> )
  1691.  
  1692. The '*' operator calculates the matrix product of two matrices.
  1693.  
  1694. Examples:
  1695.  
  1696.     $test   =  $one * $one;
  1697.  
  1698.     $test  *=  $one;
  1699.     $test  *=  $test;
  1700.  
  1701. Note that you can use matrices of any size as long as their numbers of
  1702. rows and columns correspond in the following way (example):
  1703.  
  1704.         $matrix_3 = $matrix_1 * $matrix_2;
  1705.  
  1706.                           [ 2 2 ]
  1707.                           [ 2 2 ]
  1708.                           [ 2 2 ]
  1709.  
  1710.               [ 1 1 1 ]   [ 3 3 ]
  1711.               [ 1 1 1 ]   [ 3 3 ]
  1712.               [ 1 1 1 ]   [ 3 3 ]
  1713.               [ 1 1 1 ]   [ 3 3 ]
  1714.  
  1715. I.e., the number of columns of matrix #1 is the same as the number of
  1716. rows of matrix #2, and the number of rows and columns of the resulting
  1717. matrix #3 is determined by the number of rows of matrix #1 and the
  1718. number of columns of matrix #2, respectively.
  1719.  
  1720. This way you can also perform the multiplication of a matrix with a
  1721. vector, since a vector is just a degenerated matrix with several rows
  1722. but only one column, or just one row and several columns.
  1723.  
  1724. =item '|'
  1725.  
  1726. Union ( C<$matrix3 = $matrix1 | $matrix2;> )
  1727.  
  1728. The '|' operator is used to calculate the union of two matrices
  1729. (of corresponding elements).
  1730.  
  1731. Examples:
  1732.  
  1733.     $all   =  $odd | $even;
  1734.  
  1735.     $all  |=  $odd;
  1736.     $all  |=  $even;
  1737.  
  1738. =item '-'
  1739.  
  1740. Difference ( C<$matrix3 = $matrix1 - $matrix2;> )
  1741.  
  1742. The operator '-' calculates the (dotted) difference of two matrices, i.e.,
  1743.  
  1744.     0 - 0 == 0
  1745.     0 - 1 == 0
  1746.     1 - 0 == 1
  1747.     1 - 1 == 0
  1748.  
  1749. for each corresponding element.
  1750.  
  1751. Examples:
  1752.  
  1753.     $odd   =  $all  - $even;
  1754.  
  1755.     $all  -=  $even;
  1756.  
  1757. Note that the '--' operator will produce an error message if applied
  1758. to an object of this class because subtracting a number from a matrix
  1759. makes no sense.
  1760.  
  1761. =item '&'
  1762.  
  1763. Intersection ( C<$matrix3 = $matrix1 & $matrix2;> )
  1764.  
  1765. The '&' operator is used to calculate the intersection of two matrices
  1766. (of the corresponding elements).
  1767.  
  1768. Examples:
  1769.  
  1770.     $rest  =  $all & $even;
  1771.  
  1772.     $all  &=  $even;
  1773.  
  1774. =item '^'
  1775.  
  1776. ExclusiveOr ( C<$matrix3 = $matrix1 ^ $matrix2;> )
  1777.  
  1778. The '^' operator is used to calculate the exclusive-or of two matrices
  1779. (of their corresponding elements).
  1780.  
  1781. In fact this operation is identical with the addition of two matrices
  1782. in this case of a Boolean Algebra.
  1783.  
  1784. Examples:
  1785.  
  1786.     $odd   =  $all  ^ $even;
  1787.  
  1788.     $all  ^=  $even;
  1789.  
  1790. =item '=='
  1791.  
  1792. Test For Equality ( C<if ($matrix1 == $matrix2) { ... }> )
  1793.  
  1794. This operator tests two matrices for equality.
  1795.  
  1796. Note that B<without> operator overloading, C<( $matrix1 == $matrix2 )> would
  1797. test wether the two references B<pointed to> the B<same object>! (!)
  1798.  
  1799. B<With> operator overloading in effect, C<( $matrix1 == $matrix2 )> tests
  1800. wether the two matrix objects B<contain> exactly the B<same elements>!
  1801.  
  1802. =item '!='
  1803.  
  1804. Test For Non-Equality ( C<if ($matrix1 != $matrix2) { ... }> )
  1805.  
  1806. This operator tests wether two matrices are different.
  1807.  
  1808. Note again that this tests wether the B<contents> of the two matrices are
  1809. not the same, and B<not> wether the two B<references> are different!
  1810.  
  1811. =item 'E<lt>'
  1812.  
  1813. Test For True Subset ( C<if ($matrix1 E<lt> $matrix2) { ... }> )
  1814.  
  1815. This operator tests wether $matrix1 is a true subset of $matrix2, i.e.
  1816. wether the elements contained in $matrix1 are also contained in $matrix2,
  1817. but not all elements contained in $matrix2 are contained in $matrix1.
  1818.  
  1819. Example:
  1820.  
  1821.         [ 1 0 0 0 0 ]                       [ 1 0 0 0 1 ]
  1822.         [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
  1823.         [ 0 0 1 0 0 ]  is a true subset of  [ 0 0 1 0 0 ]
  1824.         [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
  1825.         [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]
  1826.  
  1827.         [ 1 0 0 0 0 ]                       [ 1 0 0 0 1 ]
  1828.         [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
  1829.    but  [ 0 0 1 0 0 ]   is not a subset of  [ 0 0 1 0 0 ]
  1830.         [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
  1831.         [ 1 0 0 0 1 ]                       [ 0 0 0 0 1 ]
  1832.  
  1833. (nor vice-versa!)
  1834.  
  1835.         [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]
  1836.         [ 0 1 0 0 0 ]                       [ 0 1 0 0 0 ]
  1837.    and  [ 0 0 1 0 0 ]     is a subset of    [ 0 0 1 0 0 ]
  1838.         [ 0 0 0 1 0 ]                       [ 0 0 0 1 0 ]
  1839.         [ 1 0 0 0 1 ]                       [ 1 0 0 0 1 ]
  1840.  
  1841. but not a true subset because the two matrices are identical.
  1842.  
  1843. =item 'E<lt>='
  1844.  
  1845. Test For Subset ( C<if ($matrix1 E<lt>= $matrix2) { ... }> )
  1846.  
  1847. This operator tests wether $matrix1 is a subset of $matrix2, i.e.
  1848. wether all elements contained in $matrix1 are also contained in $matrix2.
  1849.  
  1850. This also evaluates to "true" when the two matrices are the same.
  1851.  
  1852. =item 'E<gt>'
  1853.  
  1854. Test For True Superset ( C<if ($matrix1 E<gt> $matrix2) { ... }> )
  1855.  
  1856. This operator tests wether $matrix1 is a true superset of $matrix2, i.e.
  1857. wether all elements contained in $matrix2 are also contained in $matrix1,
  1858. but not all elements contained in $matrix1 are contained in $matrix2.
  1859.  
  1860. Note that C<($matrix1 E<gt> $matrix2)> is exactly the same as
  1861. C<($matrix2 E<lt> $matrix1)>.
  1862.  
  1863. =item 'E<gt>='
  1864.  
  1865. Test For Superset ( C<if ($matrix1 E<gt>= $matrix2) { ... }> )
  1866.  
  1867. This operator tests wether $matrix1 is a superset of $matrix2, i.e.
  1868. wether all elements contained in $matrix2 are also contained in $matrix1.
  1869.  
  1870. This also evaluates to "true" when the two matrices are equal.
  1871.  
  1872. Note that C<($matrix1 E<gt>= $matrix2)> is exactly the same as
  1873. C<($matrix2 E<lt>= $matrix1)>.
  1874.  
  1875. =item cmp
  1876.  
  1877. Compare ( C<$result = $matrix1 cmp $matrix2;> )
  1878.  
  1879. This operator compares the two matrices lexically, i.e. it regards the
  1880. two bit vectors representing the two matrices as two large (unsigned)
  1881. numbers in binary representation and returns "-1" if the number for
  1882. $matrix1 is smaller than that for $matrix2, "0" if the two numbers are
  1883. the same (i.e., when the two matrices are equal!) or "1" if the number
  1884. representing $matrix1 is larger than the number representing $matrix2.
  1885.  
  1886. Note that this comparison has nothing to do whatsoever with algebra,
  1887. it is just an B<arbitrary> order relationship!
  1888.  
  1889. It is only intended to provide an (arbitrary) order by which (for example)
  1890. an array of matrices can be sorted, for instance to find out quickly (using
  1891. binary search) if a specific matrix has already been produced before in some
  1892. matrix-producing process or not.
  1893.  
  1894. =item eq
  1895.  
  1896. "equal"
  1897.  
  1898. =item ne
  1899.  
  1900. "not equal"
  1901.  
  1902. =item lt
  1903.  
  1904. "less than"
  1905.  
  1906. =item le
  1907.  
  1908. "less than or equal"
  1909.  
  1910. =item gt
  1911.  
  1912. "greater than"
  1913.  
  1914. =item ge
  1915.  
  1916. "greater than or equal"
  1917.  
  1918. These are all operators derived from the "cmp" operator (see above).
  1919.  
  1920. They can be used instead of the "cmp" operator to make the intended
  1921. type of comparison more obvious in your code.
  1922.  
  1923. For instance, C<($matrix1 le $matrix2)> is much more readable and clearer
  1924. than C<(($matrix1 cmp $matrix2) E<lt>= 0)>!
  1925.  
  1926. =back
  1927.  
  1928. =head1 SEE ALSO
  1929.  
  1930. Bit::Vector(3), Math::MatrixReal(3), DFA::Kleene(3),
  1931. Math::Kleene(3), Set::IntegerFast(3), Set::IntegerRange(3).
  1932.  
  1933. =head1 VERSION
  1934.  
  1935. This man page documents "Math::MatrixBool" version 4.1.
  1936.  
  1937. =head1 AUTHOR
  1938.  
  1939. Steffen Beyer <sb@sdm.de>.
  1940.  
  1941. =head1 COPYRIGHT
  1942.  
  1943. Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.
  1944.  
  1945. =head1 LICENSE AGREEMENT
  1946.  
  1947. This package is free software; you can redistribute it and/or
  1948. modify it under the same terms as Perl itself.
  1949.  
  1950.