Good day to all, I wrote an initial message (through the issues site) asking about the possibility of using the It was pointed out that the: 1. The algorithm is deterministic and that 2. It’s not possible to adapt it to iterate in a unbiased random way. Now I have a couple more questions, namely searching for advice on how to achieve what I want. Context: I’ve modeled certain parts of combinatorial optimization problem as a set of graphs that I’m exploiting to efficiently generate variables on the fly during the optimization routine. A variable in my problem is represented by a path between two nodes in one of those graphs. Specifically, what I want:
For the sampling in the third step I’m currently doing the following (assuming a sample of size X and a population of paths of Y):
Many times, the sample X is really small compared to the population Y). X can be 5002000, and Y can be 100.000+. My problem is: Since I could potentially do many iterations (and samplings), I would like to have an unbiased sampling method for the Y paths without having to enumerate them all. One option is to do the sampling during the construction of the paths. I have in mind to just use the Another option, although a lot more farfetched, is to create my own Are there better options to doing this? Thanks, Franco Peschiera _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool 
Administrator

Am 21.03.20 um 17:44 schrieb Franco Peschiera:
> Since I could potentially do many iterations (and samplings), I would > like to have an unbiased sampling method for the Y paths without having > to enumerate them all. > > One option is to do the sampling during the construction of the paths. I > have in mind to just use the get_out_neighbors method on the start > node to do my own depthfirst search, randomly choosing a neighbor at > each moment until I get to the cutoff or the end node. This, I could > do for each path until I get to my limit of paths to sample. I’m not > sure, though, if this is 1) similar in logic to the all_paths method > and 2) if this is close in efficiency (due to using python to iterate > and sample instead of C++). that go through one of the neighbors, so if you want sample uniformly from all paths, you have to do a weighted sample of the neighbors at each step. And these weights would change at each step. > Another option, although a lot more farfetched, is to create my own > all_paths method in C++ and recompile my own version of graphtool. > Is this realistic? The problem here is not which language should be used. > Are there better options to doing this? Counting all paths between two nodes is conjectured to be NPHard. This is also known as the selfavoidingwalk (SAW) problem. Sampling SAWs is not straightforward either, I believe most efficient approaches are based on MCMC. I recommend you to study the literature a little bit before attempting a solution. (It would be a lot simpler if you would be seeking instead to sample *shortest* paths between two nodes. This can be done in linear time, is even implemented in graphtool already in random_shortest_path().) Best, Tiago  Tiago de Paula Peixoto <[hidden email]> _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool signature.asc (849 bytes) Download Attachment

Tiago de Paula Peixoto <tiago@skewed.de> 
Free forum by Nabble  Edit this page 