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 all_paths you kindly shared in those links,
although I have it listed as a possible future step.
As a temporary workaround, I’ve been doing the following each time I want
to randomly sample paths between two nodes:
1. I calculate the min and max length of paths between the two nodes
(the min using topology.shortest_distance, a good aproximation of the max
is trivial).
2. I sample a number between those min and max`.
3. I execute topology.all_paths with that number as cutoff argument to
obtain the paths generator.
4. I then execute some sampling from that generator, with an iteration
limit.
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 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 weighted-distance is
reached? Is there any (alternative) way of controlling which paths I get
from the all_paths besides that cutoff argument? 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 graph-tool?
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
attachment.html (17.2 KB)