colamd.c File Reference

#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	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])

Detailed Description

Copyright (c) 2003, The Regents of the University of California, through Lawrence Berkeley National Laboratory (subject to receipt of any required approvals from U.S. Dept. of Energy)

All rights reserved.

The source code is distributed under BSD license, see the file License.txt at the top-level directory.

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_R

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

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)

INDEX

#define INDEX

(

i

)

(i)

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)

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_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
	)

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: