README: mentioning other make targets seem unnecessary
[rangi.git] / proc.c
blobcbb5047ff49932762e8afca00cfb27248a7acc96
1 /* handling solutions and root divisions */
2 #include <pthread.h>
3 #include <stdio.h>
4 #include <string.h>
5 #include "rangi.h"
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 */
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;
24 /* this makes sure each vertex is chosen as root in a single thread */
25 int ownroot(int nsub, int idx)
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;
37 pthread_mutex_unlock(&lock);
38 return ret;
41 void found(int *nodes)
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;
52 if (lastsol == i && nsols < NSOLS) {
53 lastsol = i;
54 memcpy(sols[nsols], nodes, (i + 1) * sizeof(*nodes));
55 nsols++;
57 pthread_mutex_unlock(&lock);
60 /* the size of the optimal motifs is at least nsub */
61 void nsub_detected(int nsub)
63 pthread_mutex_lock(&lock);
64 if (nsub > detected && nsub <= nsub_end)
65 detected = nsub;
66 pthread_mutex_unlock(&lock);
69 /* return the next motif size to search for */
70 int nsub_next(int nsub)
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;
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;
93 pthread_mutex_unlock(&lock);
94 return nsub;
97 void proc_init(int beg, int end, int inc, int o, int detect)
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);
107 /* should more motifs of size nsub be enumerated? */
108 int nsub_finished(int nsub)
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);
118 int motifs(int *subs[], int size)
120 int i;
121 for (i = 0; i < nsols; i++)
122 if (i < size)
123 subs[i] = sols[i];
124 return nsols;