COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/src/amd/amd_preprocess.c

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 4.1 KB
Line 
1/* ========================================================================= */
2/* === AMD_preprocess ====================================================== */
3/* ========================================================================= */
4
5/* ------------------------------------------------------------------------- */
6/* AMD, Copyright (c) Timothy A. Davis,                                      */
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/amd                          */
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 (AMD_valid (n,Ap,Ai) must not be
15 * AMD_INVALID).
16 *
17 * This input condition is NOT checked.  This routine is not user-callable.
18 */
19
20#include "amd_internal.h"
21
22/* ========================================================================= */
23/* === AMD_preprocess ====================================================== */
24/* ========================================================================= */
25
26/* AMD_preprocess does not check its input for errors or allocate workspace.
27 * On input, the condition (AMD_valid (n,n,Ap,Ai) != AMD_INVALID) must hold.
28 */
29
30GLOBAL void AMD_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 (AMD_valid (n, n, Ap, Ai) != AMD_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 (AMD_valid (n, n, Rp, Ri) == AMD_OK) ;
114    for (j = 0 ; j < n ; j++)
115    {
116        ASSERT (W [j] == Rp [j+1]) ;
117    }
118#endif
119}
Note: See TracBrowser for help on using the repository browser.