Eigen_Colamd.h

// // This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2012 Desire Nuentsa Wakam <desire.nuentsa_wakam@inria.fr>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

// This file is modified from the colamd/symamd library. The copyright is below

//   The authors of the code itself are Stefan I. Larimore and Timothy A.
//   Davis (davis@cise.ufl.edu), University of Florida.  The algorithm was
//   developed in collaboration with John Gilbert, Xerox PARC, and Esmond
//   Ng, Oak Ridge National Laboratory.
// 
//     Date:
// 
//   September 8, 2003.  Version 2.3.
// 
//     Acknowledgements:
// 
//   This work was supported by the National Science Foundation, under
//   grants DMS-9504974 and DMS-9803599.
// 
//     Notice:
// 
//   Copyright (c) 1998-2003 by the University of Florida.
//   All Rights Reserved.
// 
//   THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
//   EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
// 
//   Permission is hereby granted to use, copy, modify, and/or distribute
//   this program, provided that the Copyright, this License, and the
//   Availability of the original version is retained on all copies and made
//   accessible to the end-user of any code or package that includes COLAMD
//   or any modified version of COLAMD. 
// 
//     Availability:
// 
//   The colamd/symamd library is available at
// 
//       http://www.suitesparse.com

  
#ifndef EIGEN_COLAMD_H
#define EIGEN_COLAMD_H

namespace internal {
/* Ensure that debugging is turned off: */
#ifndef COLAMD_NDEBUG
#define COLAMD_NDEBUG
#endif /* NDEBUG */
/* ========================================================================== */
/* === Knob and statistics definitions ====================================== */
/* ========================================================================== */

/* size of the knobs [ ] array.  Only knobs [0..1] are currently used. */
#define COLAMD_KNOBS 20

/* number of output statistics.  Only stats [0..6] are currently used. */
#define COLAMD_STATS 20 

/* knobs [0] and stats [0]: dense row knob and output statistic. */
#define COLAMD_DENSE_ROW 0

/* knobs [1] and stats [1]: dense column knob and output statistic. */
#define COLAMD_DENSE_COL 1

/* stats [2]: memory defragmentation count output statistic */
#define COLAMD_DEFRAG_COUNT 2

/* stats [3]: colamd status:  zero OK, > 0 warning or notice, < 0 error */
#define COLAMD_STATUS 3

/* stats [4..6]: error info, or info on jumbled columns */ 
#define COLAMD_INFO1 4
#define COLAMD_INFO2 5
#define COLAMD_INFO3 6

/* error codes returned in stats [3]: */
#define COLAMD_OK       (0)
#define COLAMD_OK_BUT_JUMBLED     (1)
#define COLAMD_ERROR_A_not_present    (-1)
#define COLAMD_ERROR_p_not_present    (-2)
#define COLAMD_ERROR_nrow_negative    (-3)
#define COLAMD_ERROR_ncol_negative    (-4)
#define COLAMD_ERROR_nnz_negative   (-5)
#define COLAMD_ERROR_p0_nonzero     (-6)
#define COLAMD_ERROR_A_too_small    (-7)
#define COLAMD_ERROR_col_length_negative  (-8)
#define COLAMD_ERROR_row_index_out_of_bounds  (-9)
#define COLAMD_ERROR_out_of_memory    (-10)
#define COLAMD_ERROR_internal_error   (-999)

/* ========================================================================== */
/* === Definitions ========================================================== */
/* ========================================================================== */

#define ONES_COMPLEMENT(r) (-(r)-1)

/* -------------------------------------------------------------------------- */

#define COLAMD_EMPTY (-1)

/* Row and column status */
#define ALIVE (0)
#define DEAD  (-1)

/* Column status */
#define DEAD_PRINCIPAL    (-1)
#define DEAD_NON_PRINCIPAL  (-2)

/* Macros for row and column status update and checking. */
#define ROW_IS_DEAD(r)      ROW_IS_MARKED_DEAD (Row[r].shared2.mark)
#define ROW_IS_MARKED_DEAD(row_mark)  (row_mark < ALIVE)
#define ROW_IS_ALIVE(r)     (Row [r].shared2.mark >= ALIVE)
#define COL_IS_DEAD(c)      (Col [c].start < ALIVE)
#define COL_IS_ALIVE(c)     (Col [c].start >= ALIVE)
#define COL_IS_DEAD_PRINCIPAL(c)  (Col [c].start == DEAD_PRINCIPAL)
#define KILL_ROW(r)     { Row [r].shared2.mark = DEAD ; }
#define KILL_PRINCIPAL_COL(c)   { Col [c].start = DEAD_PRINCIPAL ; }
#define KILL_NON_PRINCIPAL_COL(c) { Col [c].start = DEAD_NON_PRINCIPAL ; }

/* ========================================================================== */
/* === Colamd reporting mechanism =========================================== */
/* ========================================================================== */

// == Row and Column structures ==
template <typename Index>
struct colamd_col
{
  Index start ;   /* index for A of first row in this column, or DEAD */
  /* if column is dead */
  Index length ;  /* number of rows in this column */
  union
  {
    Index thickness ; /* number of original columns represented by this */
    /* col, if the column is alive */
    Index parent ;  /* parent in parent tree super-column structure, if */
    /* the column is dead */
  } shared1 ;
  union
  {
    Index score ; /* the score used to maintain heap, if col is alive */
    Index order ; /* pivot ordering of this column, if col is dead */
  } shared2 ;
  union
  {
    Index headhash ;  /* head of a hash bucket, if col is at the head of */
    /* a degree list */
    Index hash ;  /* hash value, if col is not in a degree list */
    Index prev ;  /* previous column in degree list, if col is in a */
    /* degree list (but not at the head of a degree list) */
  } shared3 ;
  union
  {
    Index degree_next ; /* next column, if col is in a degree list */
    Index hash_next ;   /* next column, if col is in a hash list */
  } shared4 ;
  
};
 
template <typename Index>
struct Colamd_Row
{
  Index start ;   /* index for A of first col in this row */
  Index length ;  /* number of principal columns in this row */
  union
  {
    Index degree ;  /* number of principal & non-principal columns in row */
    Index p ;   /* used as a row pointer in init_rows_cols () */
  } shared1 ;
  union
  {
    Index mark ;  /* for computing set differences and marking dead rows*/
    Index first_column ;/* first column in row (used in garbage collection) */
  } shared2 ;
  
};
 
/* ========================================================================== */
/* === Colamd recommended memory size ======================================= */
/* ========================================================================== */
 
/*
  The recommended length Alen of the array A passed to colamd is given by
  the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro.  It returns -1 if any
  argument is negative.  2*nnz space is required for the row and column
  indices of the matrix. colamd_c (n_col) + colamd_r (n_row) space is
  required for the Col and Row arrays, respectively, which are internal to
  colamd.  An additional n_col space is the minimal amount of "elbow room",
  and nnz/5 more space is recommended for run time efficiency.
  
  This macro is not needed when using symamd.
  
  Explicit typecast to Index added Sept. 23, 2002, COLAMD version 2.2, to avoid
  gcc -pedantic warning messages.
*/