model_server/edge/src/matrix.cxx
/*
 * crossings
 * computes the number of crossings
 * algorithm:
 * matrix[i][j] represents the number of edges between position i on the upper
 * level and position j on the lower level, call it (i,j).
 * The edges crossing edge (i,j) from right to left are exactly those
 * edges (k,l) with k > i and l < j. You get the number of those edges
 * by adding all elements of the submatrix[k][l] with k > i and l < j.
 * The product of the elements of the submatrix and m[i][j] yields the 
 * number of crossings.
 * To compute all crossings you must iterate over all elements of the matrix.
 * This computation time is linear in the size of the matrix.
 */
crossings
computes the number of crossings
algorithm:
matrix[i][j] represents the number of edges between position i on the upper
level and position j on the lower level, call it (i,j).
The edges crossing edge (i,j) from right to left are exactly those
edges (k,l) with k > i and l < j. You get the number of those edges
by adding all elements of the submatrix[k][l] with k > i and l < j.
The product of the elements of the submatrix and m[i][j] yields the
number of crossings.
To compute all crossings you must iterate over all elements of the matrix.
This computation time is linear in the size of the matrix.
crossings computes the number of crossings algorithm : matrix [ i ] [ j ] represents the number of edges between position i on the upper level and position j on the lower level call it ( i j ) . The edges crossing edge ( i j ) from right to left are exactly those edges ( k l ) with k > i and l < j . You get the number of those edges by adding all elements of the submatrix [ k ] [ l ] with k > i and l < j . The product of the elements of the submatrix and m [ i ] [ j ] yields the number of crossings . To compute all crossings you must iterate over all elements of the matrix . This computation time is linear in the size of the matrix .
int 
matrix::crossings() 
{
  register int i , k , b , submatrix , s;
  s = 0;
  edge_vector subrow(rows);
  for (i=0; i<rows; i++) subrow[i] = 0;
  for (k=1; k<columns; k++) {
    subrow[rows-1] += m[rows-1][k-1];
    submatrix = subrow[rows-1];
    for (i=rows-2; i>=0; i--) {
      if (b = m[i][k]) {
	s += submatrix;
	if (--b) s += b * submatrix;
      }
      subrow[i] += m[i][k-1];
      submatrix += subrow[i];
    }
  }
  return s;
}
int matrix :: crossings ( ) { register int i , k , b , submatrix , s ; s = 0 ; edge_vector subrow ( rows ) ; for ( i = 0 ; i < rows ; i ++ ) subrow [ i ] = 0 ; for ( k = 1 ; k < columns ; k ++ ) { subrow [ rows - 1 ] += m [ rows - 1 ] [ k - 1 ] ; submatrix = subrow [ rows - 1 ] ; for ( i = rows - 2 ; i >= 0 ; i -- ) { if ( b = m [ i ] [ k ] ) { s += submatrix ; if ( -- b ) s += b * submatrix ; } subrow [ i ] += m [ i ] [ k - 1 ] ; submatrix += subrow [ i ] ; } } return s ; }
crossings
 computes the number of crossings
 algorithm:
 matrix[i][j] represents the number of edges between position i on the upper
 level and position j on the lower level, call it (i,j).
crossings computes the number of crossings algorithm : matrix [ i ] [ j ] represents the number of edges between position i on the upper level and position j on the lower level call it ( i j ) .