0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Can you give a link to the code you did find? $\endgroup$ – Daniel Shapero Feb 22 at 17:12
  • $\begingroup$ @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. $\endgroup$ – Laryx Decidua Feb 23 at 15:21
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 ;-) $\endgroup$ – Laryx Decidua Feb 23 at 15:35
  • $\begingroup$ 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 $\endgroup$ – Charlie S Feb 23 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.