/[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 1388 - (show annotations)
Fri Jan 11 07:45:58 2008 UTC (11 years, 8 months ago) by trankine
File MIME type: text/plain
File size: 5394 byte(s)
And get the *(&(*&(* name right
1
2 /* $Id: Pattern_mis.c 1306 2007-09-18 05:51:09Z ksteube $ */
3
4 /*******************************************************
5 *
6 * Copyright 2003-2007 by ACceSS MNRF
7 * Copyright 2007 by University of Queensland
8 *
9 * http://esscc.uq.edu.au
10 * Primary Business: Queensland, Australia
11 * Licensed under the Open Software License version 3.0
12 * http://www.opensource.org/licenses/osl-3.0.php
13 *
14 *******************************************************/
15
16 /**********************************************************************/
17
18 /* Paso: Pattern: Paso_Pattern_mis
19
20 searches for a maximal independent set MIS in the matrix pattern
21 vertices in the maximal independent set are marked in mis_marker
22 nodes to be considered are marked by -1 on the input in mis_marker
23
24 */
25 /**********************************************************************/
26
27 /* Copyrights by ACcESS Australia 2003,2004,2005 */
28 /* Author: gross@access.edu.au */
29
30 /**************************************************************/
31
32 #include "mpi_C.h"
33 #include "Paso.h"
34 #include "PasoUtil.h"
35 #include "Pattern.h"
36
37
38 /* used to generate pseudo random numbers: */
39
40 static double Paso_Pattern_mis_seed=.4142135623730951;
41
42
43 /***************************************************************/
44
45 #define IS_AVAILABLE -1
46 #define IS_IN_MIS_NOW -2
47 #define IS_IN_MIS -3
48 #define IS_CONNECTED_TO_MIS -4
49
50 void Paso_Pattern_mis(Paso_Pattern* pattern_p, index_t* mis_marker) {
51
52 index_t index_offset=(pattern_p->type & PATTERN_FORMAT_OFFSET1 ? 1:0);
53 dim_t i;
54 double *value;
55 index_t naib,iptr;
56 bool_t flag;
57 dim_t n=pattern_p->numOutput;
58 if (pattern_p->type & PATTERN_FORMAT_SYM) {
59 Paso_setError(TYPE_ERROR,"Paso_Pattern_mis: symmetric matrix pattern is not supported yet");
60 return;
61 }
62 value=TMPMEMALLOC(n,double);
63 if (!Paso_checkPtr(value)) {
64
65
66 /* is there any vertex available ?*/
67 while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {
68 /* step 1: assign a random number in [0,1] to each vertex */
69 /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours
70 if the answer is yes, the vertex is put into the independend set and all
71 its naighbours are removed from the graph by setting it mis_marker to FALSE */
72
73 /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours */
74
75 /* assign random number in [0,1] to each vertex */
76 #pragma omp parallel for private(i) schedule(static)
77 for (i=0;i<n;++i) {
78 if (mis_marker[i]==IS_AVAILABLE) {
79 value[i]=fmod(Paso_Pattern_mis_seed*(i+1),1.);
80 } else {
81 value[i]=2.;
82 }
83 }
84 /* update the seed */
85 /* Paso_Pattern_mis_seed=fmod(sqrt(Paso_Pattern_mis_seed*(n+1)),1.); */
86 /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
87 #pragma omp parallel for private(naib,i,iptr,flag) schedule(static)
88 for (i=0;i<n;++i) {
89 if (mis_marker[i]==IS_AVAILABLE) {
90 flag=IS_IN_MIS_NOW;
91 for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
92 naib=pattern_p->index[iptr]-index_offset;
93 if (naib!=i && value[naib]<=value[i]) {
94 flag=IS_AVAILABLE;
95 break;
96 }
97 }
98 mis_marker[i]=flag;
99 }
100 }
101 /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
102 #pragma omp parallel for private(naib,i,iptr) schedule(static)
103 for (i=0;i<n;i++) {
104 if (mis_marker[i]==IS_IN_MIS_NOW) {
105 for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
106 naib=pattern_p->index[iptr]-index_offset;
107 if (naib!=i) mis_marker[naib]=IS_CONNECTED_TO_MIS;
108 }
109 mis_marker[i]=IS_IN_MIS;
110 }
111 }
112 }
113 /* swap to TRUE/FALSE in mis_marker */
114 #pragma omp parallel for private(i) schedule(static)
115 for (i=0;i<n;i++) mis_marker[i]=(mis_marker[i]==IS_IN_MIS);
116 }
117 TMPMEMFREE(value);
118 }
119 #undef IS_AVAILABLE
120 #undef IS_IN_MIS_NOW
121 #undef IS_IN_MIS
122 #undef IS_CONNECTED_TO_MIS
123
124 void Paso_Pattern_color(Paso_Pattern* pattern, index_t* num_colors, index_t* colorOf) {
125 index_t out=0, *mis_marker=NULL,i;
126 dim_t n=pattern->numOutput;
127 mis_marker=TMPMEMALLOC(n,index_t);
128 if ( !Paso_checkPtr(mis_marker) ) {
129 /* get coloring */
130 #pragma omp parallel for private(i) schedule(static)
131 for (i = 0; i < n; ++i) colorOf[i]=-1;
132
133 while (Paso_Util_isAny(n,colorOf,-1) && Paso_noError()) {
134 #pragma omp parallel for private(i) schedule(static)
135 for (i = 0; i < n; ++i) mis_marker[i]=colorOf[i];
136 Paso_Pattern_mis(pattern,mis_marker);
137
138 #pragma omp parallel for private(i) schedule(static)
139 for (i = 0; i < n; ++i) if (mis_marker[i]) colorOf[i]=out;
140 ++out;
141 }
142 TMPMEMFREE(mis_marker);
143 *num_colors=out;
144 }
145 }

  ViewVC Help
Powered by ViewVC 1.1.26