Mercurial > repos > immport-devteam > cross_sample

comparison src/find_connected.c @ 1:7eab80f86779 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add FLOCK
author immport-devteam
date Mon, 27 Feb 2017 13:26:09 -0500
parents
children
comparison
equal deleted inserted replaced
0:8d951baf795f 1:7eab80f86779
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <assert.h>
5
6 //static const char *rcsid = "$Id: find_connected.c,v 1.1 2008/09/05 21:54:40 rpl Exp $";
7
8 int find_connected(int **G, int num_dense_grids, int ndim, int *grid_clusterID);
9 void depth_first(int startnode);
10
11 void bail(const char *); /* exits via abort */
12 static void check_clusters(int *gcID, int ndense);
13 static void merge_cluster(int from, int into);
14
15
16 /* Vars that will not change througout the depth-first recursion. We
17 store them here to avoid endless replication on the stack. */
18 static int **Gr=0;
19 static int *gcID = 0; /* grid cluster IDs */
20 static int *cluster_count=0; /* count of nodes per cluster */
21 static int ndense=0;
22 static int ndim=0;
23 /* cid changes between depth-first searches, but is constant within a
24 single search, so it goes here. */
25 static int cid=0;
26
27 /* Find connected components in the graph of neighboring grids defined in G.
28 *
29 * Output:
30 *
31 * grid_clusterID[] -- cluster to which each dense grid was assigned
32 * return value -- number of clusters assigned.
33 */
34 int find_connected(int **G, int n_dense_grids, int num_dm, int *grid_clusterID)
35 {
36 int nclust=0; /* number of clusters found */
37 int i;
38 int *subfac;
39 int subval=0,nempty=0;
40 int clustid=0;
41
42 size_t sz = n_dense_grids*sizeof(int);
43 cluster_count = malloc(sz);
44 if(!cluster_count)
45 bail("find_connected: Unable to allocate %zd bytes.\n");
46 memset(cluster_count,0,sz);
47
48 /* set up the statics that will be used in the DFS */
49 Gr=G;
50 gcID = grid_clusterID;
51 ndense = n_dense_grids;
52 ndim = num_dm;
53
54
55 for(i=0;i<ndense;++i)
56 grid_clusterID[i] = -1;
57
58 for(i=0;i<ndense;++i) {
59 if(grid_clusterID[i] < 0) { /* grid hasn't been assigned yet */
60 cid = nclust++;
61 depth_first(i);
62 }
63 }
64
65 #ifndef NDEBUG
66 check_clusters(gcID,ndense);
67 #endif
68
69 /* At this point we probably have some clusters that are empty due to merging.
70 We want to compact the cluster numbering to eliminate the empty clusters. */
71
72 subfac = malloc(sz);
73 if(!subfac)
74 bail("find_connected: Unable to allocate %zd bytes.\n");
75 subval=0;
76 nempty=0;
77
78 /* cluster #i needs to have its ID decremented by 1 for each empty cluster with
79 ID < i. Precaclulate the decrements in this loop: */
80 for(i=0;i<nclust;++i) {
81 //clustid = grid_clusterID[i];
82 if(cluster_count[i] == 0) {
83 subval++;
84 nempty++;
85 }
86 subfac[i] = subval;
87 }
88
89 /* Now apply the decrements to all of the dense grids */
90 for(i=0;i<ndense;++i) {
91 clustid = grid_clusterID[i];
92 grid_clusterID[i] -= subfac[clustid];
93 }
94
95 #ifndef NDEBUG
96 // check_clusters(gcID,ndense);
97 #endif
98
99 /* correct the number of clusters found */
100 nclust -= nempty;
101
102 return nclust;
103 }
104
105
106 /* Do a depth-first search for a single connected component in graph
107 * G. Start from node, tag the nodes found with cid, and record
108 * the tags in grid_clusterID. Also, record the node count in
109 * cluster_count. If we find a node that has already been assigned to
110 * a cluster, that means we're merging two clusters, so zero out the
111 * old cid's node count.
112 *
113 * Note that our graph is constructed as a DAG, so we can be
114 * guaranteed to terminate without checking for cycles.
115 *
116 * Note2: this function can potentially recurse to depth = ndense.
117 * Plan stack size accordingly.
118 *
119 * Output:
120 *
121 * grid_clusterID[] -- array where we tag the nodes.
122 * cluster_count[] -- count of the number of nodes per cluster.
123 */
124
125 void depth_first(int node)
126 {
127 int i;
128
129 if(gcID[node] == cid) // we're guaranteed no cycles, but it is possible to reach a node
130 return; // through two different paths in the same cluster. This early
131 // return saves us some unneeded work.
132
133 /* Check to see if we are merging a cluster */
134 if(gcID[node] >= 0) {
135 /* We are, so zero the count for the old cluster. */
136 cluster_count[ gcID[node] ] = 0;
137 merge_cluster(gcID[node], cid);
138 return;
139 }
140
141 /* Update for this node */
142 gcID[node] = cid;
143 cluster_count[cid]++;
144
145 /* Recursively search the child nodes */
146 for(i=0; i<ndim; ++i)
147 if(Gr[node][i] >= 0) /* This is a child node */
148 depth_first(Gr[node][i]);
149 }
150
151 void bail(const char *msg)
152 {
153 fprintf(stderr,"%s",msg);
154 abort();
155 }
156
157
158 static void check_clusters(int *gcID, int ndense)
159 {
160 int i;
161
162 for(i=0; i<ndense; ++i)
163 if(gcID[i] < 0) {
164 fprintf(stderr,"faulty cluster id at i= %d\n",i);
165 abort();
166 }
167 }
168
169 static void merge_cluster(int from, int into)
170 {
171 int i;
172
173 for(i=0; i<ndense; ++i)
174 if(gcID[i] == from)
175 gcID[i] = into;
176 }