Say I have a graph with several nodes. I need to design an algorithm which randomly creates directed edges between nodes while satisfying the following conditions:

• each node has exactly one edge pointing to it
• each node has exactly one edge pointing away from it
• no node points to itself

For example, say my graph had three nodes, the following scenarios would be acceptable:

• Node A points to B, B points to C, C points to A
• Node A points to C, C points to B, B points to A

Does anyone know what the most efficient way of doing this would be? I'm using nodejs btw. For argument's sake, we can say that I am starting with an array containing the names of the nodes.

Thanks

CodePudding user response：

lets define you have array of vertex: V = {v}; |V| = N, now we can shuffle array of vertex by using any random shuffle algorithm.

V = [v_1, v_2, v_3,..,v_n]

Now we can define N-1 edges E, where e[i] = (v[i] to v[i 1]), and the last vertex will be (v[N-1] to v[0])