/[escript]/trunk/paso/src/Pattern_mis.c
ViewVC logotype

Annotation of /trunk/paso/src/Pattern_mis.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3642 - (hide annotations)
Thu Oct 27 03:41:51 2011 UTC (7 years, 7 months ago) by caltinay
File MIME type: text/plain
File size: 5442 byte(s)
Assorted spelling/comment fixes in paso.

1 ksteube 1315
2     /*******************************************************
3 ksteube 1811 *
4 jfenwick 2881 * Copyright (c) 2003-2010 by University of Queensland
5 ksteube 1811 * Earth Systems Science Computational Center (ESSCC)
6     * http://www.uq.edu.au/esscc
7     *
8     * Primary Business: Queensland, Australia
9     * Licensed under the Open Software License version 3.0
10     * http://www.opensource.org/licenses/osl-3.0.php
11     *
12     *******************************************************/
13 ksteube 1315
14 ksteube 1811
15 ksteube 1315 /**********************************************************************/
16    
17     /* Paso: Pattern: Paso_Pattern_mis
18    
19 caltinay 3642 Searches for a maximal independent set MIS in the matrix pattern.
20     Vertices in the maximal independent set are marked in mis_marker.
21     Nodes to be considered are marked by -1 on the input in mis_marker.
22 ksteube 1315
23     */
24     /**********************************************************************/
25    
26 caltinay 3642 /* Copyrights by ACcESS Australia 2003,2004,2005 */
27     /* Author: Lutz Gross, l.gross@uq.edu.au */
28 ksteube 1315
29     /**************************************************************/
30    
31 jfenwick 3259
32 ksteube 1315 #include "Paso.h"
33     #include "PasoUtil.h"
34     #include "Pattern.h"
35 jfenwick 3259 #include "esysUtils/mpi_C.h"
36 ksteube 1315
37     /* used to generate pseudo random numbers: */
38    
39     static double Paso_Pattern_mis_seed=.4142135623730951;
40    
41    
42     /***************************************************************/
43    
44     #define IS_AVAILABLE -1
45     #define IS_IN_MIS_NOW -2
46     #define IS_IN_MIS -3
47     #define IS_CONNECTED_TO_MIS -4
48    
49     void Paso_Pattern_mis(Paso_Pattern* pattern_p, index_t* mis_marker) {
50    
51 gross 3312 const index_t index_offset=(pattern_p->type & MATRIX_FORMAT_OFFSET1 ? 1:0);
52 ksteube 1315 dim_t i;
53     double *value;
54     index_t naib,iptr;
55     bool_t flag;
56     dim_t n=pattern_p->numOutput;
57 gross 3094 if (pattern_p->numOutput != pattern_p->numInput) {
58 jfenwick 3259 Esys_setError(VALUE_ERROR,"Paso_Pattern_mis: pattern must be square.");
59 gross 3094 return;
60     }
61 ksteube 1315 value=TMPMEMALLOC(n,double);
62 jfenwick 3259 if (!Esys_checkPtr(value)) {
63 ksteube 1315
64    
65     /* is there any vertex available ?*/
66     while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {
67     /* step 1: assign a random number in [0,1] to each vertex */
68 caltinay 3642 /* step 2: if the vertex is available, check if its value is the smaller than all values of its neighbours
69     if the answer is yes, the vertex is put into the independent set and all
70     its neighbours are removed from the graph by setting it mis_marker to FALSE */
71 ksteube 1315
72 caltinay 3642 /* step 2: is the vertex is available, check if its value is the smaller than all values of its neighbours */
73 ksteube 1315
74     /* assign random number in [0,1] to each vertex */
75     #pragma omp parallel for private(i) schedule(static)
76     for (i=0;i<n;++i) {
77     if (mis_marker[i]==IS_AVAILABLE) {
78     value[i]=fmod(Paso_Pattern_mis_seed*(i+1),1.);
79     } else {
80     value[i]=2.;
81     }
82     }
83     /* update the seed */
84     /* Paso_Pattern_mis_seed=fmod(sqrt(Paso_Pattern_mis_seed*(n+1)),1.); */
85 caltinay 3642 /* detect independent vertices as those vertices that have a value less than all values of its neighbours */
86 ksteube 1315 #pragma omp parallel for private(naib,i,iptr,flag) schedule(static)
87     for (i=0;i<n;++i) {
88     if (mis_marker[i]==IS_AVAILABLE) {
89     flag=IS_IN_MIS_NOW;
90     for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
91     naib=pattern_p->index[iptr]-index_offset;
92     if (naib!=i && value[naib]<=value[i]) {
93     flag=IS_AVAILABLE;
94     break;
95     }
96     }
97     mis_marker[i]=flag;
98     }
99     }
100 caltinay 3642 /* detect independent vertices as those vertices that have a value less than all values of its neighbours */
101 ksteube 1315 #pragma omp parallel for private(naib,i,iptr) schedule(static)
102     for (i=0;i<n;i++) {
103     if (mis_marker[i]==IS_IN_MIS_NOW) {
104     for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
105     naib=pattern_p->index[iptr]-index_offset;
106     if (naib!=i) mis_marker[naib]=IS_CONNECTED_TO_MIS;
107     }
108     mis_marker[i]=IS_IN_MIS;
109     }
110     }
111     }
112     /* swap to TRUE/FALSE in mis_marker */
113     #pragma omp parallel for private(i) schedule(static)
114     for (i=0;i<n;i++) mis_marker[i]=(mis_marker[i]==IS_IN_MIS);
115     }
116     TMPMEMFREE(value);
117     }
118     #undef IS_AVAILABLE
119     #undef IS_IN_MIS_NOW
120     #undef IS_IN_MIS
121     #undef IS_CONNECTED_TO_MIS
122 gross 1361
123     void Paso_Pattern_color(Paso_Pattern* pattern, index_t* num_colors, index_t* colorOf) {
124     index_t out=0, *mis_marker=NULL,i;
125     dim_t n=pattern->numOutput;
126     mis_marker=TMPMEMALLOC(n,index_t);
127 jfenwick 3259 if ( !Esys_checkPtr(mis_marker) ) {
128 gross 1361 /* get coloring */
129     #pragma omp parallel for private(i) schedule(static)
130 artak 2107 for (i = 0; i < n; ++i) {
131     colorOf[i]=-1;
132     mis_marker[i]=-1;
133     }
134 gross 1361
135 jfenwick 3259 while (Paso_Util_isAny(n,colorOf,-1) && Esys_noError()) {
136 artak 2107 /*#pragma omp parallel for private(i) schedule(static)
137     for (i = 0; i < n; ++i) mis_marker[i]=colorOf[i];*/
138 gross 1361 Paso_Pattern_mis(pattern,mis_marker);
139    
140     #pragma omp parallel for private(i) schedule(static)
141 artak 2107 for (i = 0; i < n; ++i) {
142 gross 2859 if (mis_marker[i]) colorOf[i]=out;
143     mis_marker[i]=colorOf[i];
144 artak 2107 }
145 gross 1361 ++out;
146     }
147     TMPMEMFREE(mis_marker);
148     *num_colors=out;
149     }
150     }
151 caltinay 3642

  ViewVC Help
Powered by ViewVC 1.1.26