2 * This file is part of the GROMACS molecular simulation package.
4 * Copyright (c) 1991-2000, University of Groningen, The Netherlands.
5 * Copyright (c) 2001-2004, The GROMACS development team.
6 * Copyright (c) 2013,2014, by the GROMACS development team, led by
7 * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
8 * and including many others, as listed in the AUTHORS file in the
9 * top-level source directory and at http://www.gromacs.org.
11 * GROMACS is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public License
13 * as published by the Free Software Foundation; either version 2.1
14 * of the License, or (at your option) any later version.
16 * GROMACS is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Lesser General Public License for more details.
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with GROMACS; if not, see
23 * http://www.gnu.org/licenses, or write to the Free Software Foundation,
24 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
26 * If you want to redistribute modifications to GROMACS, please
27 * consider that scientific software is very special. Version
28 * control is crucial - bugs must be traceable. We will be happy to
29 * consider code for inclusion in the official distribution, but
30 * derived work must not be called official GROMACS. Details are found
31 * in the README & COPYING files - if they are missing, get the
32 * official version at http://www.gromacs.org.
34 * To help us fund GROMACS development, we humbly ask that you cite
35 * the research papers on the package. Check out http://www.gromacs.org.
39 #include "gromacs/legacyheaders/splitter.h"
45 #include "gromacs/legacyheaders/macros.h"
46 #include "gromacs/pbcutil/mshift.h"
47 #include "gromacs/topology/block.h"
48 #include "gromacs/topology/idef.h"
49 #include "gromacs/utility/fatalerror.h"
50 #include "gromacs/utility/smalloc.h"
56 static int sid_comp(const void *a, const void *b)
67 return (sa->atom-sb->atom);
75 static int mk_grey(egCol egc[], t_graph *g, int *AtomI,
76 int maxsid, t_sid sid[])
78 int j, ng, ai, aj, g0;
84 /* Loop over all the bonds */
85 for (j = 0; (j < g->nedge[ai]); j++)
87 aj = g->edge[ai][j]-g0;
88 /* If there is a white one, make it gray and set pbc */
89 if (egc[aj] == egcolWhite)
97 /* Check whether this one has been set before... */
98 range_check(aj+g0, 0, maxsid);
99 range_check(ai+g0, 0, maxsid);
100 if (sid[aj+g0].sid != -1)
102 gmx_fatal(FARGS, "sid[%d]=%d, sid[%d]=%d, file %s, line %d",
103 ai, sid[ai+g0].sid, aj, sid[aj+g0].sid, __FILE__, __LINE__);
107 sid[aj+g0].sid = sid[ai+g0].sid;
108 sid[aj+g0].atom = aj+g0;
116 static int first_colour(int fC, egCol Col, t_graph *g, egCol egc[])
117 /* Return the first node with colour Col starting at fC.
118 * return -1 if none found.
123 for (i = fC; (i < g->nnodes); i++)
125 if ((g->nedge[i] > 0) && (egc[i] == Col))
134 static int mk_sblocks(FILE *fp, t_graph *g, int maxsid, t_sid sid[])
137 int nW, nG, nB; /* Number of Grey, Black, White */
138 int fW, fG; /* First of each category */
139 egCol *egc = NULL; /* The colour of each node */
159 /* We even have a loop invariant:
160 * nW+nG+nB == g->nbound
165 fprintf(fp, "Walking down the molecule graph to make constraint-blocks\n");
170 /* Find the first white, this will allways be a larger
171 * number than before, because no nodes are made white
174 if ((fW = first_colour(fW, egcolWhite, g, egc)) == -1)
176 gmx_fatal(FARGS, "No WHITE nodes found while nW=%d\n", nW);
179 /* Make the first white node grey, and set the block number */
181 range_check(fW+g0, 0, maxsid);
182 sid[fW+g0].sid = nblock++;
186 /* Initial value for the first grey */
191 fprintf(debug, "Starting G loop (nW=%d, nG=%d, nB=%d, total %d)\n",
192 nW, nG, nB, nW+nG+nB);
197 if ((fG = first_colour(fG, egcolGrey, g, egc)) == -1)
199 gmx_fatal(FARGS, "No GREY nodes found while nG=%d\n", nG);
202 /* Make the first grey node black */
203 egc[fG] = egcolBlack;
207 /* Make all the neighbours of this black node grey
208 * and set their block number
210 ng = mk_grey(egc, g, &fG, maxsid, sid);
211 /* ng is the number of white nodes made grey */
220 fprintf(debug, "Found %d shake blocks\n", nblock);
228 int first, last, sid;
231 static int ms_comp(const void *a, const void *b)
233 t_merge_sid *ma = (t_merge_sid *)a;
234 t_merge_sid *mb = (t_merge_sid *)b;
237 d = ma->first-mb->first;
240 return ma->last-mb->last;
248 static int merge_sid(int at_start, int at_end, int nsid, t_sid sid[],
251 int i, j, k, n, isid, ndel;
255 /* We try to remdy the following problem:
256 * Atom: 1 2 3 4 5 6 7 8 9 10
257 * Sid: 0 -1 1 0 -1 1 1 1 1 1
260 /* Determine first and last atom in each shake ID */
263 for (k = 0; (k < nsid); k++)
265 ms[k].first = at_end+1;
269 for (i = at_start; (i < at_end); i++)
272 range_check(isid, -1, nsid);
275 ms[isid].first = min(ms[isid].first, sid[i].atom);
276 ms[isid].last = max(ms[isid].last, sid[i].atom);
279 qsort(ms, nsid, sizeof(ms[0]), ms_comp);
281 /* Now merge the overlapping ones */
283 for (k = 0; (k < nsid); )
285 for (j = k+1; (j < nsid); )
287 if (ms[j].first <= ms[k].last)
289 ms[k].last = max(ms[k].last, ms[j].last);
290 ms[k].first = min(ms[k].first, ms[j].first);
306 for (k = 0; (k < nsid); k++)
308 while ((k < nsid-1) && (ms[k].sid == -1))
310 for (j = k+1; (j < nsid); j++)
312 memcpy(&(ms[j-1]), &(ms[j]), sizeof(ms[0]));
318 for (k = at_start; (k < at_end); k++)
324 sblock->nalloc_index = sblock->nr+1;
325 snew(sblock->index, sblock->nalloc_index);
326 sblock->nra = at_end - at_start;
327 sblock->nalloc_a = sblock->nra;
328 snew(sblock->a, sblock->nalloc_a);
329 sblock->index[0] = 0;
330 for (k = n = 0; (k < nsid); k++)
332 sblock->index[k+1] = sblock->index[k] + ms[k].last - ms[k].first+1;
333 for (j = ms[k].first; (j <= ms[k].last); j++)
335 range_check(n, 0, sblock->nra);
337 range_check(j, 0, at_end);
338 if (sid[j].sid == -1)
344 fprintf(stderr, "Double sids (%d, %d) for atom %d\n", sid[j].sid, k, j);
349 /* Removed 2007-09-04
350 sblock->index[k+1] = natoms;
351 for(k=0; (k<natoms); k++)
352 if (sid[k].sid == -1)
357 assert(sblock->index[k] == sblock->nra);
363 void gen_sblocks(FILE *fp, int at_start, int at_end,
364 t_idef *idef, t_blocka *sblock,
368 int i, i0, j, k, istart, n;
372 g = mk_graph(NULL, idef, at_start, at_end, TRUE, bSettle);
375 p_graph(debug, "Graaf Dracula", g);
378 for (i = at_start; (i < at_end); i++)
383 nsid = mk_sblocks(fp, g, at_end, sid);
390 /* Now sort the shake blocks... */
391 qsort(sid+at_start, at_end-at_start, (size_t)sizeof(sid[0]), sid_comp);
395 fprintf(debug, "Sorted shake block\n");
396 for (i = at_start; (i < at_end); i++)
398 fprintf(debug, "sid[%5d] = atom:%5d sid:%5d\n", i, sid[i].atom, sid[i].sid);
401 /* Now check how many are NOT -1, i.e. how many have to be shaken */
402 for (i0 = at_start; (i0 < at_end); i0++)
404 if (sid[i0].sid > -1)
410 /* Now we have the sids that have to be shaken. We'll check the min and
411 * max atom numbers and this determines the shake block. DvdS 2007-07-19.
412 * For the purpose of making boundaries all atoms in between need to be
413 * part of the shake block too. There may be cases where blocks overlap
414 * and they will have to be merged.
416 nsid = merge_sid(at_start, at_end, nsid, sid, sblock);
417 /* Now sort the shake blocks again... */
418 /*qsort(sid,natoms,(size_t)sizeof(sid[0]),sid_comp);*/
420 /* Fill the sblock struct */
421 /* sblock->nr = nsid;
422 sblock->nra = natoms;
423 srenew(sblock->a,sblock->nra);
424 srenew(sblock->index,sblock->nr+1);
429 sblock->index[n++]=k;
431 istart = sid[i].atom;
432 while ((i<natoms-1) && (sid[i+1].sid == isid))
434 /* After while: we found a new block, or are thru with the atoms */
435 /* for(j=istart; (j<=sid[i].atom); j++,k++)
437 sblock->index[n] = k;
441 gmx_fatal(FARGS,"Death Horror: nsid = %d, n= %d",nsid,n);
447 /* Due to unknown reason this free generates a problem sometimes */
452 fprintf(debug, "Done gen_sblocks\n");