/[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 3259 - (hide annotations)
Mon Oct 11 01:48:14 2010 UTC (9 years ago) by jfenwick
File MIME type: text/plain
File size: 5583 byte(s)
Merging dudley and scons updates from branches

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     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    
23     */
24     /**********************************************************************/
25    
26     /* Copyrights by ACcESS Australia 2003,2004,2005 */
27 jfenwick 2608 /* 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     index_t index_offset=(pattern_p->type & PATTERN_FORMAT_OFFSET1 ? 1:0);
52     dim_t i;
53     double *value;
54     index_t naib,iptr;
55     bool_t flag;
56     dim_t n=pattern_p->numOutput;
57     if (pattern_p->type & PATTERN_FORMAT_SYM) {
58 jfenwick 3259 Esys_setError(TYPE_ERROR,"Paso_Pattern_mis: symmetric matrix pattern is not supported yet");
59 ksteube 1315 return;
60     }
61 gross 3094 if (pattern_p->numOutput != pattern_p->numInput) {
62 jfenwick 3259 Esys_setError(VALUE_ERROR,"Paso_Pattern_mis: pattern must be square.");
63 gross 3094 return;
64     }
65 ksteube 1315 value=TMPMEMALLOC(n,double);
66 jfenwick 3259 if (!Esys_checkPtr(value)) {
67 ksteube 1315
68    
69     /* is there any vertex available ?*/
70     while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {
71     /* step 1: assign a random number in [0,1] to each vertex */
72     /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours
73     if the answer is yes, the vertex is put into the independend set and all
74     its naighbours are removed from the graph by setting it mis_marker to FALSE */
75    
76     /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours */
77    
78     /* assign random number in [0,1] to each vertex */
79     #pragma omp parallel for private(i) schedule(static)
80     for (i=0;i<n;++i) {
81     if (mis_marker[i]==IS_AVAILABLE) {
82     value[i]=fmod(Paso_Pattern_mis_seed*(i+1),1.);
83     } else {
84     value[i]=2.;
85     }
86     }
87     /* update the seed */
88     /* Paso_Pattern_mis_seed=fmod(sqrt(Paso_Pattern_mis_seed*(n+1)),1.); */
89     /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
90     #pragma omp parallel for private(naib,i,iptr,flag) schedule(static)
91     for (i=0;i<n;++i) {
92     if (mis_marker[i]==IS_AVAILABLE) {
93     flag=IS_IN_MIS_NOW;
94     for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
95     naib=pattern_p->index[iptr]-index_offset;
96     if (naib!=i && value[naib]<=value[i]) {
97     flag=IS_AVAILABLE;
98     break;
99     }
100     }
101     mis_marker[i]=flag;
102     }
103     }
104     /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
105     #pragma omp parallel for private(naib,i,iptr) schedule(static)
106     for (i=0;i<n;i++) {
107     if (mis_marker[i]==IS_IN_MIS_NOW) {
108     for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
109     naib=pattern_p->index[iptr]-index_offset;
110     if (naib!=i) mis_marker[naib]=IS_CONNECTED_TO_MIS;
111     }
112     mis_marker[i]=IS_IN_MIS;
113     }
114     }
115     }
116     /* swap to TRUE/FALSE in mis_marker */
117     #pragma omp parallel for private(i) schedule(static)
118     for (i=0;i<n;i++) mis_marker[i]=(mis_marker[i]==IS_IN_MIS);
119     }
120     TMPMEMFREE(value);
121     }
122     #undef IS_AVAILABLE
123     #undef IS_IN_MIS_NOW
124     #undef IS_IN_MIS
125     #undef IS_CONNECTED_TO_MIS
126 gross 1361
127     void Paso_Pattern_color(Paso_Pattern* pattern, index_t* num_colors, index_t* colorOf) {
128     index_t out=0, *mis_marker=NULL,i;
129     dim_t n=pattern->numOutput;
130     mis_marker=TMPMEMALLOC(n,index_t);
131 jfenwick 3259 if ( !Esys_checkPtr(mis_marker) ) {
132 gross 1361 /* get coloring */
133     #pragma omp parallel for private(i) schedule(static)
134 artak 2107 for (i = 0; i < n; ++i) {
135     colorOf[i]=-1;
136     mis_marker[i]=-1;
137     }
138 gross 1361
139 jfenwick 3259 while (Paso_Util_isAny(n,colorOf,-1) && Esys_noError()) {
140 artak 2107 /*#pragma omp parallel for private(i) schedule(static)
141     for (i = 0; i < n; ++i) mis_marker[i]=colorOf[i];*/
142 gross 1361 Paso_Pattern_mis(pattern,mis_marker);
143    
144     #pragma omp parallel for private(i) schedule(static)
145 artak 2107 for (i = 0; i < n; ++i) {
146 gross 2859 if (mis_marker[i]) colorOf[i]=out;
147     mis_marker[i]=colorOf[i];
148 artak 2107 }
149 gross 1361 ++out;
150     }
151     TMPMEMFREE(mis_marker);
152     *num_colors=out;
153     }
154     }

  ViewVC Help
Powered by ViewVC 1.1.26