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.
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/smalloc.h"
57 static int sid_comp(const void *a
, const void *b
)
68 return (sa
->atom
-sb
->atom
);
76 static int mk_grey(egCol egc
[], t_graph
*g
, int *AtomI
,
77 int maxsid
, t_sid sid
[])
79 int j
, ng
, ai
, aj
, g0
;
85 /* Loop over all the bonds */
86 for (j
= 0; (j
< g
->nedge
[ai
]); j
++)
88 aj
= g
->edge
[ai
][j
]-g0
;
89 /* If there is a white one, make it gray and set pbc */
90 if (egc
[aj
] == egcolWhite
)
98 /* Check whether this one has been set before... */
99 range_check(aj
+g0
, 0, maxsid
);
100 range_check(ai
+g0
, 0, maxsid
);
101 if (sid
[aj
+g0
].sid
!= -1)
103 gmx_fatal(FARGS
, "sid[%d]=%d, sid[%d]=%d, file %s, line %d",
104 ai
, sid
[ai
+g0
].sid
, aj
, sid
[aj
+g0
].sid
, __FILE__
, __LINE__
);
108 sid
[aj
+g0
].sid
= sid
[ai
+g0
].sid
;
109 sid
[aj
+g0
].atom
= aj
+g0
;
117 static int first_colour(int fC
, egCol Col
, t_graph
*g
, egCol egc
[])
118 /* Return the first node with colour Col starting at fC.
119 * return -1 if none found.
124 for (i
= fC
; (i
< g
->nnodes
); i
++)
126 if ((g
->nedge
[i
] > 0) && (egc
[i
] == Col
))
135 static int mk_sblocks(FILE *fp
, t_graph
*g
, int maxsid
, t_sid sid
[])
138 int nW
, nG
, nB
; /* Number of Grey, Black, White */
139 int fW
, fG
; /* First of each category */
140 egCol
*egc
= NULL
; /* The colour of each node */
160 /* We even have a loop invariant:
161 * nW+nG+nB == g->nbound
166 fprintf(fp
, "Walking down the molecule graph to make constraint-blocks\n");
171 /* Find the first white, this will allways be a larger
172 * number than before, because no nodes are made white
175 if ((fW
= first_colour(fW
, egcolWhite
, g
, egc
)) == -1)
177 gmx_fatal(FARGS
, "No WHITE nodes found while nW=%d\n", nW
);
180 /* Make the first white node grey, and set the block number */
182 range_check(fW
+g0
, 0, maxsid
);
183 sid
[fW
+g0
].sid
= nblock
++;
187 /* Initial value for the first grey */
192 fprintf(debug
, "Starting G loop (nW=%d, nG=%d, nB=%d, total %d)\n",
193 nW
, nG
, nB
, nW
+nG
+nB
);
198 if ((fG
= first_colour(fG
, egcolGrey
, g
, egc
)) == -1)
200 gmx_fatal(FARGS
, "No GREY nodes found while nG=%d\n", nG
);
203 /* Make the first grey node black */
204 egc
[fG
] = egcolBlack
;
208 /* Make all the neighbours of this black node grey
209 * and set their block number
211 ng
= mk_grey(egc
, g
, &fG
, maxsid
, sid
);
212 /* ng is the number of white nodes made grey */
221 fprintf(debug
, "Found %d shake blocks\n", nblock
);
229 int first
, last
, sid
;
232 static int ms_comp(const void *a
, const void *b
)
234 t_merge_sid
*ma
= (t_merge_sid
*)a
;
235 t_merge_sid
*mb
= (t_merge_sid
*)b
;
238 d
= ma
->first
-mb
->first
;
241 return ma
->last
-mb
->last
;
249 static int merge_sid(int at_start
, int at_end
, int nsid
, t_sid sid
[],
252 int i
, j
, k
, n
, isid
, ndel
;
256 /* We try to remdy the following problem:
257 * Atom: 1 2 3 4 5 6 7 8 9 10
258 * Sid: 0 -1 1 0 -1 1 1 1 1 1
261 /* Determine first and last atom in each shake ID */
264 for (k
= 0; (k
< nsid
); k
++)
266 ms
[k
].first
= at_end
+1;
270 for (i
= at_start
; (i
< at_end
); i
++)
273 range_check(isid
, -1, nsid
);
276 ms
[isid
].first
= min(ms
[isid
].first
, sid
[i
].atom
);
277 ms
[isid
].last
= max(ms
[isid
].last
, sid
[i
].atom
);
280 qsort(ms
, nsid
, sizeof(ms
[0]), ms_comp
);
282 /* Now merge the overlapping ones */
284 for (k
= 0; (k
< nsid
); )
286 for (j
= k
+1; (j
< nsid
); )
288 if (ms
[j
].first
<= ms
[k
].last
)
290 ms
[k
].last
= max(ms
[k
].last
, ms
[j
].last
);
291 ms
[k
].first
= min(ms
[k
].first
, ms
[j
].first
);
307 for (k
= 0; (k
< nsid
); k
++)
309 while ((k
< nsid
-1) && (ms
[k
].sid
== -1))
311 for (j
= k
+1; (j
< nsid
); j
++)
313 memcpy(&(ms
[j
-1]), &(ms
[j
]), sizeof(ms
[0]));
319 for (k
= at_start
; (k
< at_end
); k
++)
325 sblock
->nalloc_index
= sblock
->nr
+1;
326 snew(sblock
->index
, sblock
->nalloc_index
);
327 sblock
->nra
= at_end
- at_start
;
328 sblock
->nalloc_a
= sblock
->nra
;
329 snew(sblock
->a
, sblock
->nalloc_a
);
330 sblock
->index
[0] = 0;
331 for (k
= n
= 0; (k
< nsid
); k
++)
333 sblock
->index
[k
+1] = sblock
->index
[k
] + ms
[k
].last
- ms
[k
].first
+1;
334 for (j
= ms
[k
].first
; (j
<= ms
[k
].last
); j
++)
336 range_check(n
, 0, sblock
->nra
);
338 range_check(j
, 0, at_end
);
339 if (sid
[j
].sid
== -1)
345 fprintf(stderr
, "Double sids (%d, %d) for atom %d\n", sid
[j
].sid
, k
, j
);
350 /* Removed 2007-09-04
351 sblock->index[k+1] = natoms;
352 for(k=0; (k<natoms); k++)
353 if (sid[k].sid == -1)
358 assert(sblock
->index
[k
] == sblock
->nra
);
364 void gen_sblocks(FILE *fp
, int at_start
, int at_end
,
365 t_idef
*idef
, t_blocka
*sblock
,
369 int i
, i0
, j
, k
, istart
, n
;
373 g
= mk_graph(NULL
, idef
, at_start
, at_end
, TRUE
, bSettle
);
376 p_graph(debug
, "Graaf Dracula", g
);
379 for (i
= at_start
; (i
< at_end
); i
++)
384 nsid
= mk_sblocks(fp
, g
, at_end
, sid
);
391 /* Now sort the shake blocks... */
392 qsort(sid
+at_start
, at_end
-at_start
, (size_t)sizeof(sid
[0]), sid_comp
);
396 fprintf(debug
, "Sorted shake block\n");
397 for (i
= at_start
; (i
< at_end
); i
++)
399 fprintf(debug
, "sid[%5d] = atom:%5d sid:%5d\n", i
, sid
[i
].atom
, sid
[i
].sid
);
402 /* Now check how many are NOT -1, i.e. how many have to be shaken */
403 for (i0
= at_start
; (i0
< at_end
); i0
++)
405 if (sid
[i0
].sid
> -1)
411 /* Now we have the sids that have to be shaken. We'll check the min and
412 * max atom numbers and this determines the shake block. DvdS 2007-07-19.
413 * For the purpose of making boundaries all atoms in between need to be
414 * part of the shake block too. There may be cases where blocks overlap
415 * and they will have to be merged.
417 nsid
= merge_sid(at_start
, at_end
, nsid
, sid
, sblock
);
418 /* Now sort the shake blocks again... */
419 /*qsort(sid,natoms,(size_t)sizeof(sid[0]),sid_comp);*/
421 /* Fill the sblock struct */
422 /* sblock->nr = nsid;
423 sblock->nra = natoms;
424 srenew(sblock->a,sblock->nra);
425 srenew(sblock->index,sblock->nr+1);
430 sblock->index[n++]=k;
432 istart = sid[i].atom;
433 while ((i<natoms-1) && (sid[i+1].sid == isid))
435 /* After while: we found a new block, or are thru with the atoms */
436 /* for(j=istart; (j<=sid[i].atom); j++,k++)
438 sblock->index[n] = k;
442 gmx_fatal(FARGS,"Death Horror: nsid = %d, n= %d",nsid,n);
448 /* Due to unknown reason this free generates a problem sometimes */
453 fprintf(debug
, "Done gen_sblocks\n");