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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 3641 by gross, Tue Oct 26 07:54:58 2010 UTC revision 3642 by caltinay, Thu Oct 27 03:41:51 2011 UTC
# Line 16  Line 16 
16    
17  /* Paso: Pattern: Paso_Pattern_mis  /* Paso: Pattern: Paso_Pattern_mis
18    
19     searches for a maximal independent set MIS in the matrix pattern     Searches for a maximal independent set MIS in the matrix pattern.
20     vertices in the maximal independent set are marked in mis_marker     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     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              */  /* Copyrights by ACcESS Australia 2003,2004,2005                      */
27  /* Author: Lutz Gross, l.gross@uq.edu.au                                */  /* Author: Lutz Gross, l.gross@uq.edu.au                              */
28    
29  /**************************************************************/  /**************************************************************/
30    
# Line 65  void Paso_Pattern_mis(Paso_Pattern* patt Line 65  void Paso_Pattern_mis(Paso_Pattern* patt
65       /* is there any vertex available ?*/       /* is there any vertex available ?*/
66       while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {       while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {
67          /* step 1: assign a random number in [0,1] to each vertex */          /* step 1: assign a random number in [0,1] to each vertex */
68          /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours          /* 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 independend set and all                     if the answer is yes, the vertex is put into the independent set and all
70                     its naighbours are removed from the graph by setting it mis_marker to FALSE */                     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 naigbours */          /* 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 */             /* assign random number in [0,1] to each vertex */
75             #pragma omp parallel for private(i) schedule(static)             #pragma omp parallel for private(i) schedule(static)
# Line 82  void Paso_Pattern_mis(Paso_Pattern* patt Line 82  void Paso_Pattern_mis(Paso_Pattern* patt
82             }             }
83             /* update the seed */             /* update the seed */
84             /* Paso_Pattern_mis_seed=fmod(sqrt(Paso_Pattern_mis_seed*(n+1)),1.); */             /* 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 naigbours */             /* 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)             #pragma omp parallel for private(naib,i,iptr,flag) schedule(static)
87             for (i=0;i<n;++i) {             for (i=0;i<n;++i) {
88                if (mis_marker[i]==IS_AVAILABLE) {                if (mis_marker[i]==IS_AVAILABLE) {
# Line 97  void Paso_Pattern_mis(Paso_Pattern* patt Line 97  void Paso_Pattern_mis(Paso_Pattern* patt
97                   mis_marker[i]=flag;                   mis_marker[i]=flag;
98                }                }
99             }             }
100             /* detect independent vertices as those vertices that have a value less than all values of its naigbours */             /* 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)             #pragma omp parallel for private(naib,i,iptr) schedule(static)
102             for (i=0;i<n;i++) {             for (i=0;i<n;i++) {
103                if (mis_marker[i]==IS_IN_MIS_NOW) {                if (mis_marker[i]==IS_IN_MIS_NOW) {
# Line 148  void Paso_Pattern_color(Paso_Pattern* pa Line 148  void Paso_Pattern_color(Paso_Pattern* pa
148      *num_colors=out;      *num_colors=out;
149    }    }
150  }  }
151    

Legend:
Removed from v.3641  
changed lines
  Added in v.3642

  ViewVC Help
Powered by ViewVC 1.1.26