proc.c

   1 /* handling solutions and root divisions */
   2 #include <pthread.h>
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include "rangi.h"
   6
   7 static int nsub_beg;            /* the smallest motif size to search for */
   8 static int nsub_end;            /* the largest motif size to search for */
   9 static int nsub_inc;            /* the direction of exploring motif sizes */
  10 static int one;                 /* exit after the first motif */
  11 static int dodetect;            /* early motif detection heuristic */
  12
  13 static pthread_mutex_t lock;    /* for accessing the following variables */
  14 static int lastroot = -1;       /* the last owned root */
  15 static int lastnsub = -1;       /* last queried motif size */
  16 static int lastsol = 0;         /* the last reported solution */
  17 static int detected;            /* the last detected solution via nsub_detected() */
  18 static int sols[NSOLS][NCOLORS];
  19 static int nsols;               /* the number of motifs of size lastsol */
  20 static int sols_count[NCOLORS]; /* # solutions per motif size */
  21 static int nsub_ref[NCOLORS];   /* # threads exploring each motif size */
  22 static int done;
  23
  24 /* this makes sure each vertex is chosen as root in a single thread */
  25 int ownroot(int nsub, int idx)
  26 {
  27         int ret = 1;
  28         pthread_mutex_lock(&lock);
  29         if (nsub >= lastsol && nsub >= detected) {
  30                 if ((nsub == lastnsub && idx > lastroot) ||
  31                                 lastnsub < 0 || nsub == lastnsub + nsub_inc) {
  32                         ret = 0;
  33                         lastnsub = nsub;
  34                         lastroot = idx;
  35                 }
  36         }
  37         pthread_mutex_unlock(&lock);
  38         return ret;
  39 }
  40
  41 void found(int *nodes)
  42 {
  43         int i = 0;
  44         while (nodes[i] >= 0)
  45                 i++;
  46         pthread_mutex_lock(&lock);
  47         sols_count[i]++;
  48         if (lastsol < i) {
  49                 lastsol = i;
  50                 nsols = 0;
  51         }
  52         if (lastsol == i && nsols < NSOLS) {
  53                 lastsol = i;
  54                 memcpy(sols[nsols], nodes, (i + 1) * sizeof(*nodes));
  55                 nsols++;
  56         }
  57         pthread_mutex_unlock(&lock);
  58 }
  59
  60 /* the size of the optimal motifs is at least nsub */
  61 void nsub_detected(int nsub)
  62 {
  63         pthread_mutex_lock(&lock);
  64         if (nsub > detected && nsub <= nsub_end)
  65                 detected = nsub;
  66         pthread_mutex_unlock(&lock);
  67 }
  68
  69 /* return the next motif size to search for */
  70 int nsub_next(int nsub)
  71 {
  72         pthread_mutex_lock(&lock);
  73         if (nsub > 0) {
  74                 nsub_ref[nsub]--;
  75                 nsub += nsub_inc;
  76         } else {
  77                 nsub = nsub_inc > 0 ? nsub_beg : nsub_end;
  78         }
  79         if (nsub < nsub_beg || nsub > nsub_end || done)
  80                 nsub = -1;
  81         else
  82                 nsub_ref[nsub]++;
  83         /* checking for finishing condition; no thread working on lastsol */
  84         if (lastsol >= nsub_beg && lastsol <= nsub_end && !nsub_ref[lastsol]) {
  85                 /* hitting motif size limit or no motifs of size lastsol + 1 */
  86                 if (lastsol == nsub_end || !nsub_ref[lastsol + 1])
  87                         done = 1;
  88                 /* nsub_detected() was not called for size nsub */
  89                 if (dodetect && detected > lastsol &&
  90                                 !nsub_ref[detected] && detected < nsub)
  91                         done = 1;
  92         }
  93         pthread_mutex_unlock(&lock);
  94         return nsub;
  95 }
  96
  97 void proc_init(int beg, int end, int inc, int o, int detect)
  98 {
  99         one = o;
 100         nsub_beg = beg;
 101         nsub_end = end;
 102         nsub_inc = inc;
 103         dodetect = one ? 0 : detect;
 104         pthread_mutex_init(&lock, NULL);
 105 }
 106
 107 /* should more motifs of size nsub be enumerated? */
 108 int nsub_finished(int nsub)
 109 {
 110         /* no space for more solutions */
 111         if (nsub == lastsol && one)
 112                 return 1;
 113         if (dodetect && nsub < detected)
 114                 return 1;
 115         return nsub < lastsol || done || (nsub == nsub_end && nsols >= NSOLS);
 116 }
 117
 118 int motifs(int *subs[], int size)
 119 {
 120         int i;
 121         for (i = 0; i < nsols; i++)
 122                 if (i < size)
 123                         subs[i] = sols[i];
 124         return nsols;
 125 }