[Summary view] [Print] [Text view]

   1  <?php
   2  /**
   3   * File containing the abstract ezcGraphMatrix class
   4   *
   5   * @package Graph
   6   * @version 1.5
   7   * @copyright Copyright (C) 2005-2009 eZ Systems AS. All rights reserved.
   8   * @license http://ez.no/licenses/new_bsd New BSD License
   9   * @access private
  10   */
  11  /**
  12   * Provides a genereic matrix class with basic math operations
  13   * 
  14   * The matrix class is used for internal matrix calculations, and it should not
  15   * be required to be used by end users. It offers the common arithmetics
  16   * operations, and a __toString mechanism for debugging.
  17   * 
  18   * Beside this it implements more complex matrix algorithms to solve non linear
  19   * equatations using the Gauss-Newton algorithm and LR decomposition using the
  20   * Cholesky-Crout algorithm. These algorithms are required by the average
  21   * polynom calculation in the ezcGraphDataSetAveragePolynom class.
  22   *
  23   * @version 1.5
  24   * @package Graph
  25   * @access private
  26   */
  27  class ezcGraphMatrix
  28  {
  29  
  30      /**
  31       * Count of matrix rows
  32       * 
  33       * @var int
  34       */
  35      protected $rows;
  36  
  37      /**
  38       * Count of matrix columns
  39       * 
  40       * @var int
  41       */
  42      protected $columns;
  43  
  44      /**
  45       * Array containing matrix values.
  46       *
  47       * // Matrix
  48       *  array(
  49       *      // Rows
  50       *      array(
  51       *          // Column values
  52       *          (float)
  53       *      )
  54       *  )
  55       * 
  56       * @var array(array(float))
  57       */
  58      protected $matrix;
  59  
  60      /**
  61       * Constructor
  62       *
  63       * Creates a matrix with given dimensions. Optionally accepts an array to 
  64       * define the initial matrix values. If no array is given an identity 
  65       * matrix is created.
  66       * 
  67       * @param int $rows Number of rows
  68       * @param int $columns Number of columns
  69       * @param array $values Array with values
  70       * @return void
  71       */
  72      public function __construct( $rows = 3, $columns = 3, array $values = null )
  73      {
  74          $this->rows = max( 1, (int) $rows );
  75          $this->columns = max( 1, (int) $columns );
  76  
  77          if ( $values !== null )
  78          {
  79              $this->fromArray( $values );
  80          }
  81          else
  82          {
  83              $this->init();
  84          }
  85      }
  86  
  87      /**
  88       * Create matrix from array
  89       *
  90       * Use an array with float values to set matrix values.
  91       * 
  92       * @param array $values Array with values
  93       * @return ezcGraphMatrix Modified matrix
  94       */
  95      public function fromArray( array $values )
  96      {
  97          for ( $i = 0; $i < $this->rows; ++$i )
  98          {
  99              for ( $j = 0; $j < $this->columns; ++$j )
 100              {
 101                  $this->matrix[$i][$j] =
 102                      ( isset( $values[$i][$j] )
 103                      ? (float) $values[$i][$j]
 104                      : 0 );
 105              }
 106          }
 107  
 108          return $this;
 109      }
 110  
 111      /**
 112       * Init matrix
 113       *
 114       * Sets matrix to identity matrix.
 115       * 
 116       * @return ezcGraphMatrix Modified matrix
 117       */
 118      public function init()
 119      {
 120          for ( $i = 0; $i < $this->rows; ++$i )
 121          {
 122              for ( $j = 0; $j < $this->columns; ++$j )
 123              {
 124                  $this->matrix[$i][$j] = ( $i === $j ? 1 : 0 );
 125              }
 126          }
 127  
 128          return $this;
 129      }
 130  
 131      /**
 132       * Returns number of rows
 133       * 
 134       * @return int Number of rows
 135       */
 136      public function rows()
 137      {
 138          return $this->rows;
 139      }
 140  
 141      /**
 142       * Returns number of columns 
 143       * 
 144       * @return int Number of columns
 145       */
 146      public function columns()
 147      {
 148          return $this->columns;
 149      }
 150  
 151      /**
 152       * Get a single matrix value
 153       *
 154       * Returns the value of the matrix at the given position
 155       * 
 156       * @param int $i Column
 157       * @param int $j Row
 158       * @return float Matrix value
 159       */
 160      public function get( $i, $j )
 161      {
 162          if ( ( $i < 0 ) ||
 163               ( $i >= $this->rows ) ||
 164               ( $j < 0 ) ||
 165               ( $j >= $this->columns ) )
 166          {
 167              throw new ezcGraphMatrixOutOfBoundingsException( $this->rows, $this->columns, $i, $j );
 168          }
 169  
 170          return ( !isset( $this->matrix[$i][$j] ) ? .0 : $this->matrix[$i][$j] );
 171      }
 172  
 173      /**
 174       * Set a single matrix value
 175       *
 176       * Sets the value of the matrix at the given position.
 177       * 
 178       * @param int $i Column
 179       * @param int $j Row
 180       * @param float $value Value
 181       * @return ezcGraphMatrix Updated matrix
 182       */
 183      public function set( $i, $j, $value )
 184      {
 185          if ( ( $i < 0 ) ||
 186               ( $i >= $this->rows ) ||
 187               ( $j < 0 ) ||
 188               ( $j >= $this->columns ) )
 189          {
 190              throw new ezcGraphMatrixOutOfBoundingsException( $this->rows, $this->columns, $i, $j );
 191          }
 192  
 193          $this->matrix[$i][$j] = $value;
 194  
 195          return $this;
 196      }
 197  
 198      /**
 199       * Adds one matrix to the current one
 200       *
 201       * Calculate the sum of two matrices and returns the resulting matrix.
 202       * 
 203       * @param ezcGraphMatrix $matrix Matrix to sum with
 204       * @return ezcGraphMatrix Result matrix
 205       */
 206      public function add( ezcGraphMatrix $matrix )
 207      {
 208          if ( ( $this->rows !== $matrix->rows() ) ||
 209               ( $this->columns !== $matrix->columns() ) )
 210          {
 211              throw new ezcGraphMatrixInvalidDimensionsException( $this->rows, $this->columns, $matrix->rows(), $matrix->columns() );
 212          }
 213  
 214          for ( $i = 0; $i < $this->rows; ++$i )
 215          {
 216              for ( $j = 0; $j < $this->columns; ++$j )
 217              {
 218                  $this->matrix[$i][$j] += $matrix->get( $i, $j );
 219              }
 220          }
 221  
 222          return $this;
 223      }
 224  
 225      /**
 226       * Subtracts matrix from current one
 227       *
 228       * Calculate the diffenrence of two matices and returns the result matrix.
 229       * 
 230       * @param ezcGraphMatrix $matrix subtrahend
 231       * @return ezcGraphMatrix Result matrix
 232       */
 233      public function diff( ezcGraphMatrix $matrix )
 234      {
 235          if ( ( $this->rows !== $matrix->rows() ) ||
 236               ( $this->columns !== $matrix->columns() ) )
 237          {
 238              throw new ezcGraphMatrixInvalidDimensionsException( $this->rows, $this->columns, $matrix->rows(), $matrix->columns() );
 239          }
 240  
 241          for ( $i = 0; $i < $this->rows; ++$i )
 242          {
 243              for ( $j = 0; $j < $this->columns; ++$j )
 244              {
 245                  $this->matrix[$i][$j] -= $matrix->get( $i, $j );
 246              }
 247          }
 248  
 249          return $this;
 250      }
 251  
 252      /**
 253       * Scalar multiplication
 254       *
 255       * Multiplies matrix with the given scalar and returns the result matrix
 256       * 
 257       * @param float $scalar Scalar
 258       * @return ezcGraphMatrix Result matrix
 259       */
 260      public function scalar( $scalar )
 261      {
 262          $scalar = (float) $scalar;
 263  
 264          for ( $i = 0; $i < $this->rows; ++$i )
 265          {
 266              for ( $j = 0; $j < $this->columns; ++$j )
 267              {
 268                  $this->matrix[$i][$j] *= $scalar;
 269              }
 270          }
 271      }
 272  
 273      /**
 274       * Transpose matrix
 275       * 
 276       * @return ezcGraphMatrix Transposed matrix
 277       */
 278      public function transpose()
 279      {
 280          $matrix = clone $this;
 281  
 282          $this->rows = $matrix->columns();
 283          $this->columns = $matrix->rows();
 284  
 285          $this->matrix = array();
 286  
 287          for ( $i = 0; $i < $this->rows; ++$i )
 288          {
 289              for ( $j = 0; $j < $this->columns; ++$j )
 290              {
 291                  $this->matrix[$i][$j] = $matrix->get( $j, $i );
 292              }
 293          }
 294  
 295          return $this;
 296      }
 297  
 298      /**
 299       * Multiplies two matrices
 300       *
 301       * Multiply current matrix with another matrix and returns the result 
 302       * matrix.
 303       *
 304       * @param ezcGraphMatrix $matrix Second factor
 305       * @return ezcGraphMatrix Result matrix
 306       */
 307      public function multiply( ezcGraphMatrix $matrix ) 
 308      {
 309          $mColumns = $matrix->columns();
 310          if ( $this->columns !== ( $mRows = $matrix->rows() ) ) 
 311          {
 312              throw new ezcGraphMatrixInvalidDimensionsException( $this->columns, $this->rows, $mColumns, $mRows );
 313          }
 314  
 315          $result = new ezcGraphMatrix( $this->rows, $mColumns );
 316  
 317          for ( $i = 0; $i < $this->rows; ++$i ) 
 318          {
 319              for ( $j = 0; $j < $mColumns; ++$j ) 
 320              {
 321                  $sum = 0;
 322                  for ( $k = 0; $k < $mRows; ++$k ) {
 323                      $sum += $this->matrix[$i][$k] * $matrix->get( $k, $j );
 324                  }
 325  
 326                  $result->set( $i, $j, $sum );
 327              }
 328          }
 329  
 330          return $result;
 331      }
 332  
 333      /**
 334       * Solve nonlinear equatation
 335       * 
 336       * Tries to solve equatation given by two matrices, with assumption, that:
 337       *      A * x = B
 338       * where $this is A, and the paramenter B. x is cosnidered as a vector
 339       * x = ( x^n, x^(n-1), ..., x^2, x, 1 )
 340       *
 341       * Will return a polynomial solution for x.
 342       *
 343       * See: http://en.wikipedia.org/wiki/Gauss-Newton_algorithm
 344       *
 345       * @param ezcGraphMatrix $matrix B
 346       * @return ezcGraphPolygon Solution of equatation
 347       */
 348      public function solveNonlinearEquatation( ezcGraphMatrix $matrix )
 349      {
 350          // Build complete equatation
 351          $equatation = new ezcGraphMatrix( $this->rows, $columns = ( $this->columns + 1 ) );
 352  
 353          for ( $i = 0; $i < $this->rows; ++$i ) 
 354          {
 355              for ( $j = 0; $j < $this->columns; ++$j ) 
 356              {
 357                  $equatation->set( $i, $j, $this->matrix[$i][$j] );
 358              }
 359              $equatation->set( $i, $this->columns, $matrix->get( $i, 0 ) );
 360          }
 361  
 362          // Compute upper triangular matrix on left side of equatation
 363          for ( $i = 0; $i < ( $this->rows - 1 ); ++$i ) 
 364          {
 365              for ( $j = $i + 1; $j < $this->rows; ++$j ) 
 366              {
 367                  if ( $equatation->get( $j, $i ) !== 0 )
 368                  {
 369                      if ( $equatation->get( $j, $i ) == 0 )
 370                      {
 371                          continue;
 372                      }
 373                      else
 374                      {
 375                          $factor = -( $equatation->get( $i, $i ) / $equatation->get( $j, $i ) );
 376                      }
 377  
 378                      for ( $k = $i; $k < $columns; ++$k )
 379                      {
 380                          $equatation->set( $j, $k, $equatation->get( $i, $k ) + $factor * $equatation->get( $j, $k ) );
 381                      }
 382                  }
 383              }
 384          }
 385  
 386          // Normalize values on left side matrix diagonale
 387          for ( $i = 0; $i < $this->rows; ++$i ) 
 388          {
 389              if ( ( ( $value = $equatation->get( $i, $i ) ) != 1 ) &&
 390                   ( $value != 0 ) )
 391              {
 392                  $factor = 1 / $value;
 393                  for ( $k = $i; $k < $columns; ++$k )
 394                  {
 395                      $equatation->set( $i, $k, $equatation->get( $i, $k ) * $factor );
 396                  }
 397              }
 398          }
 399  
 400          // Build up solving polynom
 401          $polynom = new ezcGraphPolynom();
 402          for ( $i = ( $this->rows - 1 ); $i >= 0; --$i )
 403          {
 404              for ( $j = $i + 1; $j < $this->columns; ++$j )
 405              {
 406                  $equatation->set(
 407                      $i, 
 408                      $this->columns, 
 409                      $equatation->get( $i, $this->columns ) + ( -$equatation->get( $i, $j ) * $polynom->get( $j ) )
 410                  );
 411                  $equatation->set( $i, $j, 0 );
 412              }
 413              $polynom->set( $i, $equatation->get( $i, $this->columns ) );
 414          }
 415  
 416          return $polynom;
 417      }
 418  
 419      /**
 420       * Build LR decomposition from matrix
 421       *
 422       * Use Cholesky-Crout algorithm to get LR decomposition of the current 
 423       * matrix.
 424       *
 425       * Will return an array with two matrices:
 426       *  array(
 427       *      'l' => (ezcGraphMatrix) $left,
 428       *      'r' => (ezcGraphMatrix) $right,
 429       *  )
 430       * 
 431       * @return array( ezcGraphMatrix )
 432       */
 433      public function LRdecomposition()
 434      {
 435          /**
 436           * Use Cholesky-Crout algorithm to get LR decomposition
 437           *
 438           *  Input: Matrix A ($this)
 439           *  
 440           *  For i = 1 To n
 441           *      For j = i To n
 442           *          R(i,j)=A(i,j)             
 443           *          For k = 1 TO i-1               
 444           *              R(i,j)-=L(i,k)*R(k,j)
 445           *          end
 446           *      end    
 447           *      For j=i+1 To n
 448           *          L(j,i)= A(j,i)
 449           *          For k = 1 TO i-1
 450           *              L(j,i)-=L(j,k)*R(k,i)
 451           *          end
 452           *          L(j,i)/=R(i,i)
 453           *      end
 454           *  end
 455           *  
 456           *  Output: matrices L,R
 457           */
 458          $l = new ezcGraphMatrix( $this->columns, $this->rows );
 459          $r = new ezcGraphMatrix( $this->columns, $this->rows );
 460  
 461          for ( $i = 0; $i < $this->columns; ++$i ) 
 462          {
 463              for ( $j = $i; $j < $this->rows; ++$j ) 
 464              {
 465                  $r->set( $i, $j, $this->matrix[$i][$j] );
 466                  for ( $k = 0; $k <= ( $i - 1 ); ++$k )
 467                  {
 468                      $r->set( $i, $j, $r->get( $i, $j ) - $l->get( $i, $k ) * $r->get( $k, $j ) );
 469                  }
 470              }
 471  
 472              for ( $j = $i + 1; $j < $this->rows; ++$j ) 
 473              {
 474                  $l->set( $j, $i, $this->matrix[$j][$i] );
 475                  for ( $k = 0; $k <= ( $i - 1 ); ++$k )
 476                  {
 477                      $l->set( $j, $i, $l->get( $j, $i ) - $l->get( $j, $k ) * $r->get( $k, $i ) );
 478                  }
 479                  $l->set( $j, $i, $l->get( $j, $i ) / $r->get( $i, $i ) );
 480              }
 481          }
 482  
 483          return array( 
 484              'l' => $l, 
 485              'r' => $r,
 486          );
 487      }
 488  
 489      /**
 490       * Returns a string representation of the matrix
 491       * 
 492       * @return string
 493       */
 494      public function __toString()
 495      {
 496          $string = sprintf( "%d x %d matrix:\n", $this->rows, $this->columns );
 497  
 498          for ( $i = 0; $i < $this->rows; ++$i ) 
 499          {
 500              $string .= '| ';
 501              for ( $j = 0; $j < $this->columns; ++$j ) 
 502              {
 503                  $string .= sprintf( '%04.2f ', $this->get( $i, $j ) );
 504              }
 505              $string .= "|\n";
 506          }
 507  
 508          return $string;
 509      }
 510  }
 511  ?>