1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

How to find a random cycle in a large graph?

Discussion in 'Mathematics' started by Ian, Oct 8, 2018.

  1. Ian

    Ian Guest

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

    Login To add answer/comment

Share This Page