SRC/etree.c File Reference

Elimination tree computation and layout routines. More...

#include <stdio.h>
#include <stdlib.h>
#include "superlu_ddefs.h"

Functions
static int_t *	mxCallocInt (int_t n)
static void	initialize_disjoint_sets (int_t n, int_t **pp)
static int_t	make_set (int_t i, int_t *pp)
static int_t	link (int_t s, int_t t, int_t *pp)
static int_t	find (int_t i, int_t *pp)
static void	finalize_disjoint_sets (int_t *pp)
int_t	sp_symetree_dist (int_t *acolst, int_t *acolend, int_t *arow, int_t n, int_t *parent)
	Symmetric elimination tree.
int_t	sp_coletree_dist (int_t *acolst, int_t *acolend, int_t *arow, int_t nr, int_t nc, int_t *parent)
	Nonsymmetric elimination tree.
static void	etdfs (int_t v, int_t first_kid[], int_t next_kid[], int_t post[], int_t *postnum)
static void	nr_etdfs (int_t n, int_t *parent, int_t *first_kid, int_t *next_kid, int_t *post, int_t postnum)
int_t *	TreePostorder_dist (int_t n, int_t *parent)
Variables
static int_t *	first_kid
	Depth-first search from vertext.
static int_t *	next_kid
static int_t *	post
static int_t	postnum

---

Detailed Description

  Implementation of disjoint set union routines.
  Elements are integers in 0..n-1, and the 
  names of the sets themselves are of type int.

  Calls are:
  initialize_disjoint_sets (n) initial call.
  s = make_set (i)             returns a set containing only i.
  s = link (t, u)		 returns s = t union u, destroying t and u.
  s = find (i)		 return name of set containing i.
  finalize_disjoint_sets 	 final call.

  This implementation uses path compression but not weighted union.
  See Tarjan's book for details.
  John Gilbert, CMI, 1987.

  Implemented path-halving by XL 7/5/95.
 

---

Function Documentation

static void etdfs	(	int_t	v,
		int_t	first_kid[],
		int_t	next_kid[],
		int_t	post[],
		int_t *	postnum
	)			[static]

static void finalize_disjoint_sets

(

int_t *

pp

)

[static]

static int_t find	(	int_t	i,
		int_t *	pp
	)			[static]

static void initialize_disjoint_sets	(	int_t	n,
		int_t **	pp
	)			[static]

static int_t link	(	int_t	s,
		int_t	t,
		int_t *	pp
	)			[static]

static int_t make_set	(	int_t	i,
		int_t *	pp
	)			[static]

static int_t* mxCallocInt

(

int_t

n

)

[static]

static void nr_etdfs	(	int_t	n,
		int_t *	parent,
		int_t *	first_kid,
		int_t *	next_kid,
		int_t *	post,
		int_t	postnum
	)			[static]

int_t sp_coletree_dist	(	int_t *	acolst,
		int_t *	acolend,
		int_t *	arow,
		int_t	nr,
		int_t	nc,
		int_t *	parent
	)

      Find the elimination tree for A'*A.
      This uses something similar to Liu's algorithm. 
      It runs in time O(nz(A)*log n) and does not form A'*A.

      Input:
        Sparse matrix A.  Numeric values are ignored, so any
        explicit zeros are treated as nonzero.
      Output:
        Integer array of parents representing the elimination
        tree of the symbolic product A'*A.  Each vertex is a
        column of A, and nc means a root of the elimination forest.

      John R. Gilbert, Xerox, 10 Dec 1990
      Based on code by JRG dated 1987, 1988, and 1990.
 

int_t sp_symetree_dist	(	int_t *	acolst,
		int_t *	acolend,
		int_t *	arow,
		int_t	n,
		int_t *	parent
	)

      p = spsymetree (A);

      Find the elimination tree for symmetric matrix A.
      This uses Liu's algorithm, and runs in time O(nz*log n).

      Input:
        Square sparse matrix A.  No check is made for symmetry;
        elements below and on the diagonal are ignored.
        Numeric values are ignored, so any explicit zeros are 
        treated as nonzero.
      Output:
        Integer array of parents representing the etree, with n
        meaning a root of the elimination forest.
      Note:  
        This routine uses only the upper triangle, while sparse
        Cholesky (as in spchol.c) uses only the lower.  Matlab's
        dense Cholesky uses only the upper.  This routine could
        be modified to use the lower triangle either by transposing
        the matrix or by traversing it by rows with auxiliary
        pointer and link arrays.

      John R. Gilbert, Xerox, 10 Dec 1990
      Based on code by JRG dated 1987, 1988, and 1990.
      Modified by X.S. Li, November 1999.
 

int_t* TreePostorder_dist	(	int_t	n,
		int_t *	parent
	)

---

Variable Documentation

int_t* first_kid [static]

  q = TreePostorder_dist (n, p);

	Postorder a tree.
	Input:
	  p is a vector of parent pointers for a forest whose
        vertices are the integers 0 to n-1; p[root]==n.
	Output:
	  q is a vector indexed by 0..n-1 such that q[i] is the
	  i-th vertex in a postorder numbering of the tree.

        ( 2/7/95 modified by X.Li:
          q is a vector indexed by 0:n-1 such that vertex i is the
          q[i]-th vertex in a postorder numbering of the tree.
          That is, this is the inverse of the previous q. )

	In the child structure, lower-numbered children are represented
	first, so that a tree which is already numbered in postorder
	will not have its order changed.

  Written by John Gilbert, Xerox, 10 Dec 1990.
  Based on code written by John Gilbert at CMI in 1987.
 

int_t * next_kid [static]

int_t* post [static]

int_t postnum [static]