Suppose we have a large directed graph $G$, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve these goals as quickly as possible:
Find a random cycle $R$ in this graph. The 'Random' means no matter how big the cycle is, all the possible cycles should be picked with the same probabilities. (To be clear, a cycle means a directed close cycle) If there is no cycle in this graph, then stop and exit.
After finding the random cycle, we reverse this cycle $R$, which means this cycle will be changed to another direction. Now how should we find a random cycle on this new graph $G'$.
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 cycle easily.
It's okay to preprocess the graph for a long time, but what I want is to ensure that the step 1 and step 2 could be as quickly as possible.
For example, now we have a graph:
$$ \require{AMScd} \begin{CD} 1 @>>> 2\\ @AAA \nwarrow @VVV\\ 4 @<<< 3 \end{CD} $$
First we need to find a random cycle, and there are two cycles in this graph. Suppose we get this one.
$$ \require{AMScd} \begin{CD} 1 @>>> 2\\ & \nwarrow @VVV\\ & & 3 \end{CD} $$
Then, after reversing the first cycle, the graph becomes:
$$ \require{AMScd} \begin{CD} 1 @<<< 2\\ @AAA \searrow @AAA\\ 4 @<<< 3 \end{CD} $$
When we get a random cycle on this graph, there are two cycles that we can choose:
1. $$ \require{AMScd} \begin{CD} 1 @<<< 2\\ & \searrow @AAA\\ & & 3 \end{CD} $$
2. $$ \require{AMScd} \begin{CD} 1 & \\ @AAA \searrow &\\ 4 @<<< 3 \end{CD} $$