Return to Question

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:

1. 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.

2. 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'$.

3. 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} $$

Suppose we have a large directed graph $G$ with no self-cycle and no more than one edge between two nodes, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve these goals as quickly as possible:

1. 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.

2. 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'$.

3. 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} $$

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:

1. 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.

2. 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'$.

3. 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.

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 we can get two cycles. Suppose we get the first one.

1. $$ \require{AMScd} \begin{CD} 1 @>>> 2\\ & \nwarrow @VVV\\ & & 3 \end{CD} $$

2. $$ \require{AMScd} \begin{CD} 1 @>>> 2\\ @AAA @VVV\\ 4 @<<< 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} $$

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:

1. 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.

2. 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'$.

3. 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} $$

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:

1. 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.

2. 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'$.

3. 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.

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 we can get two cycles:

$$ \require{AMScd} \begin{CD} 1 @>>> 2\\ & \nwarrow @VVV\\ & & 3 \end{CD} $$

$$ \require{AMScd} \begin{CD} 1 @>>> 2\\ @AAA @VVV\\ 4 @<<< 3 \end{CD} $$

Then, after reversing this 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} $$

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:

1. 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.

2. 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'$.

3. 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.

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 we can get two cycles. Suppose we get the first one.

1. $$ \require{AMScd} \begin{CD} 1 @>>> 2\\ & \nwarrow @VVV\\ & & 3 \end{CD} $$

2. $$ \require{AMScd} \begin{CD} 1 @>>> 2\\ @AAA @VVV\\ 4 @<<< 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} $$