|
1
|
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 }
|
