Hello,
I’m using the R package. Is there a way of randomly sampling a simple path between two vertices that does not involve all_simple_paths()? I would like to avoid exhaustive search altogether.
Thank you.
I’m not an expert on random paths, so I could be completely wrong, but I think the answer is no. I can’t find such a function in igraph, and it also seems hard to find a random path without knowing all the paths. When you want a random path, I guess you’d want every path to be returned with the same probability. But I don’t think you can know how probable a path should be before you’ve found all the paths. If you don’t want every path to have the same probability then there’s probably something you can try like try random walks, but I think it will give you skewed results, like paths from A to B being differently distributed than from B to A (not sure! Maybe it works).
What are the demands on the randomness of the paths? Equal probability for each path?
1 Like
I agree with @GroteGnoom, though my way of explaining it hopefully will add something.
In general, if you pose a random selection problem as choosing a random item x from a set of X you must be able to potentially generate the set X, unless you have a way of guaranteeing that your generation of a single item is random with respect to the options X. So, do you have to generate the full set X in this case?
When teaching Algorithms, I use shortest paths as an example of how problems that seem different in difficulty are actually of the same complexity. Consider single-source shortest paths (SSSP: finding shortest paths from A to all other vertices). One might have the intuition that the more constrained single-source single-target SP problem (only finding shortest paths from A to some specified B) is computationally simpler than SSSP because you are interested in fewer paths, but you can’t know whether you got the shortest path from A to B unless you try via all possible C because a shorter path to B may be possible via some C you have not explored. So SSSP is computationally the same as all-pairs SP. (The rest of my example to students is that the simple addition of requiring return to A makes a huge difference in complexity: it becomes the NP-Hard Traveling Salesperson Problem.) You may not necessarily be focused on shortest paths but this shows why all-pairs may be needed for your problem if it is posed as having all the paths on hand and then selecting one.
If your halting criteria were taking a given number of steps rather than reaching vertex B the situation would be different. You can then simply have a random walker that chooses randomly from each outgoing link of the vertex it is currently at (under the no-repeated-vertices constraint of simple paths). But if your halting criteria were to reach a given vertex B you could get stuck if you made a random choice to a subgraph you can’t get out of because you have already visited all the adjacent vertices and B is not one of them. You could then use backtracking (classic AI search algorithm that goes back to the prior choice and makes a different one, and doing so recursively if all options fail at that point), but I’m not sure how this affects the claim of random selection from possible paths. Thus an algorithm that identifies all of (not just one of) the alternatives may be needed with a specified target. (I welcome any corrections or additions from anyone more expert in this area.)
Perhaps this is TMI but it was interesting to think about it.
1 Like