old_colamd.c File Reference

An approximate minimum degree column ordering algorithm. More...

#include <limits.h>
#include "colamd.h"
#include <assert.h>

Include dependency graph for old_colamd.c:

Classes
struct	ColInfo_struct
struct	RowInfo_struct

Macros
#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	PUBLIC
#define	PRIVATE   static
#define	DEBUG0(params)   ;
#define	DEBUG1(params)   ;
#define	DEBUG2(params)   ;
#define	DEBUG3(params)   ;
#define	DEBUG4(params)   ;

Typedefs
typedef struct ColInfo_struct	ColInfo
typedef struct RowInfo_struct	RowInfo

Functions
PRIVATE int	init_rows_cols (int n_row, int n_col, RowInfo Row[], ColInfo Col[], int A[], int p[])
PRIVATE void	init_scoring (int n_row, int n_col, RowInfo Row[], ColInfo 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, RowInfo Row[], ColInfo Col[], int A[], int head[], int n_col2, int max_deg, int pfree)
PRIVATE void	order_children (int n_col, ColInfo Col[], int p[])
PRIVATE void	detect_super_cols (ColInfo Col[], int A[], int head[], int row_start, int row_length)
PRIVATE int	garbage_collection (int n_row, int n_col, RowInfo Row[], ColInfo Col[], int A[], int *pfree)
PRIVATE int	clear_mark (int n_row, RowInfo Row[])
PUBLIC int	colamd_recommended (int nnz, int n_row, int n_col)
PUBLIC void	colamd_set_defaults (double knobs[COLAMD_KNOBS])
PUBLIC int	colamd (int n_row, int n_col, int Alen, int A[], int p[], double knobs[COLAMD_KNOBS])

Detailed Description

An approximate minimum degree column ordering algorithm.

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)

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)

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

)

;

EMPTY

#define EMPTY   (-1)

FALSE

#define FALSE   (0)

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

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

ColInfo

typedef struct ColInfo_struct ColInfo

RowInfo

typedef struct RowInfo_struct RowInfo

Function Documentation

clear_mark()

PRIVATE int clear_mark	(	int	n_row,
		RowInfo	Row[]
	)

colamd()

PUBLIC int colamd	(	int	n_row,
		int	n_col,
		int	Alen,
		int	A[],
		int	p[],
		double	knobs[COLAMD_KNOBS]
	)

Here is the call graph for this function:

colamd_recommended()

PUBLIC int colamd_recommended	(	int	nnz,
		int	n_row,
		int	n_col
	)

colamd_set_defaults()

PUBLIC void colamd_set_defaults

(

double

knobs[COLAMD_KNOBS]

)

detect_super_cols()

PRIVATE void detect_super_cols	(	ColInfo	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,
		RowInfo	Row[],
		ColInfo	Col[],
		int	A[],
		int	head[],
		int	n_col2,
		int	max_deg,
		int	pfree
	)

Here is the call graph for this function:

garbage_collection()

PRIVATE int garbage_collection	(	int	n_row,
		int	n_col,
		RowInfo	Row[],
		ColInfo	Col[],
		int	A[],
		int *	pfree
	)

init_rows_cols()

PRIVATE int init_rows_cols	(	int	n_row,
		int	n_col,
		RowInfo	Row[],
		ColInfo	Col[],
		int	A[],
		int	p[]
	)

init_scoring()

PRIVATE void init_scoring	(	int	n_row,
		int	n_col,
		RowInfo	Row[],
		ColInfo	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,
		ColInfo	Col[],
		int	p[]
	)