Computer Physics Communications Program Library

Programs in Physics & Physical Chemistry

PROGRAM SUMMARY

Manuscript Title: Shortest multiple disconnected path for the analysis of entanglements in two-and three-dimensional polymeric systems
Authors: Martin Kröger
Program title: Z
Catalogue identifier: ADVG
Journal reference: Comput. Phys. Commun. 168(2005)209
Programming language: USANSI Fortran 77 and Fortran 90.
Computer: Silicon Graphics (Irix), Sun (Solaris), PC (Linux).
Operating system: UNIX, Linux.
RAM: 1 MByte
Keywords: primitive path, multiple disconnected path, entanglement, configuration, polymer, obstacles, line segments, nodes, edges, algorithm, scaling behavior, critical molecular weight, concentration.
PACS: 36.20.Ey, 82.35.Lr, 83.10.Kn.
Classification: 7.7.
Nature of problem: The problem is to obtain primitive paths substantiating a shortest multiple disconnected path (SP) for a given polymer configuration (chains of particles, with or without additional single particles as obstacles for the 2D case). Primitive paths are here defined as in [1, 2] as the shortest line (path) respecting 'topological' constraints (from neighboring polymers or point obstacles) between ends of polymers. There is a unique solution for the 2D case. For the 3D case it is unique if we construct a primitive path of a single chain embedded within fixed line obstacles [3]. For a large 3D configuration made of several chains, short is meant to be the Euclidean shortest multiple disconnected path (SP) where primitive paths are constructed for all chains simultaneously. While the latter problem, in general, does not possess a unique solution, the algorithm must return a locally optimal solution, robust against minor displacements of the disconnected path and chain re-labeling. The problem is solved if the number of kinks (or entanglements Z), explicitly deduced from the SP, is quite insensitive to the exact conformation of the SP which allows to estimate Z with a small error.
Solution method: Primitive paths are constructed from the given polymer configuration (a non-shortest multiple disconnected path, including obstacles, if present) by first replacing each polymer contour by a line with a number of 'kinks' (beads, nodes) and 'segments' (edges). To obtain primitive paths, defined to be uncrossable by any other objects (neighboring primitive paths, line or point obstacles), the algorithm minimizes the length of all primitive paths consecutively, until a final minimum Euclidean length of the SP is reached. Fast geometric operations rather than dynamical methods are used to minimize the contour lengths of the primitive paths. Neighbor lists are used to keep track of potentially intersecting segments of other chains. Periodic boundary conditions are employed. A finite small line thickness is used in order to make sure that entanglements are not 'lost' due to finite precision of representation of numbers.
Restrictions: For a single chain embedded within fixed line or point obstacles, the algorithm returns the exact SP. For more complex problems, the algorithm returns a locally optimal SP. Except for exotic, probably rare, configurations it turns out that different locally optimal SPs possess quite an identical number of nodes. In general, the problem constructing the SP is known to be NP-hard [3], and we offer a solution which should suffice to analyze physical problems, and gives an estimate about the precision and uniqueness of the result (from a standard deviation by varying the parameter: cyclicswitch). The program is NOT restricted to handle systems for which segment lengths of the SP exceed half the box size.
Running time: Typical running times are approximately two orders of magnitude shorter compared with the ones needed for a corresponding molecular dynamics approach, and scale mostly linearly with system size. We provide a benchmark table.
References:
[1]	M. Rubinstein, E. Helfand, Statistics of the entanglement of polymers: Concentration effects, J. Chem. Phys. 82, 2477 (1985).
[2]	R. Everaers, S. K. Sukumaran, G. S. Grest, C. Svaneborg, A. Sivasubramanian, K. Kremer, Science 303, 823 (2004).
[3]	J. S. B. Mitchell, Geometric shortest paths and network optimization., in: Handbook of Computational Geometry, J.-R.Sack, J. Urrutia, eds., pp. 633-701 (Elsevier, Amsterdam 20001)