38 vector<my_idxtype>& eind,
40 vector<my_idxtype>& xadj,
41 vector<my_idxtype>& adjncy,
42 const mpi::communicator& comm)
44 int i, j, jj, k, kk, m;
45 int pe, count, mask, pass;
46 int lnns, my_nns, node;
47 int firstelm, firstnode, lnode, nrecv, nsend;
50 int npes = comm.size();
51 int mype = comm.rank();
54 int nelms = elmdist[mype+1]-elmdist[mype];
62 int gminnode = mpi::all_reduce (comm, eind[
idxamin(eptr[nelms], eind)], mpi::minimum<int>());
63 for (i=0; i<eptr[nelms]; i++)
66 int gmaxnode = mpi::all_reduce (comm, eind[
idxamax(eptr[nelms], eind)], mpi::maximum<int>());
70 vector<my_idxtype> nodedist (npes+1, 0);
71 for (nodedist[0]=0, i=0, j=gmaxnode+1; i<npes; i++) {
73 nodedist[i+1] = nodedist[i]+k;
76 my_nns = nodedist[mype+1]-nodedist[mype];
77 firstnode = nodedist[mype];
79 vector<KeyValueType> nodelist (eptr[nelms]);
80 vector<my_idxtype> auxarray (eptr[nelms]);
81 vector<my_idxtype> htable (
amax(my_nns, mask+1), -1);
82 vector<int> scounts (4*npes+2);
83 int *rcounts = scounts.begin().operator->() + npes;
84 int *sdispl = scounts.begin().operator->() + 2*npes;
85 int *rdispl = scounts.begin().operator->() + 3*npes+1;
89 for (i=0; i<nelms; i++) {
90 for (j=eptr[i]; j<eptr[i+1]; j++) {
91 nodelist[j].key = eind[j];
96 ikeysort(eptr[nelms], nodelist.begin().operator->());
98 for (count=1, i=1; i<eptr[nelms]; i++) {
99 if (nodelist[i].key > nodelist[i-1].key)
104 vector<my_idxtype> nmap (lnns);
109 nmap[0] = nodelist[0].key;
110 eind[nodelist[0].val] = 0;
111 nodelist[0].val = auxarray[nodelist[0].val];
112 for (i=1; i<eptr[nelms]; i++) {
113 if (nodelist[i].key > nodelist[i-1].key) {
114 nmap[count] = nodelist[i].key;
117 eind[nodelist[i].val] = count-1;
118 nodelist[i].val = auxarray[nodelist[i].val];
124 fill (scounts.begin(), scounts.begin() + npes, 0);
125 for (pe=i=0; i<eptr[nelms]; i++) {
126 while (nodelist[i].key >= nodedist[pe+1])
132 mpi::all_to_all (comm, scounts.begin().operator->(), rcounts);
134 icopy(npes, scounts.begin().operator->(), sdispl);
135 init_csr_ptr(npes, sdispl);
137 icopy(npes, rcounts, rdispl);
138 init_csr_ptr(npes, rdispl);
140 check_macro(sdispl[npes] == eptr[nelms]*2,
"unexpected sdispl[]");
142 nrecv = rdispl[npes]/2;
143 vector<KeyValueType> recvbuffer (
amax(1, nrecv));
146 MPI_Alltoallv(nodelist.begin().operator->(), scounts.begin().operator->(), sdispl,
IDX_DATATYPE, recvbuffer.begin().operator->(), rcounts, rdispl,
IDX_DATATYPE, comm);
150 vector<my_idxtype> gnptr (my_nns+1, 0);
151 for (i=0; i<npes; i++) {
152 for (j=rdispl[i]/2; j<rdispl[i+1]/2; j++) {
153 lnode = recvbuffer[j].key-firstnode;
154 check_macro(lnode >= 0 && lnode < my_nns,
"unexpected lnode range")
159 init_csr_ptr (my_nns, gnptr.begin());
161 vector<my_idxtype> gnind (
amax(1, gnptr[my_nns]));
162 for (pe=0; pe<npes; pe++) {
163 firstelm = elmdist[pe];
164 for (j=rdispl[pe]/2; j<rdispl[pe+1]/2; j++) {
165 lnode = recvbuffer[j].key-firstnode;
166 gnind[gnptr[lnode]++] = recvbuffer[j].val+firstelm;
173 fill (scounts.begin(), scounts.begin() + npes, 0);
176 for (pe=0; pe<npes; pe++) {
177 for (j=rdispl[pe]/2; j<rdispl[pe+1]/2; j++) {
178 lnode = recvbuffer[j].key-firstnode;
179 if (htable[lnode] == -1) {
180 scounts[pe] += gnptr[lnode+1]-gnptr[lnode];
186 for (j=rdispl[pe]/2; j<rdispl[pe+1]/2; j++) {
187 lnode = recvbuffer[j].key-firstnode;
191 mpi::all_to_all (comm, scounts.begin().operator->(), rcounts);
192 icopy(npes, scounts.begin().operator->(), sdispl);
193 init_csr_ptr(npes, sdispl);
198 nsend = sdispl[npes];
200 vector<my_idxtype> sbuffer (
amax(1, nsend));
202 for (pe=0; pe<npes; pe++) {
203 for (j=rdispl[pe]/2; j<rdispl[pe+1]/2; j++) {
204 lnode = recvbuffer[j].key-firstnode;
205 if (htable[lnode] == -1) {
206 for (k=gnptr[lnode]; k<gnptr[lnode+1]; k++) {
207 if (k == gnptr[lnode])
208 sbuffer[count++] = -1*(gnind[k]+1);
210 sbuffer[count++] = gnind[k];
215 check_macro(count == sdispl[pe+1],
"unexpected count");
218 for (j=rdispl[pe]/2; j<rdispl[pe+1]/2; j++) {
219 lnode = recvbuffer[j].key-firstnode;
224 icopy(npes, rcounts, rdispl);
225 init_csr_ptr(npes, rdispl);
227 nrecv = rdispl[npes];
229 vector<my_idxtype> rbuffer (
amax(1, nrecv));
232 MPI_Alltoallv(sbuffer.begin().operator->(), scounts.begin().operator->(), sdispl,
IDX_DATATYPE, rbuffer.begin().operator->(), rcounts, rdispl,
IDX_DATATYPE, comm);
235 vector<my_idxtype> nptr (lnns+1, 0);
236 my_idxtype *nind = rbuffer.begin().operator->();
237 for (pe=0; pe<npes; pe++) {
238 for (j=rdispl[pe]; j<rdispl[pe+1]; j++) {
241 nind[j] = (-1*nind[j])-1;
246 init_csr_ptr(lnns, nptr.begin());
249 check_macro(nptr[lnns] == nrecv,
"unexpected nptr[]")
251 xadj.resize(nelms+1);
252 fill (xadj.begin(), xadj.end(), 0);
253 my_idxtype *myxadj = xadj.begin().operator->();
254 fill (htable.begin(), htable.begin() + mask+1, -1);
255 firstelm = elmdist[mype];
261 vector<my_idxtype> ind (maxcount);
262 vector<my_idxtype> wgt (maxcount);
263 my_idxtype *myadjncy = NULL;
265 for (pass=0; pass<2; pass++) {
266 for (i=0; i<nelms; i++) {
267 for (count=0, j=eptr[i]; j<eptr[i+1]; j++) {
270 for (k=nptr[node]; k<nptr[node+1]; k++) {
271 if ((kk=nind[k]) == firstelm+i)
continue;
272 m = htable[(kk&mask)];
276 htable[(kk&mask)] = count++;
281 for (jj=0; jj<count; jj++) {
294 if (count == maxcount-1) {
295 ind.resize (2*maxcount);
296 wgt.resize (2*maxcount);
301 for (j=0; j<count; j++) {
302 htable[(ind[j]&mask)] = -1;
303 if (wgt[j] >= *ncommonnodes) {
307 myadjncy[myxadj[i]++] = ind[j];
313 init_csr_ptr(nelms, myxadj);
314 adjncy.resize (myxadj[nelms]);
315 myadjncy = adjncy.begin().operator->();
324 for (i=0; i<eptr[nelms]; i++)
325 eind[i] = nmap[eind[i]] + gminnode;