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

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

Parent Directory Parent Directory | Revision Log Revision Log


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

1
2 /*******************************************************
3 *
4 * Copyright (c) 2003-2010 by University of Queensland
5 * 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
14
15 /**********************************************************************/
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 /* Author: Lutz Gross, l.gross@uq.edu.au */
28
29 /**************************************************************/
30
31
32 #include "Paso.h"
33 #include "PasoUtil.h"
34 #include "Pattern.h"
35 #include "esysUtils/mpi_C.h"
36
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 const index_t index_offset=(pattern_p->type & MATRIX_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->numOutput != pattern_p->numInput) {
58 Esys_setError(VALUE_ERROR,"Paso_Pattern_mis: pattern must be square.");
59 return;
60 }
61 value=TMPMEMALLOC(n,double);
62 if (!Esys_checkPtr(value)) {
63
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 /* 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
72 /* step 2: is the vertex is available, check if its value is the smaller than all values of its neighbours */
73
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 /* detect independent vertices as those vertices that have a value less than all values of its neighbours */
86 #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 /* detect independent vertices as those vertices that have a value less than all values of its neighbours */
101 #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
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 if ( !Esys_checkPtr(mis_marker) ) {
128 /* get coloring */
129 #pragma omp parallel for private(i) schedule(static)
130 for (i = 0; i < n; ++i) {
131 colorOf[i]=-1;
132 mis_marker[i]=-1;
133 }
134
135 while (Paso_Util_isAny(n,colorOf,-1) && Esys_noError()) {
136 /*#pragma omp parallel for private(i) schedule(static)
137 for (i = 0; i < n; ++i) mis_marker[i]=colorOf[i];*/
138 Paso_Pattern_mis(pattern,mis_marker);
139
140 #pragma omp parallel for private(i) schedule(static)
141 for (i = 0; i < n; ++i) {
142 if (mis_marker[i]) colorOf[i]=out;
143 mis_marker[i]=colorOf[i];
144 }
145 ++out;
146 }
147 TMPMEMFREE(mis_marker);
148 *num_colors=out;
149 }
150 }
151

  ViewVC Help
Powered by ViewVC 1.1.26