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

Question

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!

Answer 1

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.

Answer 2

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;

typedef boost::graph_traits<myGraph>::adjacency_iterator adj_iter;

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'
    for (std::pair<adj_iter, adj_iter> ap = boost::adjacent_vertices(path.back(), g); ap.first != ap.second; ++ap.first)
    {
        //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];
        //whatever your termination conditions are
        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.