colamd.c File Reference

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: