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,2015,2017,2018 by the GROMACS development team.
7 * Copyright (c) 2019,2020, by the GROMACS development team, led by
8 * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
9 * and including many others, as listed in the AUTHORS file in the
10 * top-level source directory and at http://www.gromacs.org.
12 * GROMACS is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public License
14 * as published by the Free Software Foundation; either version 2.1
15 * of the License, or (at your option) any later version.
17 * GROMACS is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * Lesser General Public License for more details.
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with GROMACS; if not, see
24 * http://www.gnu.org/licenses, or write to the Free Software Foundation,
25 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27 * If you want to redistribute modifications to GROMACS, please
28 * consider that scientific software is very special. Version
29 * control is crucial - bugs must be traceable. We will be happy to
30 * consider code for inclusion in the official distribution, but
31 * derived work must not be called official GROMACS. Details are found
32 * in the README & COPYING files - if they are missing, get the
33 * official version at http://www.gromacs.org.
35 * To help us fund GROMACS development, we humbly ask that you cite
36 * the research papers on the package. Check out http://www.gromacs.org.
47 #include "gromacs/pbcutil/mshift.h"
48 #include "gromacs/topology/block.h"
49 #include "gromacs/topology/idef.h"
50 #include "gromacs/utility/fatalerror.h"
51 #include "gromacs/utility/gmxassert.h"
52 #include "gromacs/utility/smalloc.h"
59 static bool sid_comp(const t_sid& sa, const t_sid& sb)
63 return sa.atom < sb.atom;
67 return sa.sid < sb.sid;
71 static int mk_grey(gmx::ArrayRef<egCol> edgeColor, const t_graph* g, int* AtomI, int maxsid, t_sid sid[])
78 g0 = g->edgeAtomBegin;
79 /* Loop over all the bonds */
80 for (int aj : g->edges[ai])
83 /* If there is a white one, make it gray and set pbc */
84 if (edgeColor[aj] == egcolWhite)
90 edgeColor[aj] = egcolGrey;
92 /* Check whether this one has been set before... */
93 range_check(aj + g0, 0, maxsid);
94 range_check(ai + g0, 0, maxsid);
95 if (sid[aj + g0].sid != -1)
97 gmx_fatal(FARGS, "sid[%d]=%d, sid[%d]=%d, file %s, line %d", ai, sid[ai + g0].sid,
98 aj, sid[aj + g0].sid, __FILE__, __LINE__);
102 sid[aj + g0].sid = sid[ai + g0].sid;
103 sid[aj + g0].atom = aj + g0;
111 static int first_colour(const int fC, const egCol Col, const t_graph* g, gmx::ArrayRef<const egCol> edgeColor)
112 /* Return the first node with colour Col starting at fC.
113 * return -1 if none found.
118 for (i = fC; i < int(g->edges.size()); i++)
120 if (!g->edges[i].empty() && edgeColor[i] == Col)
129 static int mk_sblocks(FILE* fp, t_graph* g, int maxsid, t_sid sid[])
132 int nW, nG, nB; /* Number of Grey, Black, White */
133 int fW, fG; /* First of each category */
136 if (!g->numConnectedAtoms)
143 std::vector<egCol> edgeColor(g->edges.size(), egcolWhite);
145 g0 = g->edgeAtomBegin;
146 nW = g->numConnectedAtoms;
152 /* We even have a loop invariant:
153 * nW+nG+nB == g->nbound
158 fprintf(fp, "Walking down the molecule graph to make constraint-blocks\n");
163 /* Find the first white, this will allways be a larger
164 * number than before, because no nodes are made white
167 if ((fW = first_colour(fW, egcolWhite, g, edgeColor)) == -1)
169 gmx_fatal(FARGS, "No WHITE nodes found while nW=%d\n", nW);
172 /* Make the first white node grey, and set the block number */
173 edgeColor[fW] = egcolGrey;
174 range_check(fW + g0, 0, maxsid);
175 sid[fW + g0].sid = nblock++;
179 /* Initial value for the first grey */
184 fprintf(debug, "Starting G loop (nW=%d, nG=%d, nB=%d, total %d)\n", nW, nG, nB, nW + nG + nB);
189 if ((fG = first_colour(fG, egcolGrey, g, edgeColor)) == -1)
191 gmx_fatal(FARGS, "No GREY nodes found while nG=%d\n", nG);
194 /* Make the first grey node black */
195 edgeColor[fG] = egcolBlack;
199 /* Make all the neighbours of this black node grey
200 * and set their block number
202 ng = mk_grey(edgeColor, g, &fG, maxsid, sid);
203 /* ng is the number of white nodes made grey */
211 fprintf(debug, "Found %d shake blocks\n", nblock);
220 int first, last, sid;
223 static int ms_comp(const void* a, const void* b)
225 const t_merge_sid* ma = reinterpret_cast<const t_merge_sid*>(a);
226 const t_merge_sid* mb = reinterpret_cast<const t_merge_sid*>(b);
229 d = ma->first - mb->first;
232 return ma->last - mb->last;
240 static int merge_sid(int at_start, int at_end, int nsid, t_sid sid[], t_blocka* sblock)
242 int i, j, k, n, isid, ndel;
245 /* We try to remdy the following problem:
246 * Atom: 1 2 3 4 5 6 7 8 9 10
247 * Sid: 0 -1 1 0 -1 1 1 1 1 1
250 /* Determine first and last atom in each shake ID */
253 for (k = 0; (k < nsid); k++)
255 ms[k].first = at_end + 1;
259 for (i = at_start; (i < at_end); i++)
262 range_check(isid, -1, nsid);
265 ms[isid].first = std::min(ms[isid].first, sid[i].atom);
266 ms[isid].last = std::max(ms[isid].last, sid[i].atom);
269 qsort(ms, nsid, sizeof(ms[0]), ms_comp);
271 /* Now merge the overlapping ones */
273 for (k = 0; (k < nsid);)
275 for (j = k + 1; (j < nsid);)
277 if (ms[j].first <= ms[k].last)
279 ms[k].last = std::max(ms[k].last, ms[j].last);
280 ms[k].first = std::min(ms[k].first, ms[j].first);
296 for (k = 0; (k < nsid); k++)
298 while ((k < nsid - 1) && (ms[k].sid == -1))
300 for (j = k + 1; (j < nsid); j++)
302 std::memcpy(&(ms[j - 1]), &(ms[j]), sizeof(ms[0]));
308 for (k = at_start; (k < at_end); k++)
314 sblock->nalloc_index = sblock->nr + 1;
315 snew(sblock->index, sblock->nalloc_index);
316 sblock->nra = at_end - at_start;
317 sblock->nalloc_a = sblock->nra;
318 snew(sblock->a, sblock->nalloc_a);
319 sblock->index[0] = 0;
320 for (k = n = 0; (k < nsid); k++)
322 sblock->index[k + 1] = sblock->index[k] + ms[k].last - ms[k].first + 1;
323 for (j = ms[k].first; (j <= ms[k].last); j++)
325 range_check(n, 0, sblock->nra);
327 range_check(j, 0, at_end);
328 if (sid[j].sid == -1)
334 fprintf(stderr, "Double sids (%d, %d) for atom %d\n", sid[j].sid, k, j);
340 GMX_RELEASE_ASSERT(sblock->index[k] == sblock->nra, "Internal inconsistency; sid merge failed");
347 void gen_sblocks(FILE* fp, int at_end, const InteractionDefinitions& idef, t_blocka* sblock, gmx_bool bSettle)
354 g = mk_graph(nullptr, idef, at_end, TRUE, bSettle);
357 p_graph(debug, "Graaf Dracula", g);
360 for (i = 0; i < at_end; i++)
365 nsid = mk_sblocks(fp, g, at_end, sid);
372 /* Now sort the shake blocks... */
373 std::sort(sid, sid + at_end, sid_comp);
377 fprintf(debug, "Sorted shake block\n");
378 for (i = 0; i < at_end; i++)
380 fprintf(debug, "sid[%5d] = atom:%5d sid:%5d\n", i, sid[i].atom, sid[i].sid);
383 /* Now check how many are NOT -1, i.e. how many have to be shaken */
384 for (i0 = 0; i0 < at_end; i0++)
386 if (sid[i0].sid > -1)
392 /* Now we have the sids that have to be shaken. We'll check the min and
393 * max atom numbers and this determines the shake block. DvdS 2007-07-19.
394 * For the purpose of making boundaries all atoms in between need to be
395 * part of the shake block too. There may be cases where blocks overlap
396 * and they will have to be merged.
398 merge_sid(0, at_end, nsid, sid, sblock);
400 /* Due to unknown reason this free generates a problem sometimes */
404 fprintf(debug, "Done gen_sblocks\n");