0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Suppose there are n edges. Generate uniformly an n bit binary number, and use this to select edges. If the edges form a ring, go with it. Otherwise, try again. Since there are potentially exponentially many rings, I do not see how you are going to do much better. Gerhard "There Are Lots Of Cycles" Paseman, 2018.09.07. $\endgroup$ – Gerhard Paseman Sep 8 '18 at 0:55
  • 1
    $\begingroup$ What do you mean by a ring? A simple directed cycle? $\endgroup$ – Robert Israel Sep 8 '18 at 1:46
  • 1
    $\begingroup$ But reversing a ring will destroy cycles ("rings") from the original graph $G$, so they will never be found. Moreover, the directed cycles that you do find by this algorithm will be dependent upon the random sequence that the cycles are found. Surely you don't want to create a table that 1) contains cycles that were not in the original graph, and 2) depend upon the random sequence of discovery. Right? $\endgroup$ – David G. Stork Sep 8 '18 at 3:52
  • 1
    $\begingroup$ @GerhardPaseman: Often graph algorithms can be better than you think. For instance, a somewhat similar question is how to randomly (uniformly) select a spanning tree, say in $K_n$. If you randomly choose $n-1$ edges, then the probability that they make a spanning tree is something like $1/n^n$ so it will take an extremely long time to get one that works. But Wilson's algorithm samples one in polynomial time. $\endgroup$ – Nate Eldredge Sep 8 '18 at 15:15
  • 5
    $\begingroup$ There's no general efficient algorithm to sample uniformly a directed simple cycle (unless RP = NP) - see Jerrum-Valiant-Vazirani '86, proposition 5.1. This doesn't mean that it's hopeless for your graphs - e.g. there might be some Markov chain that happens to mix rapidly for the kind of graphs you care about. (Do you want simple cycles or are cycles with points of degree > 2 allowed?) $\endgroup$ – Lorenzo Sep 8 '18 at 15:25
0
$\begingroup$

Here is what I thought:

  1. First we need to define some terms:

$Out(V)$: the set of vertices which is the tail ends adjacent to vertex $V$

$In(V)$: the set of vertices which is the head ends adjacent to vertex $V$

Outdegree $deg^+(V)$: the size of $Out(V)$.

Indegree $deg^-(V)$: the size of $In(V)$.

Deadends: $\{V \mid deg^-(V) = 0 \text{ or } deg^+(V) = 0\}$

$V$ is Unobvious deadend: $\bigwedge_{u \in Out(V) \bigcup In(V)} \{u \text{ is deadend or unobvious deadend}\}$

  1. Then we start to get a random cycle:

$Step1$: Calculate $Out(V)$ and $In(V)$ for all vertices. Check and put all the deadends in a set $Deadend$.

$Step2$: Pick a random vertex $V$ from the graph $G$ except $Deadend$, and put it into two queues $OutQueue$ and $InQueue$ to do two BFS searches. And there are also two sets $OutVisited$ and $InVisited$ to store what vertices we have already visited.

$Step3$: Pop the first vertex in $OutQueue$ as $outU$ and $InQueue$ as $inU$. Check whether $inU$ is in $OutVisited$ or $outU$ in $InVisited$, which means we have already find a cycle. If found, go to $Step6$. If not found, then put $outU$ in $OutVisited$ and $inU$ in $InVisited$.

$Step4$: Put all the vertices, which is not deadend and not unobvious deadend, in $Out(outU)$ into $OutQueue$. If all of the vertices in $Out(outU)$ are in $Deadend$, then put $outU$ into $Deadend$, and back to $Step3$. Do the same for $In(inU)$ and $InQueue$.

$Step5$: If $OutQueue$ or $InQueue$ is empty, this means we cannot find a cycle from this vertex $V$, then we put all the visited vertices in $Deadend$. Back to $Step2$ to start a new skimming.

$Step6$: If find a cycle, return this cycle. If all of the vertices are in the $Deadend$, then there's no cycle in this graph.

  1. If we get a cycle, reverse the cycle, and find a new random cycle:

Reversing a cycle in the graph G will not change $Out(V)$ and $In(V)$.

And to find a new random cycle, do as the same as mentioned above.



However, there are some problems of this method:

  1. This method cannot ensure that every cycles in graph $G$ will be equally picked.

  2. I am not sure that only by checking outdegrees and indegrees will not miss a cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.