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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4873 - (show annotations)
Wed Apr 16 06:38:51 2014 UTC (5 years, 5 months ago) by caltinay
File size: 4306 byte(s)
whitespace only changes.

1
2 /*****************************************************************************
3 *
4 * Copyright (c) 2003-2014 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 2012-2013 by School of Earth Sciences
13 * Development from 2014 by Centre for Geoscience Computing (GeoComp)
14 *
15 *****************************************************************************/
16
17
18 /****************************************************************************/
19
20 /* Paso: Pattern: Pattern_mis
21
22 Searches for a maximal independent set MIS in the matrix pattern.
23 Vertices in the maximal independent set are marked in mis_marker.
24 Nodes to be considered are marked by -1 on the input in mis_marker.
25
26 */
27 /****************************************************************************/
28
29 /* Copyrights by ACcESS Australia 2003,2004,2005 */
30 /* Author: Lutz Gross, l.gross@uq.edu.au */
31
32 /****************************************************************************/
33
34 #include "Pattern.h"
35 #include "PasoUtil.h"
36
37 namespace paso {
38
39 // used to generate pseudo random numbers
40 static double Pattern_mis_seed=.4142135623730951;
41
42 #define IS_AVAILABLE -1
43 #define IS_IN_MIS_NOW -2
44 #define IS_IN_MIS -3
45 #define IS_CONNECTED_TO_MIS -4
46
47 void Pattern::mis(index_t* mis_marker) const
48 {
49 const index_t index_offset=(type & MATRIX_FORMAT_OFFSET1 ? 1:0);
50 if (numOutput != numInput) {
51 Esys_setError(VALUE_ERROR, "Pattern::mis: pattern must be square.");
52 return;
53 }
54
55 const dim_t n = numOutput;
56 double* value = new double[n];
57
58 // is there any vertex available?
59 while (util::isAny(n, mis_marker, IS_AVAILABLE)) {
60 /* step 1: assign a random number in [0,1] to each vertex
61 * step 2: if the vertex is available, check if its value is smaller
62 * than all values of its neighbours. If the answer is yes,
63 * the vertex is put into the independent set and all its
64 * neighbours are removed from the graph by setting
65 * mis_marker to false
66 */
67 /* assign random number in [0,1] to each vertex */
68 #pragma omp parallel for schedule(static)
69 for (dim_t i=0; i < n; ++i) {
70 if (mis_marker[i]==IS_AVAILABLE) {
71 value[i]=fmod(Pattern_mis_seed*(i+1),1.);
72 } else {
73 value[i]=2.;
74 }
75 }
76 // update the seed
77 // Pattern_mis_seed=fmod(sqrt(Pattern_mis_seed*(n+1)),1.);
78
79 // detect independent vertices as those vertices that have a value
80 // less than all values of its neighbours
81 #pragma omp parallel for schedule(static)
82 for (dim_t i=0; i < n; ++i) {
83 if (mis_marker[i]==IS_AVAILABLE) {
84 index_t flag=IS_IN_MIS_NOW;
85 for (index_t iptr=ptr[i]-index_offset; iptr<ptr[i+1]-index_offset; ++iptr) {
86 const index_t naib=index[iptr]-index_offset;
87 if (naib != i && value[naib] <= value[i]) {
88 flag=IS_AVAILABLE;
89 break;
90 }
91 }
92 mis_marker[i]=flag;
93 }
94 }
95 // detect independent vertices as those vertices that have a value
96 // less than all values of its neighbours
97 #pragma omp parallel for schedule(static)
98 for (dim_t i=0; i < n; i++) {
99 if (mis_marker[i]==IS_IN_MIS_NOW) {
100 for (index_t iptr=ptr[i]-index_offset; iptr<ptr[i+1]-index_offset; ++iptr) {
101 const index_t naib=index[iptr]-index_offset;
102 if (naib != i)
103 mis_marker[naib]=IS_CONNECTED_TO_MIS;
104 }
105 mis_marker[i]=IS_IN_MIS;
106 }
107 }
108 }
109 // swap to true/false in mis_marker
110 #pragma omp parallel for schedule(static)
111 for (dim_t i=0; i < n; i++)
112 mis_marker[i] = (mis_marker[i]==IS_IN_MIS);
113 delete[] value;
114 }
115 #undef IS_AVAILABLE
116 #undef IS_IN_MIS_NOW
117 #undef IS_IN_MIS
118 #undef IS_CONNECTED_TO_MIS
119
120 } // namespace paso
121

Properties

Name Value
svn:mergeinfo /branches/amg_from_3530/paso/src/Pattern_mis.cpp:3531-3826 /branches/lapack2681/paso/src/Pattern_mis.cpp:2682-2741 /branches/pasowrap/paso/src/Pattern_mis.cpp:3661-3674 /branches/py3_attempt2/paso/src/Pattern_mis.cpp:3871-3891 /branches/restext/paso/src/Pattern_mis.cpp:2610-2624 /branches/ripleygmg_from_3668/paso/src/Pattern_mis.cpp:3669-3791 /branches/stage3.0/paso/src/Pattern_mis.cpp:2569-2590 /branches/symbolic_from_3470/paso/src/Pattern_mis.cpp:3471-3974 /branches/symbolic_from_3470/ripley/test/python/paso/src/Pattern_mis.cpp:3517-3974 /release/3.0/paso/src/Pattern_mis.cpp:2591-2601 /trunk/paso/src/Pattern_mis.cpp:4257-4344 /trunk/ripley/test/python/paso/src/Pattern_mis.cpp:3480-3515

  ViewVC Help
Powered by ViewVC 1.1.26