# Need software for generating self-avoiding random walks on a tetrahedral lattice

I am looking for FOSS code that can generate self-avoiding random walk trajectories on a tetrahedral lattice. The purpose of the exercise is to create random conformations of model polymer chains that serve as input to a simulation protocol. It would be nice if the code satisfied the following criteria:

• Implemented in C++ or C, or maybe Fortran, source code is available under a reasonable FOSS licence;
• The code shall be reasonably portable (no reliance on e.g. GCC extensions);
• As input it should take the length of the walk (chain length) and the length of the lattice edge ("bond length") and return one (or more) arrays of 3D coordinates;
• Performance should be adequate up to about 1000 walk steps, I don't need very long trajectories/chains;
• It has been used with success by the person who recommends it :-)

I have done my Googling homework and found one piece of software on GitHub. However, it has not been touched since 5 years and cannot be compiled with a modern compiler (GCC 10) any more.

For all hints, pointers etc. I would be grateful. Thanks!

• Can you give a link to the code you did find? Feb 22, 2021 at 17:12
• @DanielShapero https://github.com/Roulattice/Roulattice . The code is full of things like int foo; global declarations leading to multiple-declaration linking errors, uninitialised variables etc. These could probably be corrected but the software is complex enough that I didn't want to invest too much time in bringing it up to speed. Feb 23, 2021 at 15:21
• Is there any reference you can point to that better describes what you're trying to do? I don't understand the structure of the lattice you're considering or what a random walk means for you. Jul 25, 2021 at 17:11

I fixed the compilation issues in the Roulattice package you mentioned and it now compiles and seems to do stuff. Most of the issues were easily solvable, though there's an uninitialized memory error that occurs if you don't use the -torsion flag. Run it like below.

./roulattice -tetra_saw1 50 -num 1000 -torsion


The updated repo is available on my Github at: https://github.com/r-barnes/Roulattice. As of July 25, 2021 the changes are also available in Roulattice/master at https://github.com/Roulattice/Roulattice

I would comment that the code is a bit of a mess inside and doesn't include unit tests, so I recommend trying to do something to verify its outputs; I don't place high trust in the authors having done this right.

Perhaps I am misunderstanding the objective, but this seems pretty simple and wouldn't require a dedicated library (beyond that to create the mesh in the first place). Here is a recursive version I made with with the boost graph library, which is agnostic with respect to the structure of the grid.

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
int, boost::no_property, boost::no_property, boost::vecS> myGraph;

void GetPaths(const myGraph& g, int max_size, const std::vector<int>& path, std::vector<std::vector<int>>& paths)
{
//for each adjacent vertex to the last vertex in 'path'
{
//if the path contains the vertex, continue to the next adjacent vertex
if (std::find(path.begin(), path.end(), g[*ap.first]) != path.end()) { continue; }
//otherwise, make a copy of the path with space for an extra vertex (you may need 'path' for the other adjacent vertices
std::vector<int> new_path(path.size() + 1);
std::copy(path.begin(), path.end(), new_path.begin());
new_path.back() = g[*ap.first];
if (new_path.size() == max_size)
{
paths.push_back(new_path);
}
//otherwise, go deeper
else
{
GetPaths(g, max_size, new_path, paths);
}
}
}


To adapt this to your problem, I suggest using std::pair<std::vector<int>,double> as a path/length object. For the edge properties of the graph, you would have a double representing distance. The termination conditions would be a maximum number of steps or the accumulated length of the path.

You could make this non-recursive by having a container for incomplete paths, perhaps even a tbb::concurrent_vector so you can parallelize it.

• Thanks for the code. The real challenge lies in 1) constructing the tetrahedral lattice (requires some not-too-complex but easy-to-mess-up trigonometrics :-) ) and 2) making sure it runs faster than O(N^2). State-of-the-art implementations have O(N) time complexity, to achieve it they use some clever tricks which are not trivial to reproduce. That's why I'd prefer climbing onto the shoulders of giants ;-) Feb 23, 2021 at 15:35
• It seemed like your question was about walking over the grid, which is easy to write yourself. Generating the grid is harder, but there are lots of libraries out there for that. This is the easiest to use, and is very fast. wias-berlin.de/software/tetgen Feb 23, 2021 at 15:41
• Continuing to the next vertex if the current one is already in the path gives, I think, a biased distribution. Jul 25, 2021 at 4:06