/[escript]/branches/doubleplusgood/paso/src/Pattern_mis.cpp
ViewVC logotype

Contents of /branches/doubleplusgood/paso/src/Pattern_mis.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

  ViewVC Help
Powered by ViewVC 1.1.26