Suppose we have a large directed graph, containing about 2000 nodes and about 10 edges per node. Now we need to achieve these goals as quickly as possible:
Find a random ring in this graph. The 'Random' means no matter how big the ring is, all the possible rings should be picked with the same probabilities. (To be clear, a ring means a directed close ring)
After finding the random ring, we reverse this ring, which means this ring will be changed to another direction. Now how should we find a random ring on this new graph.
The step 1 and step 2 can be invoked for many times, please find a proper way to store the graph and find a random ring easily.
For example, now we have a graph:
{ 1 -> [2], 2 -> [3], 3 -> [1, 4], 4 -> [1] }
First we need to find a random ring, and we can only get one ring:
[1 -> 2 -> 3 -> 1].
Then, after reversing this ring, the graph becomes:
{ 1 -> [3], 2 -> [1], 3 -> [2, 4], 4 -> [1] }
When we get a random ring on this graph, there are two rings that we can choose:
[1 -> 3 -> 2 -> 1]
[1 -> 3 -> 4 -> 1]