Hello again Tiago, First of all thanks for the resources and help. As you may expect, I somewhat lack a specialized background in graph theory and so I sometimes miss the correct terminology. As a reminder, this is a DAG. I haven’t, yet, implemented the random unbiased generator version of As a temporary workaround, I’ve been doing the following each time I want to randomly sample paths between two nodes:
This is, of course, just a very crude and biased way of sampling, but at least it returns a different set of paths at each time it is executed. Until now, I’ve been assuming each edge has a weight of 1. I now would like to test giving edges a weight in order for that For example, I’ve been even wondering if I could just create a temporal view from the graph, by a randomly filtering edges or nodes before samplinh the paths, so as to, again, reduce the graph I will be sampling at each iteration. as always thanks for your time and help! Franco Peschiera Message: 2 _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool 
Administrator

Am 15.04.20 um 10:42 schrieb Franco Peschiera:
> I now would like to test giving edges a weight in order for that > cutoff argument to use it. I know the shortest_distance function > accepts weights of edges in order to do Dijkstra. Could the same be done > with all_paths such that the search is stopped if an accumulated > weighteddistance is reached? I'm afraid not. > Is there any (alternative) way of > controlling which paths I get from the all_paths besides that cutoff > argument? There is no other argument to the function, which is deterministic. You could randomize the order of the edges in the graph (by removing and adding them again in a random order), which will change which paths are shown first, but would not give you a proper unbiased sampling. > Or whatever specialized logic regarding path sampling / > filtering I would have to implemented myself (just like the examples you > shared)? Would this be something you would consider adding to graphtool? I think adding an algorithm to perform uniform sampling of paths in DAGs would be useful, but I can't promise I will find the time anytime soon to implement one. 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> 
In reply to this post by Franco Peschiera
Hello Tiago, Thanks again for the quick answers and feedback. In fact, the more I think about how to take the most advantage of the graph, the more I think that in my case what I would really like is to control the way the paths are being sampled. So, the process would become a biased sampling where I’m the one giving the bias in the form of the probability of choosing each edge when traversing from the origin to the destination. This probability would depend on information of the node and additional information that will depend on each iteration of my algorithm. It could also be an edge property, I guess. One caveat is that DFS will not be possible since I want to make each sampling independent from the previous one and so getting several paths would be less efficient. Although I’d assume that this is not too much of a problem given that I’d need a smaller sample if I know it’s probably going to be a better one. I was thinking on doing something on the lines of the following (I’ve only tested it with a small graph):
I fear this will not be as efficient as just getting a lot of paths via thanks! Franco
_______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool 
Administrator

Am 20.04.20 um 19:30 schrieb Franco Peschiera:
> I fear this will not be as efficient as just getting a lot of paths via > all_paths. Do you think this makes sense for sampling with preferences > on edges? I'll refrain from judging whether it makes sense. It's up to you to decide for yourself what you want to do. > And if so, do you think it will perform a lot better if I did > it as a graphtool C++ extension? In general C++ will speed up any equivalent algorithm when compared to pure python, often by factors of up to 200x. But a good advice is to focus first on defining your problem well, and writing a correct implementation first, and worrying about optimization later. 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 