Am 23.03.20 um 22:14 schrieb Franco Peschiera: > Hello Tiago, > > First of all, thanks for your time. > > I see what you mean by having a biased logic that would prefer shorter > paths to longer ones, I had not thought about that. > > Regarding the self-reference part, I think it would not be a problem > because of the structure of my particular (directed) graph. In fact, > each node represents an assignment *at some given time period* and the > outward neighbors of a node represent assignments *in the future*. In > this way, a path can never visit a previously visited node since there > are no possible cycles. In fact I can easily calculate the shortest and > longest possible path between two nodes (shortest: using graphql's > `shortest_distance` method, longest= number of periods in between the > two nodes).
Well, for DAG (directed acyclic graphs) the situation is quite different, you should have said so in the beginning. > So the paths I want to create (or sample) are just the different ways > one can go from a node N1 (in period P1) to node N2 (in period P2 > P1). > I think that in my graph I could just sample neighbors with a weight > that depends on how far they are (in number of periods) from the node: > the farthest neighbor will have the least probability of being chosen. > This way, I'd compensate the fact that shorter paths take less hops. > > What do you think? Why do I get the impression I'm using google more than you to answer your question? Here is an approach using rejection sampling: https://math.stackexchange.com/questions/2673132/a-procedure-for-sampling-paths-in-a-directed-acyclic-graph Another approach is to count the number of paths that go through each node (this is feasible for DAGs) and use this to sample directly, see: https://pdfs.semanticscholar.org/0d74/e82c41124f83c842d5432abcb914ed1f410f.pdf Best, Tiago -- Tiago de Paula Peixoto <[email protected]> _______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
