← Back to branch summary

~ubuntu-branches/ubuntu/natty/suitesparse/natty

« back to all changes in this revision

Viewing changes to CAMD/Source/camd_preprocess.c

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme
  • Date: 2006-12-22 10:16:15 UTC
  • Revision ID: james.westby@ubuntu.com-20061222101615-2ohaj8902oix2rnk
Tags: upstream-2.3.1
Import upstream version 2.3.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
CAMD/Source/camd_preprocess.c
 
1
/* ========================================================================= */
 
2
/* === CAMD_preprocess ===================================================== */
 
3
/* ========================================================================= */
 
4
 
 
5
/* ------------------------------------------------------------------------- */
 
6
/* CAMD Version 2.1, Copyright (c) 2006 by Timothy A. Davis, Yanqing Chen,   */
 
7
/* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
 
8
/* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
 
9
/* web: http://www.cise.ufl.edu/research/sparse/camd                         */
 
10
/* ------------------------------------------------------------------------- */
 
11
 
 
12
/* Sorts, removes duplicate entries, and transposes from the nonzero pattern of
 
13
 * a column-form matrix A, to obtain the matrix R.  The input matrix can have
 
14
 * duplicate entries and/or unsorted columns (CAMD_valid (n,Ap,Ai) must not be
 
15
 * CAMD_INVALID).
 
16
 *
 
17
 * This input condition is NOT checked.  This routine is not user-callable.
 
18
 */
 
19
 
 
20
#include "camd_internal.h"
 
21
 
 
22
/* ========================================================================= */
 
23
/* === CAMD_preprocess ===================================================== */
 
24
/* ========================================================================= */
 
25
 
 
26
/* CAMD_preprocess does not check its input for errors or allocate workspace.
 
27
 * On input, the condition (CAMD_valid (n,n,Ap,Ai) != CAMD_INVALID) must hold.
 
28
 */
 
29
 
 
30
GLOBAL void CAMD_preprocess
 
31
(
 
32
    Int n,              /* input matrix: A is n-by-n */
 
33
    const Int Ap [ ],   /* size n+1 */
 
34
    const Int Ai [ ],   /* size nz = Ap [n] */
 
35
 
 
36
    /* output matrix R: */
 
37
    Int Rp [ ],         /* size n+1 */
 
38
    Int Ri [ ],         /* size nz (or less, if duplicates present) */
 
39
 
 
40
    Int W [ ],          /* workspace of size n */
 
41
    Int Flag [ ]        /* workspace of size n */
 
42
)
 
43
{
 
44
 
 
45
    /* --------------------------------------------------------------------- */
 
46
    /* local variables */
 
47
    /* --------------------------------------------------------------------- */
 
48
 
 
49
    Int i, j, p, p2 ;
 
50
 
 
51
    ASSERT (CAMD_valid (n, n, Ap, Ai) != CAMD_INVALID) ;
 
52
 
 
53
    /* --------------------------------------------------------------------- */
 
54
    /* count the entries in each row of A (excluding duplicates) */
 
55
    /* --------------------------------------------------------------------- */
 
56
 
 
57
    for (i = 0 ; i < n ; i++)
 
58
    {
 
59
        W [i] = 0 ;             /* # of nonzeros in row i (excl duplicates) */
 
60
        Flag [i] = EMPTY ;      /* Flag [i] = j if i appears in column j */
 
61
    }
 
62
    for (j = 0 ; j < n ; j++)
 
63
    {
 
64
        p2 = Ap [j+1] ;
 
65
        for (p = Ap [j] ; p < p2 ; p++)
 
66
        {
 
67
            i = Ai [p] ;
 
68
            if (Flag [i] != j)
 
69
            {
 
70
                /* row index i has not yet appeared in column j */
 
71
                W [i]++ ;           /* one more entry in row i */
 
72
                Flag [i] = j ;      /* flag row index i as appearing in col j*/
 
73
            }
 
74
        }
 
75
    }
 
76
 
 
77
    /* --------------------------------------------------------------------- */
 
78
    /* compute the row pointers for R */
 
79
    /* --------------------------------------------------------------------- */
 
80
 
 
81
    Rp [0] = 0 ;
 
82
    for (i = 0 ; i < n ; i++)
 
83
    {
 
84
        Rp [i+1] = Rp [i] + W [i] ;
 
85
    }
 
86
    for (i = 0 ; i < n ; i++)
 
87
    {
 
88
        W [i] = Rp [i] ;
 
89
        Flag [i] = EMPTY ;
 
90
    }
 
91
 
 
92
    /* --------------------------------------------------------------------- */
 
93
    /* construct the row form matrix R */
 
94
    /* --------------------------------------------------------------------- */
 
95
 
 
96
    /* R = row form of pattern of A */
 
97
    for (j = 0 ; j < n ; j++)
 
98
    {
 
99
        p2 = Ap [j+1] ;
 
100
        for (p = Ap [j] ; p < p2 ; p++)
 
101
        {
 
102
            i = Ai [p] ;
 
103
            if (Flag [i] != j)
 
104
            {
 
105
                /* row index i has not yet appeared in column j */
 
106
                Ri [W [i]++] = j ;  /* put col j in row i */
 
107
                Flag [i] = j ;      /* flag row index i as appearing in col j*/
 
108
            }
 
109
        }
 
110
    }
 
111
 
 
112
#ifndef NDEBUG
 
113
    ASSERT (CAMD_valid (n, n, Rp, Ri) == CAMD_OK) ;
 
114
    for (j = 0 ; j < n ; j++)
 
115
    {
 
116
        ASSERT (W [j] == Rp [j+1]) ;
 
117
    }
 
118
#endif
 
119
}