colamd.c File Reference
Common

Approximate minimum degree column ordering algorithm. More...

`#include <limits.h>`
`#include <math.h>`
`#include "colamd.h"`
`#include <stdio.h>`
Include dependency graph for colamd.c:

## Data Structures

struct | Colamd_Col_struct
struct | Colamd_Row_struct

## Macros

#define | NDEBUG
#define | NULL ((void *) 0)
#define | Int int
#define | ID "%d"
#define | Int_MAX INT_MAX
#define | COLAMD_recommended colamd_recommended
#define | COLAMD_set_defaults colamd_set_defaults
#define | COLAMD_MAIN colamd
#define | SYMAMD_MAIN symamd
#define | COLAMD_report colamd_report
#define | SYMAMD_report symamd_report
#define | PUBLIC
#define | PRIVATE static
#define | DENSE_DEGREE(alpha, n) ((Int) MAX (16.0, (alpha) * sqrt ((double) (n))))
#define | MAX(a, b) (((a) > (b)) ? (a) : (b))
#define | MIN(a, b) (((a) < (b)) ? (a) : (b))
#define | ONES_COMPLEMENT(r) (-(r)-1)
#define | TRUE (1)
#define | FALSE (0)
#define | EMPTY (-1)
#define | ALIVE (0)
#define | DEAD (-1)
#define | DEAD_PRINCIPAL (-1)
#define | DEAD_NON_PRINCIPAL (-2)
#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 ; }
#define | INDEX(i) (i)
#define | DEBUG0(params) ;
#define | DEBUG1(params) ;
#define | DEBUG2(params) ;
#define | DEBUG3(params) ;
#define | DEBUG4(params) ;
#define | ASSERT(expression)
#define | COLAMD_C(n_col, ok) ((t_mult (t_add (n_col, 1, ok), sizeof (Colamd_Col), ok) / sizeof (Int)))
#define | COLAMD_R(n_row, ok) ((t_mult (t_add (n_row, 1, ok), sizeof (Colamd_Row), ok) / sizeof (Int)))

## Typedefs

typedef struct Colamd_Col_struct | Colamd_Col
typedef struct Colamd_Row_struct | Colamd_Row

## Functions

PRIVATE Int | init_rows_cols (Int n_row, Int n_col, Colamd_Row Row[], Colamd_Col Col[], Int A[], Int p[], Int stats[COLAMD_STATS])
PRIVATE void | init_scoring (Int n_row, Int n_col, Colamd_Row Row[], Colamd_Col Col[], Int A[], Int head[], double knobs[COLAMD_KNOBS], Int *p_n_row2, Int *p_n_col2, Int *p_max_deg)
PRIVATE Int | find_ordering (Int n_row, Int n_col, Int Alen, Colamd_Row Row[], Colamd_Col Col[], Int A[], Int head[], Int n_col2, Int max_deg, Int pfree, Int aggressive)
PRIVATE void | order_children (Int n_col, Colamd_Col Col[], Int p[])
PRIVATE void | detect_super_cols (Colamd_Col Col[], Int A[], Int head[], Int row_start, Int row_length)
PRIVATE Int | garbage_collection (Int n_row, Int n_col, Colamd_Row Row[], Colamd_Col Col[], Int A[], Int *pfree)
PRIVATE Int | clear_mark (Int tag_mark, Int max_mark, Int n_row, Colamd_Row Row[])
PRIVATE void | print_report (char *method, Int stats[COLAMD_STATS])
static size_t | t_add (size_t a, size_t b, int *ok)
static size_t | t_mult (size_t a, size_t k, int *ok)
PUBLIC size_t | COLAMD_recommended (Int nnz, Int n_row, Int n_col)
PUBLIC void | COLAMD_set_defaults (double knobs[COLAMD_KNOBS])
PUBLIC Int | SYMAMD_MAIN (Int n, Int A[], Int p[], Int perm[], double knobs[COLAMD_KNOBS], Int stats[COLAMD_STATS], void *(*allocate)(size_t, size_t), void(*release)(void *))
PUBLIC Int | COLAMD_MAIN (Int n_row, Int n_col, Int Alen, Int A[], Int p[], double knobs[COLAMD_KNOBS], Int stats[COLAMD_STATS])
PUBLIC void | COLAMD_report (Int stats[COLAMD_STATS])
PUBLIC void | SYMAMD_report (Int stats[COLAMD_STATS])

## Macro Definition Documentation

## ALIVE

#define ALIVE (0)

## ASSERT

#define ASSERT | ( |  | expression | ) |

## COL_IS_ALIVE

#define COL_IS_ALIVE | ( |  | c | ) | (Col [c].start >= ALIVE)

## COL_IS_DEAD

#define COL_IS_DEAD | ( |  | c | ) | (Col [c].start < ALIVE)

## COL_IS_DEAD_PRINCIPAL

#define COL_IS_DEAD_PRINCIPAL | ( |  | c | ) | (Col [c].start == DEAD_PRINCIPAL)

## COLAMD_C

#define COLAMD_C | ( |  | n_col,
|  |  | ok
| ) |  | ((t_mult (t_add (n_col, 1, ok), sizeof (Colamd_Col), ok) / sizeof (Int)))

## COLAMD_MAIN

#define COLAMD_MAIN colamd

## COLAMD_R

#define COLAMD_R | ( |  | n_row,
|  |  | ok
| ) |  | ((t_mult (t_add (n_row, 1, ok), sizeof (Colamd_Row), ok) / sizeof (Int)))

## COLAMD_recommended

#define COLAMD_recommended colamd_recommended

## COLAMD_report

#define COLAMD_report colamd_report

## COLAMD_set_defaults

#define COLAMD_set_defaults colamd_set_defaults

## DEAD

#define DEAD (-1)

## DEAD_NON_PRINCIPAL

#define DEAD_NON_PRINCIPAL (-2)

## DEAD_PRINCIPAL

#define DEAD_PRINCIPAL (-1)

## DEBUG0

#define DEBUG0 | ( |  | params | ) | ;

## DEBUG1

#define DEBUG1 | ( |  | params | ) | ;

## DEBUG2

#define DEBUG2 | ( |  | params | ) | ;

## DEBUG3

#define DEBUG3 | ( |  | params | ) | ;

## DEBUG4

#define DEBUG4 | ( |  | params | ) | ;

## DENSE_DEGREE

#define DENSE_DEGREE | ( |  | alpha,
|  |  | n
| ) |  | ((Int) MAX (16.0, (alpha) * sqrt ((double) (n))))

## EMPTY

#define EMPTY (-1)

## FALSE

#define FALSE (0)

## ID

#define ID "%d"

## INDEX

#define INDEX | ( |  | i | ) | (i)

## Int

#define Int int

## Int_MAX

#define Int_MAX INT_MAX

## KILL_NON_PRINCIPAL_COL

#define KILL_NON_PRINCIPAL_COL | ( |  | c | ) | { Col [c].start = DEAD_NON_PRINCIPAL ; }

## KILL_PRINCIPAL_COL

#define KILL_PRINCIPAL_COL | ( |  | c | ) | { Col [c].start = DEAD_PRINCIPAL ; }

## KILL_ROW

#define KILL_ROW | ( |  | r | ) | { Row [r].shared2.mark = DEAD ; }

## MAX

#define MAX | ( |  | a,
|  |  | b
| ) |  | (((a) > (b)) ? (a) : (b))

## MIN

#define MIN | ( |  | a,
|  |  | b
| ) |  | (((a) < (b)) ? (a) : (b))

## NDEBUG

#define NDEBUG

## NULL

#define NULL ((void *) 0)

## ONES_COMPLEMENT

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

## PRIVATE

#define PRIVATE static

## PUBLIC

#define PUBLIC

## ROW_IS_ALIVE

#define ROW_IS_ALIVE | ( |  | r | ) | (Row [r].shared2.mark >= ALIVE)

## ROW_IS_DEAD

#define ROW_IS_DEAD | ( |  | r | ) | ROW_IS_MARKED_DEAD (Row[r].shared2.mark)

## ROW_IS_MARKED_DEAD

#define ROW_IS_MARKED_DEAD | ( |  | row_mark | ) | (row_mark < ALIVE)

## SYMAMD_MAIN

#define SYMAMD_MAIN symamd

## SYMAMD_report

#define SYMAMD_report symamd_report

## TRUE

#define TRUE (1)

## Typedef Documentation

## Colamd_Col

typedef struct Colamd_Col_struct Colamd_Col

## Colamd_Row

typedef struct Colamd_Row_struct Colamd_Row

## Function Documentation

## clear_mark()

PRIVATE Int clear_mark | ( | Int | tag_mark,
|  | Int | max_mark,
|  | Int | n_row,
|  | Colamd_Row | Row[]
| ) |  |

## COLAMD_MAIN()

PUBLIC Int COLAMD_MAIN | ( | Int | n_row,
|  | Int | n_col,
|  | Int | Alen,
|  | Int | A[],
|  | Int | p[],
|  | double | knobs[COLAMD_KNOBS],
|  | Int | stats[COLAMD_STATS]
| ) |  |

Here is the call graph for this function:

## COLAMD_recommended()

PUBLIC size_t COLAMD_recommended | ( | Int | nnz,
|  | Int | n_row,
|  | Int | n_col
| ) |  |

Here is the call graph for this function:

## COLAMD_report()

PUBLIC void COLAMD_report | ( | Int | stats[COLAMD_STATS] | ) |

Here is the call graph for this function:

## COLAMD_set_defaults()

PUBLIC void COLAMD_set_defaults | ( | double | knobs[COLAMD_KNOBS] | ) |

## detect_super_cols()

PRIVATE void detect_super_cols | ( | Colamd_Col | Col[],
|  | Int | A[],
|  | Int | head[],
|  | Int | row_start,
|  | Int | row_length
| ) |  |

## find_ordering()

PRIVATE Int find_ordering | ( | Int | n_row,
|  | Int | n_col,
|  | Int | Alen,
|  | Colamd_Row | Row[],
|  | Colamd_Col | Col[],
|  | Int | A[],
|  | Int | head[],
|  | Int | n_col2,
|  | Int | max_deg,
|  | Int | pfree,
|  | Int | aggressive
| ) |  |

Here is the call graph for this function:

## garbage_collection()

PRIVATE Int garbage_collection | ( | Int | n_row,
|  | Int | n_col,
|  | Colamd_Row | Row[],
|  | Colamd_Col | Col[],
|  | Int | A[],
|  | Int * | pfree
| ) |  |

## init_rows_cols()

PRIVATE Int init_rows_cols | ( | Int | n_row,
|  | Int | n_col,
|  | Colamd_Row | Row[],
|  | Colamd_Col | Col[],
|  | Int | A[],
|  | Int | p[],
|  | Int | stats[COLAMD_STATS]
| ) |  |

## init_scoring()

PRIVATE void init_scoring | ( | Int | n_row,
|  | Int | n_col,
|  | Colamd_Row | Row[],
|  | Colamd_Col | Col[],
|  | Int | A[],
|  | Int | head[],
|  | double | knobs[COLAMD_KNOBS],
|  | Int * | p_n_row2,
|  | Int * | p_n_col2,
|  | Int * | p_max_deg
| ) |  |

## order_children()

PRIVATE void order_children | ( | Int | n_col,
|  | Colamd_Col | Col[],
|  | Int | p[]
| ) |  |

## print_report()

PRIVATE void print_report | ( | char * | method,
|  | Int | stats[COLAMD_STATS]
| ) |  |

## SYMAMD_MAIN()

PUBLIC Int SYMAMD_MAIN | ( | Int | n,
|  | Int | A[],
|  | Int | p[],
|  | Int | perm[],
|  | double | knobs[COLAMD_KNOBS],
|  | Int | stats[COLAMD_STATS],
|  | void *(*)(size_t, size_t) | allocate,
|  | void(*)(void *) | release
| ) |  |

## SYMAMD_report()

PUBLIC void SYMAMD_report | ( | Int | stats[COLAMD_STATS] | ) |

Here is the call graph for this function:

## t_add()

static size_t t_add | ( | size_t | a,
|  | size_t | b,
|  | int * | ok
| ) |  |

static

## t_mult()

static size_t t_mult | ( | size_t | a,
|  | size_t | k,
|  | int * | ok
| ) |  |

static

Here is the call graph for this function: